The max-flow min-cut theorem of Ford and Fulkerson (for undirected networks) may be regarded as a statement about the circuits and cocircuits using some fixed element of the cycle matroid of a graph. We show that, in general, a matroid has this property (in the integer form) if and only if it is binary and has no minor isomorphic to the dual of the Fano matroid.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics