Perfect Matchings and What Parity Can Tell Us
A perfect matching must cover every vertex exactly once. That requirement creates simple counting constraints: the graph must have an even number of vertices, each component must contain an even number, and the number of matching edges crossing any chosen vertex set has a prescribed parity. Degree information adds local restrictions: an isolated vertex cannot be covered, while the only edge at a degree-one vertex must be used. These tests can quickly rule out a perfect matching or narrow down its possible edges.
They are necessary conditions, not a complete existence test. A graph may pass the basic parity checks and still have no perfect matching. The goal is to use the restrictions accurately, and to know what they do and do not establish.
All graphs below are finite and simple. The empty graph, with \(V=\varnothing\) and \(E=\varnothing\), has the empty matching as a perfect matching: there are no vertices left unsaturated. For a nonempty graph, a perfect matching can exist only if the vertex set can be partitioned into pairs joined by edges.
Vertex Counts and Components
Proof. Let \(M\) be a perfect matching. Every edge of \(M\) covers exactly two vertices, and different edges of \(M\) have no common endpoints. Since every vertex is covered, \(V\) is partitioned into pairs, so \(|V|=2|M|\), which is even. Each edge has both endpoints in one connected component: otherwise its endpoints would themselves connect two components. Thus the edges of \(M\) partition the vertices of each component into pairs as well. Each component consequently has even order. If \(V=\varnothing\), there are no components and \(|V|=0=2|M|\), so the statements also hold. \(\square\)
The component condition can be more informative than the total vertex count. A graph with an even total order can still have an odd-order component. No matching edge can leave that component to pair one of its vertices with a vertex elsewhere.
Worked Example: Even Order but No Perfect Matching
Let \(G=(V,E)\), where \(V=\{1,2,3,4,5,6\}\) and \(E=\{12,23,31,45,56,64\}\). This is the disjoint union of two triangles. The total order is \(|V|=6\), which is even, so the total-order test alone does not rule out a perfect matching.
The two connected components have vertex sets \(\{1,2,3\}\) and \(\{4,5,6\}\), each of size \(3\). By the theorem, a perfect matching would have to pair the vertices within each component, but a set of three vertices cannot be partitioned into pairs. Therefore \(G\) has no perfect matching.
Check: A matching in a triangle contains at most one edge, so in this graph a matching contains at most one edge from each triangle, hence at most \(2\) edges total. A perfect matching on \(6\) vertices would need \(6/2=3\) edges. This independently confirms that no perfect matching exists.
Even order for every component is only a necessary condition. It does not say that the edges inside a component can actually pair its vertices. Degree restrictions provide another way to detect a failure.
Degree Constraints: Impossible and Forced Edges
Proof. If a vertex has degree \(0\), it is incident to no edge and so cannot be saturated by any matching. Now suppose a vertex \(v\) has degree \(1\), and let \(uv\) be its unique incident edge. A perfect matching must saturate \(v\), so it must use an edge incident to \(v\). Since \(uv\) is the only such edge, every perfect matching must contain \(uv\). \(\square\)
Once a forced edge \(uv\) is chosen, the remaining vertices must be matched using the graph obtained by deleting \(u\) and \(v\). More precisely, if \(uv\in E\), then \(G\) has a perfect matching containing \(uv\) exactly when \(G-\{u,v\}\), the subgraph induced by the remaining vertices, has a perfect matching. One direction follows by removing \(uv\) from the matching; the other follows by adding \(uv\) to a perfect matching of the remaining graph. This reduction can be repeated, but a contradiction can arise if two forced edges share an endpoint.
Worked Example: Degree-One Vertices Cause a Conflict
Let \(G=(V,E)\), where \(V=\{c,1,2,3\}\) and \(E=\{c1,c2,c3\}\). This is the star \(K_{1,3}\). Its order is \(4\), so the total-order test does not rule out a perfect matching.
Each of the three vertices \(1,2,3\) has degree \(1\). For a perfect matching, the proposition would force all three edges \(c1,c2,c3\) to be present. But they all share the endpoint \(c\), so they cannot all belong to a matching. In fact, any matching can contain at most one edge of this graph and can therefore cover at most \(2\) of its \(4\) vertices.
Check: A perfect matching on \(4\) vertices must contain \(4/2=2\) pairwise disjoint edges. The edge set has no two pairwise disjoint edges, since every edge is incident to \(c\). Thus there is no perfect matching, despite the even order and the fact that the graph is connected.
In other graphs, repeatedly applying the degree-one rule identifies a candidate matching rather than a contradiction. Every forced edge must be checked against the remaining graph; finding forced edges is not by itself a proof that all vertices can be covered.
Worked Example: Forced Edges Determine a Perfect Matching
Let \(G=(V,E)\), where \(V=\{1,2,3,4,5,6\}\) and \(E=\{12,23,34,45,56\}\), the path on six vertices. Vertex \(1\) has degree \(1\), so edge \(12\) is forced. Delete vertices \(1,2\). In the remaining graph on \(\{3,4,5,6\}\), vertex \(3\) has only the neighbor \(4\), so \(34\) is forced. Delete \(3,4\); the remaining vertices \(5,6\) are joined by edge \(56\), which must be selected. The resulting set is \(M=\{12,34,56\}\).
The edges in \(M\) are pairwise disjoint and their endpoints are exactly \(\{1,2,3,4,5,6\}\), so \(M\) is a perfect matching. The forced choices also show it is the only one: \(12\) is required, then \(34\) is required, and finally \(56\) is required.
Check: The matching has \(3\) edges, and \(2|M|=2\cdot3=6=|V|\). Directly, the three edges cover vertices \(1,2\), \(3,4\), and \(5,6\), with no endpoint repeated.
Parity Across a Cut
For a vertex set \(S\subseteq V\), an edge crosses from \(S\) to \(V\setminus S\) if exactly one of its endpoints lies in \(S\). The cut edges are the edges with this property. A perfect matching cannot choose an arbitrary number of cut edges: its number of chosen crossing edges has the same parity as \(|S|\).
Proof. Let \(a\) be the number of edges of \(M\) with both endpoints in \(S\), and let \(b\) be the number of edges of \(M\) with exactly one endpoint in \(S\). Because \(M\) is perfect, every vertex of \(S\) is covered. Each of the \(a\) internal edges covers two vertices of \(S\), and each of the \(b\) crossing edges covers one. Therefore \(|S|=2a+b\). Since \(2a\) is even, \(b\) and \(|S|\) have the same parity. This also covers \(S=\varnothing\), for which \(a=b=0\). \(\square\)
This condition tests a candidate matching by counting only its selected edges that cross the chosen cut. If \(|S|\) is odd, that count must be odd; if \(|S|\) is even, it must be even. For a matching that is not necessarily perfect, let \(u\) be the number of its unsaturated vertices in \(S\). The same count gives \(|S|=2a+b+u\), so \(b\) has the parity of \(|S|-u\). The perfect-matching version is the special case \(u=0\).
Worked Example: Checking Both Perfect Matchings of a Six-Cycle
Let \(G=(V,E)\), where \(V=\{1,2,3,4,5,6\}\) and \(E=\{12,23,34,45,56,61\}\), a cycle of length \(6\). Take \(S=\{1,2,3\}\), so \(|S|=3\) is odd. The vertices outside \(S\) are \(\{4,5,6\}\). The crossing edges of the graph are \(34\) and \(61\): edge \(34\) has endpoint \(3\) in \(S\) and endpoint \(4\) outside, while \(61\) has endpoint \(1\) in \(S\) and endpoint \(6\) outside. The other edges \(12,23,45,56\) do not cross.
The perfect matching \(M=\{12,34,56\}\) uses edge \(34\) as its only crossing edge. Thus it has \(1\) crossing edge, which is odd, as the condition requires. The other candidate \(M'=\{23,45,61\}\) uses edge \(61\) as its only crossing edge: \(23\) lies entirely in \(S\), and \(45\) lies entirely outside \(S\). Thus \(M'\) also has \(1\) crossing edge, which is odd.
These are all the perfect matchings of this graph. Vertex \(1\) must be matched either to \(2\) or to \(6\). If \(1\) is matched to \(2\), then \(3\) must be matched to \(4\), leaving \(5\) to be matched to \(6\), giving \(M\). If \(1\) is matched to \(6\), then \(2\) must be matched to \(3\), leaving \(4\) to be matched to \(5\), giving \(M'\).
Check: Each listed matching has \(3\) edges with disjoint endpoints, and \(2\cdot3=6\), so each covers all \(6\) vertices. The cut contains exactly \(2\) graph edges, but the theorem concerns the number selected by a perfect matching: that number is \(1\) for \(M\) and \(1\) for \(M'\), not \(2\).
Using the Tests Carefully
The examples show several levels of checking. The total order is a first test; component orders refine it. Degree-zero and degree-one vertices impose local restrictions. A cut gives a parity condition on the selected matching edges, not necessarily on the total number of edges in the cut. If any necessary condition fails, there is no perfect matching. If all the tests pass, existence is still not established: additional structure may be needed to prove that a perfect matching exists.
A common mistake is to count every edge crossing a cut and treat that count as the number used by a perfect matching. The cut-parity theorem does not say that all cut edges are selected. For \(S=\{1,2,3\}\) in the six-cycle example, the cut edges are \(34\) and \(61\), but each of the two perfect matchings selects only one of them. Another error is to infer existence merely from even order. The two-triangle graph has even order but odd-order components, and the star has even order and is connected but cannot pair all its vertices.
When testing a proposed perfect matching, check all three parts of its definition: every listed edge belongs to \(E\), no two listed edges share an endpoint, and every vertex appears as an endpoint exactly once. Then use parity or degree constraints as independent checks. These calculations are useful both for rejecting impossible candidates and for reducing a search to a smaller graph.
Check Your Understanding
For each question, distinguish a necessary condition from a conclusion that proves existence.
- Why does a graph with an odd number of vertices have no perfect matching?
- A graph has two connected components of orders \(4\) and \(5\). Which necessary condition fails?
- Let \(S\) have \(7\) vertices. What parity must the number of edges of a perfect matching crossing from \(S\) to its complement have?
- In a graph, vertices \(a\) and \(b\) both have degree \(1\), and each has the unique neighbor \(c\). What does the degree-one rule imply about a perfect matching?
- Give a reason even order alone cannot guarantee a perfect matching, using one of the examples in this tutorial.