6
$\begingroup$

I heard that Hall's marriage theorem can be proved by the max-flow-min-cut theorem. Could you outline how that is possible?

Hall's theorem says that in a bipartite graph there exists a complete matching (covering all vertices of the smaller side) if and only if (naming one side of the bipartition A and the other B) for every subset $A_s$ of vertices in A there are at least $\lvert A_s\rvert$ vertices in B reachable form $A_s $ (through one edge).

$\endgroup$
1
$\begingroup$

Let $G$ be a bipartite graph with bipartition $(A,B)$. Suppose $G$ satisfies Hall's condition. We need to show $G$ has a complete matching from $A$ to $B$.

Form a directed graph from $G$ by adding a source vertex $s$, sink vertex $t$, joining $s$ to each vertex in $A$ and joining each vertex in $B$ to $t$. Assign each vertex in $A \cup B$ a capacity of $1$. In this digraph, the maximum flow from $s$ to $t$ is equal to the maximum number of independent edges in $G$ and hence is equal to the maximum size of a matching in $G$. We need to show this value is $|A|$. A min cut in the digraph is a set of vertices of the form $T_1 \cup T_2$ where $T_1 \subseteq A, T_2 \subseteq B$. To show that the max flow value is $|A|$, by the max flow min cut theorem it suffices to show that the min cut has value $|A|$. It's clear the min cut has size at most $|A|$ since $A$ is a cut.

Let $S_1 = A-T_1$ and $S_2 = B-T_2$. Since $T_1 \cup T_2$ is a cut, there are no edges in $G$ from $S_1$ to $S_2$. Hence, all the neighbors of $S_1$ are in $T_2$. If the min cut has size less than $|A|$, then $|T_1|+|T_2| < |A|$, and since $|T_1|+|S_1|=|A|$, we have $|T_2| < |S_1|$, which violates Hall's condition. Hence, the min cut has size equal to $|A|$. This proves that the maximum flow value is equal to $|A|$. This implies that $G$ has $|A|$ independent edges.

$\endgroup$
  • $\begingroup$ "Since $T_1 \cup T_2$ is a cut, there are no edges in $G$ from $S_1$ to $S_2$." I think you are equivocating between two different notions of "cut" here. The "cut" in max-flow-min-cut can be any set of vertices that contains $s$ but not $t$; there is no requirement that no edges cross the cut in the "wrong" direction. (Also, I suspect you want to declare capacities on edges, not on vertices.) $\endgroup$ – darij grinberg Dec 14 '17 at 21:57
  • $\begingroup$ "A min cut in the digraph is a set of vertices of the form $T_1 \cup T_2$ where $T_1 \subseteq A, T_2 \subseteq B$." I do not understand, why can't the cut contain the new vertices that you added, $s$ and/or $t$? $\endgroup$ – Erel Segal-Halevi Jan 16 at 7:15
0
$\begingroup$

I will give a hint. As always the entire ball game is picking the proper flow graph. As is the typical flavor, your flow graph will be bipartite with one side connected to the source, and the other connected to the sink. Now you want to attach weights to the edges to ensure that:

1) The flow "sees" the size of the sets in a cut.

2) Any sensible cut must respect the graph structure.

Hope that helps.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.