-
A matching in an undirected graph is a subset of its edges where each edge does not share endpoints with each other.
We say that a vertex is matched or saturated if it is an endpoint in one of the edges in the matching, otherwise it is unmatched or unsaturated.
-
A matching is a maximum matching if it contains as many edges as possible. Every vertex is adjacent to at most one edge of the matching.
-
A Complete Matching from
to in a bipartite with partitions and is a injection between the vertices in and a subset of vertices in such that corresponding vertices are joined.
Hall’s Marriage Theorem
-
Let
be a bipartite graph with partitions and . For each subset , let be the neighborhood of . Then a complete matching from
to exists if and only if
Transversal Theory Formulation
- Let
b a non-empty finite set and be a family of non-empty subsets of . Then has a transversal if and only if the union of any of the subsets contain at least elements.
Halmos-Vaughan Proof
-
Trivially, for any subset
must correspond to at least one vertex in so the condition holds. For the converse, suppose that for any subset
, then . Argue by strong induction. Clearly the base case where must hold. -
Now suppose it holds for
. Consider two cases. Let , and consider . Note as well that denotes the unmatched vertices in .
-
If
Then we are done as we will have at least a spare vertex in
which we may match to any vertex in . -
If
Then, by induction, we may match these vertices to each other leaving us with
vertices unmatched. The induction hypothesis applies for the remaining
vertices since this is a smaller subgraph. Let . We show by contradiction that it does. Now, if
, then together with the original vertices, we have Line 2 follows from the fact
and are disjoint. Note that is a subset of , so it must follow Halls’ condition that and this gives a contradiction to the above. Therefore, the induction hypothesis applies to
as well, and we may find a matching.
Rado’s Proof
-
Necessity follows from the previous proof
-
We show sufficiency by showing that each one of the subsets contains more than one element that can be removed without altering the condition outlined in Hall’s Theorem, and eventually we may reduce this to the case where each subset contains exactly one element, the element in the transversal
Suppose
contains elements , and the removal of either invalidates the condition (i.e., a reduction described above is impossible). Then there are subsets and of with the property that and where That is, consider the family but with one of
and removed from , and as stipulated, Hall’s condition doesn’t hold. But also Now, observe the contradiction The last line follows from inclusion-exclusion principle
Konig-Egevary Theorem
-
A vertex cover
is a subset of vertices such that every edge in the graph is incident to at least one vertex in -
A minimum vertex cover is a vertex cover which contains as few vertices as possible.
-
In any bipartite graph, the number of edges in a maximum matching equals the number of vertices in a minimum vertex cover.
-
Proof: Let
be a bipartite graph with bipartition . be a minimum vertex cover. denote the cardinality of the maximum matching the minimum vertex cover. Clearly
since the minimum vertex cover is incident to all edges, so any matching must match to at least some of these vertices. Split
into and , that is into sets that are contained in each of the bipartitions. Let
and . Clearly there is no edge connecting
and otherwise these edges weren’t covered by the covering. Consider a subset
. Clearly | otherwise we may simply use in , leading to a contradiction by the fact that is already a minimum vertex cover, so there can be no smaller. The above is Hall’s condition so Hall’s Marriage Condition applies.
A similar thing applies to
. So there must be a complete matching that contains the vertices of
and (i.e., ). This is only possible when (i.e., the matching contains all the vertices in the cover, plus possibly extra.). Since
and , the theorem is proven.
Menger’s Theorem
- Can be thought of as a special case of the Max-Flow Min-Cut Theorem
- (Wilson 28.1) Edge Version - the maximum number of edge-independent paths connecting two distinct vertices
and of a connected graph is equal to the minimum number of edges in a -edge cut. - (Wilson 28.1) Vertex Version - the maximum number of vertex disjoint paths connected two distinct vertices
and of a connected graph is equal to the minimum number of edges in a -vertex cut. - (Wilson 28.6) Menger’s Theorem implies Hall’s Theorem
- (Wilson 28.3) - A graph is
-connected if and only if any two distinct vertices of are connected by at least -edge disjoint paths - (Wilson 28.4) - A graph is
-connected if and only if any two distinct vertices of are connected by at least -vertex disjoint paths