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 misses a vertex if it leaves it unmatched.
A Perfect matching is one that covers every vertex of the graph.
A Complete Matching from to in a bipartite graph 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.

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.

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.

A matching is a Maximum Matching if it contains as many edges as possible.
- A vertex is critical if it is covered by every maximum matching.
Let be a path and a matching in . We say that is an alternating path relative to if every second edge of lies in . We may similarly define an alternating cycle. An augmenting path is an alternating path with its endpoints being unmatched.
If and are maximum matchings, all paths and cycles in the symmetric difference have even length.
- Proof: Any path in these matchings alternate relative to both and . Thus if has odd length, then is a matching in containing, WLOG, more edges of than with more edges than which is a contradiction.
(Godsil 3.5.2) Let such that no maximum matching misses both of them. Let and be the maximum matchings that miss and respectively. Then, there is a -path of even length in ¹
- Idea: If and lie on distinct paths, then any path on must be alternating in which implies is a matching which misses both vertices.

(Godsil 3.5.3) Let be distinct vertices in and a -path. If no vertex is critical, then no maximum matching misses both and .
- Proof: Argue by induction on path length. Clearly this is true for a path of two vertices, so consider that is distinct from . If the corresponding and paths do not contain critical vertices then no maximum matching misses both and , and both and .
  
  Since is not critical, there is a maximum matching that misses it. Argue by contradiction and suppose is a maximum matching missing and . Then, apply (Godsil 3.5.2) to find a path and path in . However, note that must only be incident to a single edge in which means both paths must be the same. We have which contradicts our stipulation that they are distinct.
Berge’s Lemma A matching is maximal if and only if there is no augmenting path with respect to .