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

Unable to parse markup [type=CF_MATHJAX]

.

It is most likely well 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

  Unable to parse markup [type=CF_MATHJAX]

  and

  Unable to parse markup [type=CF_MATHJAX]

  , 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

Unable to parse markup [type=CF_MATHJAX]

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

Unable to parse markup [type=CF_MATHJAX]

and

Unable to parse markup [type=CF_MATHJAX]

, such that

Unable to parse markup [type=CF_MATHJAX]

and

Unable to parse markup [type=CF_MATHJAX]

. Then the following is evidently true:

• There are no edges from

  Unable to parse markup [type=CF_MATHJAX]

  to

  Unable to parse markup [type=CF_MATHJAX]

  (otherwise the cut would be infinite);
• Thus, every edge in the bipartite graph is incident to some vertex from

  Unable to parse markup [type=CF_MATHJAX]

  or

  Unable to parse markup [type=CF_MATHJAX]

  (or both);
• Minimum cut is formed only by edges going from $$$S$$$ to

  Unable to parse markup [type=CF_MATHJAX]

  and from

  Unable to parse markup [type=CF_MATHJAX]

  to $$$T$$$ and thus its size is

  Unable to parse markup [type=CF_MATHJAX]

  .

Putting it all together, the minimum vertex cover is

Unable to parse markup [type=CF_MATHJAX]

, and it can be easily found from the minimum cut:

1. Find a minimum cut

   Unable to parse markup [type=CF_MATHJAX]

   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

   Unable to parse markup [type=CF_MATHJAX]

   and

   Unable to parse markup [type=CF_MATHJAX]

   .

(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)

Unable to parse markup [type=CF_MATHJAX]

of any

Unable to parse markup [type=CF_MATHJAX]

is such that

Unable to parse markup [type=CF_MATHJAX]

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

Note that for $$$k=1$$$ and

Unable to parse markup [type=CF_MATHJAX]

, 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

Unable to parse markup [type=CF_MATHJAX]

.

If the graph is not a $$$k$$$-expander, there can't be such flow, as there is a subset

Unable to parse markup [type=CF_MATHJAX]

through which you can't push flow of size

Unable to parse markup [type=CF_MATHJAX]

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

Unable to parse markup [type=CF_MATHJAX]

, the graph is not a $$$k$$$-expander.

Let's split the minimum cut into

Unable to parse markup [type=CF_MATHJAX]

and

Unable to parse markup [type=CF_MATHJAX]

, as above. There still must be no edges from

Unable to parse markup [type=CF_MATHJAX]

to

Unable to parse markup [type=CF_MATHJAX]

, as they have infinite capacities. So, there is a cut of size

Unable to parse markup [type=CF_MATHJAX]

, which translates into

Unable to parse markup [type=CF_MATHJAX]

.

On the other hand, edges from

Unable to parse markup [type=CF_MATHJAX]

are only directed in

Unable to parse markup [type=CF_MATHJAX]

, thus

Unable to parse markup [type=CF_MATHJAX]

is a subset of $$$A$$$ for which

Unable to parse markup [type=CF_MATHJAX]

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

   Unable to parse markup [type=CF_MATHJAX]

   have capacity $$$k$$$, edges

   Unable to parse markup [type=CF_MATHJAX]

   have capacity $$$1$$$ and edges

   Unable to parse markup [type=CF_MATHJAX]

   have capacity $$$+\infty$$$;
2. Check that the maximum flow (minimum cut) in the network is

   Unable to parse markup [type=CF_MATHJAX]

   . If it is, the graph is a $$$k$$$-expander, otherwise it's not.