Proving vertex form of Menger's Theorem et al. without using capacity of vertices.

499 Views Asked by At

I'm teaching an undergrad course in graph theory and have just finished the proof of Max Flow/Min Cut. So far I have used Diestel's definition (more or less) of flow network as a digraph $G$ with a capacity function $c: E\rightarrow \mathbb{N}$ and a flow function $f:E\rightarrow \mathbb{Z}$ satisfying

  1. $f(e)\leq c(e)$ for all $e\in E(G)$
  2. $f(y,x) = -f(x,y)$ for all $x, y\in G$
  3. $f(u, V(G)) = 0$ for $u\neq s, t$, where $$f(u, X) := \sum_{v\in X}\:f(u,v)$$

The edge form of Menger's Theorem is easy enough to prove with these axioms, but all proofs of the vertex form I have found online or in texts require either different axioms [e.g., drop (2) and substitute an equality of sums for (3)] or defining the capacity of a vertex, neither of which sounds too appealing for an undergrad course where the applications need to be as straightforward as possible.

It seems like the correct approach would involve creating an auxiliary graph in which the vertices of the graph in question were replaced with capacity 1 (yielding a cut which would be the min cut) and then tying the number of independent paths to the value of a flow function using an augmenting path algorithm.

(If you have room: Bollobás gives a proof of Hall's using Max Flow/Min Cut, but with vertex capacities ... is there a simple proof using edge capacities?)