How many disjoint edge-cuts a DAG must have? The following question is related to the optimality of the Bellman-Ford $s$-$t$ shortest
path dynamic programming algorithm (see this post for a connection). Also, a positive answer would imply that the minimal size of 
a monotone nondeterministic branching program for the 
STCONN problem is $\Theta(n^3)$.

Let $G$ be a DAG (directed acyclic graph)
with one source node $s$ and one target node $t$.
A $k$-cut is a set of edges, whose removal destroys all $s$-$t$ paths
of length $\geq k$; we assume that there are such paths in $G$. 
Note that shorter $s$-$t$ paths need not be destroyed.


Question:
Does $G$ must have at least (about) $k$ disjoint $k$-cuts?


If there are no $s$-$t$ paths shorter than $k$, the answer is YES, because
we have the following known min-max fact (a dual to
Menger’s theorem) attributed to Robacker$\ast$.
An $s$-$t$ cut is
a $k$-cut for $k=1$ (destroys all $s$-$t$ paths).


Fact:
In any directed graph, the maximum number of edge-disjoint $s$-$t$ cuts is equal to the minimum length of an $s$-$t$ path.


Note that this holds even if the graph is not acyclic.

Proof:
Trivially, the minimum is at least the maximum, since each $s$-$t$
path intersects
each $s$-$t$ cut in an edge.
To see equality, let $d(u)$ be the length of a shortest path from $s$ to $u$.
Let  $U_r=\{u\colon d(u)=r\}$, for $r = 1,\ldots, d(t)$, and
let $E_r$ be the set of edges leaving $U_r$.
It is clear that the sets $E_r$ are disjoint, because the sets $U_r$ are such.
So, it remains to show that each $E_r$ is an $s$-$t$ cut.
To show this, take an arbitrary $s$-$t$ path $p=(u_1, u_2, \ldots,u_m)$
with $u_1=s$ and $u_m=t$. Since $d(u_{i+1})\leq d(u_i)+1$, the sequence
of distances $d(u_1),\ldots,d(u_m)$ must reach the value
$d(u_m)=d(t)$ by starting at $d(u_1)=d(s)=0$ and increasing the value by at
most $1$ in each step. If some value $d(u_i)$ is decreased , then we must
reach value $d(u_i)$ latter. So, there must be a $j$ where a jump
from $d(u_j)=r$ to $d(u_{j+1})=r+1$ happens, meaning the edge $(u_j,u_{j+1})$
belongs to $E_r$, as desired. Q.E.D.

But what if there are also shorter (than $k$) paths? Any hint/reference?


$^{\ast}$
J.T. Robacker, Min-Max Theorems on Shortest Chains and Disjoint Cuts of a Network, 
Research Memorandum RM-1660, The RAND Corporation, Santa Monica, California, [12 Jan-
uary] 1956. 

EDIT (a day later): Via a short and very nice argument, 
David Eppstein answered the original question 
above in negative: the complete DAG $T_n$ (a transitive tournament) cannot have more than four disjoint $k$-cuts! In fact, he proves the following interesting structural fact, for $k$ about $\sqrt{n}$. A cut is pure if it contains no edges incident to $s$ or to $t$.


Every pure $k$-cut in $T_n$ contains a path of length $k$.


This, in particular, implies that every two pure $k$-cuts must intersect! But perhaps there still are many pure $k$-cuts that do not overlap
"too much". Hence, a relaxed question (the consequences for STCONN would be the same):


Question 2: 
If every pure $k$-cut has $\geq M$ edges, does then the graph must have 
about $\Omega(k\cdot M)$ edges?


The connection with the complexity
of STCONN comes from the result of Erd&#337;s and Gallai that one has to remove all but $(k-1)m/2$ edges from (undirected) $K_m$ in order to destroy all paths of length $k$. 

EDIT 2: I now asked Question 2 at mathoverflow.
Short answer: no.

Let $G$ be a complete DAG (transitive tournament) on $n$ vertices with $s$ and $t$ its source and sink, and let $k=\sqrt{n/3}$. Observe that there can be at most four disjoint cuts that contain more tham $n/3$ edges incident to $s$ or more than $n/3$ edges incident to $t$. So, if there are to be many disjoint cuts, we can assume that there exists a cut $C$ that does not contain large numbers of edges incident to $s$ and $t$.

Now let $X$ be the complete subgraph induced in $G$ by the set of vertices $x$ such that edges $sx$ and $xt$ do not belong to $C$. The number of vertices in $X$ is at least $n/3$, because otherwise $C$ would touch too many edges incident to $s$ or $t$. However, $X\setminus C$ cannot contain a $k$-path, because if such a path existed it could be concatenated with $s$ and $t$ to form a long path in $G\setminus C$. Therefore, the longest-path layering of $X\setminus C$ has fewer than $k$ layers, and has a layer containing more than $(n/3)/k=k$ vertices. Since this is a layer of the longest path layering, it is independent in $X\setminus C$, and therefore complete in $C$, so $C$ contains a path $P$ through the vertices of this layer, of length $k$. This path must be disjoint from all of the other cuts.

Every cut that is not $C$ must contain either the edge from $s$ to the start of path $P$ or the edge from the end of path $P$ to $t$, or else it would not block the path $s$–$P$–$t$. So if $C$ exists, there can be at most three disjoint cuts. And if $C$ does not exist (that is, if all cuts cover more than $n/3$ edges incident to $s$ or to $t$) there can be at most four disjoint cuts. Either way, this is a lot fewer than $k$ cuts.