Matchings

A matching in a GraphGraph is a subset such that no two edges in have a common vertex.

If a vertex is contained in an edge in it is called matched, otherwise unmatched.

A maximum matching of is a matching such that no matching of has strictly greater cardinality.

A complete matching or perfect matching of is a matching such that every vertex is matched.

Let be a graph and be a matching of . Then the path where is an alternating path for if the edges are in but the edges are not in , for all , and and are unmatched.

Let be a graph and be a matching of . Then there is an alternating path for if and only if is not maximal.

Proof:
: Let be an alternating path for . Then, remove all edges from and insert all edges . The resulting matching is still a matching since and were previously unmatched. We thus removed edges and added edges, resulting in a larger matching, hence was not maximal to begin with.
: Let be a maximum matching, and let be the set of edges which are in or but not in both. is nonempty since is not maximal. Consider the graph . Every vertex must have degree at most , meaning consists of cycles and/or paths. In a cycle, precisely every second edge would need to belong to and every second to , so if consisted only of cycles we would have which is false. Hence can only have more edges if there is a path with an odd number of edges where there is one more edge from than from . This is then clearly an alternating path for .

The deficiency of a bipartite graph is where is the set of neighbours of .

The size of a maximum matching in a bipartite graph is Proof:
It is clear that is an upper bound for since if such that , then for any matching, at least vertices of are unmatched. By TheoremTheorem, it is thus sufficient to show that given any matching with , there is an alternating path for .

Let contain the unmatched vertices of , so . Then so there is a . If is unmatched we are done. Otherwise, let be matched with . Then , so there is another vertex which is a potential end of an alternating path. By continuing this process, we always reach new vertices of , so since the graph is finite, we will eventually reach an unmatched vertex of , to which we can create an alternating path from some vertex in .

Let be a bipartite graph. Hall's condition is the statement that for every . In other words, that .

A bipartite graph has a complete matching if and only if Hall's condition is satisfied.

1. Start with any matching with at least one edge.
2. Search for an alternating path for .
3. If an alternating path is found, construct a larger matching by "inverting" the alternating path, i.e. adding every edge of the path that was not in , and removing the ones that were. Then repeat from 2.
4. If no alternating path can be found, we are done.

The brute force way is to choose an unmatched vertex and see if there is an alternating path starting with by just trying everything recursively.