Short Proofs of Hall’s and Kőnig’s Theorems
The motivation of this post is to provide a concise proof concept that can be used to prove both Hall’s marriage theorem and Kőnig’s theorem, which are two of the most well-known theorems in graph theory. Particularly, the max flow min cut theorem concerning a flow network can be employed.
I. Constructing a flow network for any bipartite graph
Given any bipartite graph G = X ∪ Y, we can construct a flow network as follows.
Basically, we add a source (s) and a sink (t) connecting to X and Y, respectively, such that the edges from s or the edges to t are assigned unit capacity whereas the original edges in G are assigned infinite capacity.
As a result of this, we can observe the following notable fact: given a min cut (as per max flow min cut theorem) {s} ∪ X₁ ∪ Y₁ and {t} ∪ X₂ ∪ Y₂ where X = X₁ ∪ X₂ and Y = Y₁ ∪ Y₂, the max flow should be equal to |X₂| + |Y₁| due to the fact that there cannot be any edges from X₁ to Y₂ (as otherwise we need to add infinity to the min cut value = max flow value, which is nonsensical).
II.a. Application to Kőnig’s theorem
Given the max flow whose value is |X₂| + |Y₁|, we note that X₂ ∪ Y₁ is in fact a vertex cover of G due to the aforementioned aspect that there cannot be any edges from X₁ to Y₂. Due to the one-to-one correspondence between a flow and a matching (i.e. one can think of a matching as a flow in our flow network construction and vice versa), this means that we are able to find a matching and a vertex cover whose sizes are equal in a bipartite graph, proving Kőnig’s theorem.
II.b. Application to Hall’s marriage theorem
Again given the max flow whose value is |X₂| + |Y₁|, we note that |X₂| + |Y₁| is in fact greater than or equal to |X₂| + |X₁| = |X| in the context of Hall’s marriage theorem, because Y₁ is (a superset of) the neighborhood of X₁ due to the fact that there cannot be any edges from X₁ to Y₂. In other words, we are able to find a flow (and thus a matching) whose value is moreover equal to |X|, as it cannot be strictly greater than |X|. This yields a matching of size |X| in G, proving Hall’s marriage theorem.
