Kőnig's and Hall's theorems through minimum cut in bipartite graphs

Revision en15, by adamant, 2022-08-07 14:51:32

Hi everyone!

There is a well-known result about bipartite graphs which is formulated as follows:

In any bipartite graph, the number of edges in a maximum matching equals the number of vertices in a minimum vertex cover.

Knowing it you can easily find the size of a minimum vertex cover in a given bipartite graph. But what about actually recovering such cover? Well... There is an algorithm to it, but it's lengthy and not very motivated, so I constantly forget its details. However, there is a simple alternative, which is easily reproduced from scratch, even if you forget specific details.

Besides, there is another well-known result which is formulated as follows:

A bipartite graph has a perfect matching if and only if every subset $\alpha$ of one part has a neighborhood $\beta$ in the other part such that $|\beta| \geq |\alpha|$.

This result can be proven with a similar approach. It is likely known to those familiar with the topic, but still might be of interest to someone.

### Kőnig's theorem

Recall that given a flow network $G=(V, E)$, finding minimum cut between $s$ and $t$ is done as follows:

• Find a maximum flow $f$ from $s$ to $t$ in the network;
• Find $X$, the set of all vertices reachable from $s$ in the residual network;
• Minimum cut is formed by $S=X$ and $T=V \setminus X$, that is the minimum cut is formed by the edges going from $S$ to $T$.

Now, recall that bipartite matching between sets of vertices $A$ and $B$ may be found as maximum flow in the following network:

• There is an edge of capacity $1$ going from $s$ to every vertex of $A$;
• There is an edge of capacity $1$ going from every vertex of $B$ to $t$;
• There is an edge of capacity $+\infty$ going between some vertices of $A$ and $B$, as defined by the bipartite graph.

Now... Is there anything special about minimum cut in such network?

Minimum cut $(S, T)$ in a flow network induced by a bipartite graph

Generally, some vertices from $A$ and some vertices from $B$ will be with the source $s$ in the cut, while other will be with the sink $t$.

Let $A = A_S \cup A_T$ and $B = B_S \cup B_T$, such that $A_S, B_S \subset S$ and $A_T, B_T \subset T$. Then the following is evidently true:

• There are no edges from $A_S$ to $B_T$ (otherwise the cut would be infinite);
• Thus, every edge in the bipartite graph is incident to some vertex from $A_T$ or $B_S$ (or both);
• Minimum cut is formed only by edges going from $S$ to $A_T$ and from $B_S$ to $T$ and thus its size is $|A_T|+|B_S|$.

Putting it all together, the minimum vertex cover is $A_T \cup B_S$, and it can be easily found from the minimum cut:

1. Find a minimum cut $(S, T)$ in the flow network of the maximum matching on bipartite graph with parts $A$ and $B$;
2. A minimum vertex cover is comprised of the sets $A_T = (A \cap T)$ and $B_S = (B \cap S)$.

### (Generalized) Hall's theorem

The approach above is useful in some other cases as well. Consider the following problem:

A bipartite graph on parts $A$ and $B$ is a $k$-expander if the neighborhood (set of adjacent vertices) $\beta \subset B$ of any $\alpha \subset A$ is such that

$|\beta| \geq k |\alpha|.$

Given a bipartite graph, you need to check whether it is a $k$-expander.

Note that for $k=1$ and $|A|=|B|$, the condition above is, by Hall's theorem, equivalent to graph having a perfect matching.

Let's construct a similar flow network, but the edges from $s$ to $A$ will have capacity $k$, while the edges from $B$ to $t$ have capacity $1$, and the edges between $A$ and $B$ still have capacity $+\infty$. One has to check whether such graph has a maximum flow of size $k|A|$.

If the graph is not a $k$-expander, there can't be such flow, as there is a subset $\alpha \subset A$ through which you can't push flow of size $k|\alpha|$ no matter what. But how to prove that the graph is a $k$-expander when there is such flow?

Well, we rather prove that if the minimum cut in the graph has a capacity less than $k|A|$, the graph is not a $k$-expander.

Let's split the minimum cut into $A_S \cup B_S$ and $A_T \cup B_T$, as above. There still must be no edges from $A_S$ to $B_T$, as they have infinite capacities. So, there is a cut of size $k|A_T|+|B_S|<k|A|$, which translates into $|B_S| < k(|A|-|A_T|) = k|A_S|$.

On the other hand, edges from $A_S$ are only directed in $B_S$, thus $\alpha=A_S$ is a subset of $A$ for which $|\beta| \geq k|\alpha|$ does not hold.

That being said, the algorithm to check whether the graph is a $k$-expander is as follows:

1. Construct a network, in which edges $s \to A$ have capacity $k$, edges $B \to t$ have capacity $1$ and edges $A \to B$ have capacity $+\infty$;
2. Check that the maximum flow (minimum cut) in the network is $k|A|$. If it is, the graph is a $k$-expander, otherwise it's not.

#### History

Revisions

Rev. Lang. By When Δ Comment
en15 adamant 2022-08-07 14:51:32 57 Tiny change: 'first one.\n\nIt is like' -> 'first one. It is like'
en14 adamant 2022-08-07 03:35:16 4
en13 adamant 2022-08-07 02:03:52 383 Tiny change: 'nstruct a flow network, ' -> 'nstruct a network, '
en12 adamant 2022-08-07 02:00:57 9
en11 adamant 2022-08-07 02:00:31 2167 + Hall lemma
en10 adamant 2022-08-06 23:35:52 10 Tiny change: '$or$B_S$;\n- Minim' -> '$ or $B_S$ (or both);\n- Minim'
en9 adamant 2022-08-06 23:07:05 16 Tiny change: ' no edges between $A_S$ and $B_T$ (ot' -> ' no edges from $A_S$ to $B_T$ (ot'
en8 adamant 2022-08-06 23:05:45 19 Tiny change: 'and $B_T$ or $A_T$ and $B_S$ (otherwi' -> 'and $B_T$ (otherwi'
en7 adamant 2022-08-06 22:35:31 36 Tiny change: 'ver**.\n\nNow, the result is well-known and knowing it ' -> 'ver**.\n\nKnowing it '
en6 adamant 2022-08-06 22:32:30 16
en5 adamant 2022-08-06 22:31:16 10
en4 adamant 2022-08-06 22:29:00 216
en3 adamant 2022-08-06 22:24:33 8
en2 adamant 2022-08-06 22:16:36 828 Tiny change: 'g" width="600px">\n<b' -> 'g" width="700px">\n<b' (published)
en1 adamant 2022-08-06 21:57:14 1972 Initial revision (saved to drafts)