I'm trying to better understand the min-cut problem for directed acyclic graphs. I understand that the minimum capacity cut has equal capacity to the max flow of a graph by the max flow-min cut theorem (https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem). This makes some sense to me but I'm confused as to what happens in a DAG with unit edge weights. In this case, there's three claims I'm trying to make:
- The max flow of a DAG with unit edge weights has an upper bound equal to the sum of the number of edges entering all sinks. In other words, max flow is bounded by the sum of the indegree of all sink nodes.
- Because all edges have the same weight, there are $\binom{n}{\text{max flow}}$ possible min-cuts where $n$ is the number of edges. In essence, if the max flow for a DAG is 3, then choosing any 3 edges would give you a min-cut.
- If you apply the Ford-Fulkerson to identify a min-cut, it will effectively always include edges connected to the source node because those will immediately have their capacity maxed out and the algorithm returns the cut closest to the source(s).
These feel unintuitive to say the least but seem to hold true for the few small examples I tried to run through. In particular, the second statement seems very wrong to me. It seems to imply that any set of edges with capacity equal to max flow constitute a min-cut. While a min-cut definitely has capacity equal to max flow, I'd guess the reverse statement that any set of cuts with a capacity equal to max flow is a min-cut isn't necessarily true (though I can't quite come up with a counter-example).
My question is, are any of the 3 claims above true?
Edit:
After thinking about it some more, I think I found a counterexample to my 2nd claim. In the DAG below, the max flow is 2 but cutting any two of the dotted edges wouldn't yield a partition.