Matchings That Can Leave Any Chosen Vertex
A perfect matching pairs every vertex with exactly one other vertex. In an odd-order graph, that cannot happen: one vertex must be left out. A stronger question is whether the vertex left out can be chosen in advance. Graphs with this property are called factor-critical. They arise naturally when studying odd components in matching arguments: their defining feature is that any one vertex can be set aside while the rest are paired.
All graphs here are finite and simple. A matching is a set of edges no two of which share an endpoint. A matching is perfect if every vertex is an endpoint of one of its edges. A matching that leaves exactly one vertex uncovered is sometimes called a near-perfect matching. A maximum matching has largest possible size; a maximal matching is one to which no edge can be added while retaining a matching. These last two terms are not interchangeable.
For a vertex \(v\), \(G-v\) denotes the graph obtained by deleting \(v\) and every edge incident with \(v\). We count the empty matching as a perfect matching of the graph with no vertices, since it covers every vertex of that graph.
The requirement is “for every vertex,” not merely “for some vertex.” The matching may depend on which vertex is prescribed: different vertices can require different matchings. The definition includes the graph with one vertex. Its only vertex can be left uncovered by the empty matching.
The Vertex-Deletion Criterion
Proof. Suppose first that \(G\) is factor-critical, and fix any vertex \(v\). By definition, there is a matching \(M\) in \(G\) whose only uncovered vertex is \(v\). No edge of \(M\) is incident with \(v\), since a matching edge incident with \(v\) would cover it. Thus every edge of \(M\) belongs to \(G-v\), and every vertex of \(G-v\) is covered by \(M\). So \(M\) is a perfect matching of \(G-v\).
Conversely, suppose that \(G-v\) has a perfect matching for every vertex \(v\). Fix any \(v\), and take a perfect matching of \(G-v\). The same set of edges is a matching in \(G\); it covers every vertex other than \(v\), and leaves \(v\) uncovered. This works for every choice of \(v\), so \(G\) is factor-critical. \(\square\)
This criterion translates the definition into a useful test: choose a vertex to delete, then find a perfect matching in the remaining graph. It also makes the parity restriction immediate. If \(G-v\) has a perfect matching, its vertices occur in pairs, so \(|V(G)|-1\) is even. Hence every factor-critical graph has odd order. The condition does not say that \(G\) itself has a perfect matching; for odd order, that is impossible.
Proof. Let \(G\) be factor-critical. We have already shown that its order is odd. Suppose that \(G\) has at least two connected components. Fix a component \(C\), and choose \(v\in V(C)\). A perfect matching of \(G-v\) must match every vertex in each component other than \(C\) using edges within that component, since there are no edges between components. Therefore each component other than \(C\) has even order. Also, within \(C-v\), all vertices must be matched to one another, so \(|V(C)|-1\) is even and \(C\) has odd order. Now choose a vertex in a different component \(D\). Applying the same reasoning shows that \(C\) must have even order, because it is now a component other than the one from which a vertex was deleted. This contradicts that \(C\) has odd order. Thus \(G\) has only one component and is connected. The one-vertex graph is connected by the usual convention and is included. \(\square\)
Odd Cycles Are Factor-Critical
Proof. Label the vertices of the cycle in order \(v_0,v_1,\ldots,v_{2k}\), with edges between consecutive vertices and between \(v_{2k}\) and \(v_0\). Fix a vertex \(v_i\) to delete. The remaining vertices occur along the path that starts at \(v_{i+1}\) and continues around the cycle to \(v_{i-1}\), with indices read modulo \(2k+1\). This path has \(2k\) vertices. Pair its first and second vertices, its third and fourth vertices, and continue in this way. Each pair is joined by a cycle edge, and the pairs are disjoint and cover all \(2k\) remaining vertices. They form a perfect matching of \(C_{2k+1}-v_i\). Since the choice of \(i\) was arbitrary, every vertex can be deleted leaving a perfect matching. \(\square\)
Worked Example: Deleting Any Vertex of a 5-Cycle
Let \(G\) have \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,34,45,51\}\). There are five listed vertices and five listed edges; each vertex has two incident edges, so the degree sum is \(5\cdot2=10\), consistent with \(2|E|=2\cdot5=10\).
The theorem gives factor-criticality, and here are the perfect matchings for each deletion. Each row lists two edges; the edges share no endpoints and cover the four vertices remaining:
| Deleted vertex | Perfect matching in \(G-v\) | Vertices covered |
|---|---|---|
| 1 | \(\{23,45\}\) | \(2,3,4,5\) |
| 2 | \(\{34,51\}\) | \(1,3,4,5\) |
| 3 | \(\{45,12\}\) | \(1,2,4,5\) |
| 4 | \(\{51,23\}\) | \(1,2,3,5\) |
| 5 | \(\{12,34\}\) | \(1,2,3,4\) |
Check: deleting any one of the five vertices leaves \(5-1=4\) vertices, and each displayed matching has \(2\) edges, covering \(2\cdot2=4\) vertices. Every listed matching uses edges of \(G\), so the deletion criterion verifies factor-criticality.
Worked Example: Deleting Any Vertex of a 7-Cycle
Let \(G\) have \(V=\{1,2,3,4,5,6,7\}\) and \(E=\{12,23,34,45,56,67,71\}\). The cycle has seven vertices; its seven edges give each vertex degree \(2\), so the degree sum is \(7\cdot2=14=2\cdot7\). As in the odd-cycle theorem, deleting one vertex leaves a path with six vertices. The table pairs consecutive vertices along that path.
| Deleted vertex | Perfect matching in \(G-v\) | Vertices covered |
|---|---|---|
| 1 | \(\{23,45,67\}\) | \(2,3,4,5,6,7\) |
| 2 | \(\{34,56,71\}\) | \(1,3,4,5,6,7\) |
| 3 | \(\{45,67,12\}\) | \(1,2,4,5,6,7\) |
| 4 | \(\{56,71,23\}\) | \(1,2,3,5,6,7\) |
| 5 | \(\{67,12,34\}\) | \(1,2,3,4,6,7\) |
| 6 | \(\{71,23,45\}\) | \(1,2,3,4,5,7\) |
| 7 | \(\{12,34,56\}\) | \(1,2,3,4,5,6\) |
Check: each deletion leaves \(7-1=6\) vertices, and each row contains \(3\) disjoint edges, covering \(3\cdot2=6\) vertices. All the edges in the table occur in the specified edge set. Thus every deletion leaves a perfect matching.
Worked Example: A Chorded 5-Cycle
Factor-criticality is not limited to cycles. Let \(G\) have \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,34,45,51,13\}\): this is a 5-cycle with the additional edge \(13\). Its degrees are \(3,2,3,2,2\), whose sum is \(12\); the edge list has \(6\) edges, and \(2|E|=2\cdot6=12\).
For each deleted vertex, the following edges give a perfect matching of what remains:
| Deleted vertex | Perfect matching in \(G-v\) | Vertices covered |
|---|---|---|
| 1 | \(\{23,45\}\) | \(2,3,4,5\) |
| 2 | \(\{13,45\}\) | \(1,3,4,5\) |
| 3 | \(\{12,45\}\) | \(1,2,4,5\) |
| 4 | \(\{15,23\}\) | \(1,2,3,5\) |
| 5 | \(\{12,34\}\) | \(1,2,3,4\) |
Check: each row contains two disjoint edges from the stated edge set, and therefore covers \(2\cdot2=4\) vertices. Those are exactly the \(5-1=4\) vertices left after deletion. This verifies factor-criticality directly, without relying on the graph being exactly a cycle.
What the Criterion Does—and Does Not—Say
The deletion criterion is useful in matching arguments because it asks a local question for each possible exposed vertex: can the remaining graph be paired perfectly? In settings involving odd components and tight sets, factor-criticality records a particularly flexible form of matchability. The chosen vertex can be specified in advance, which is stronger than merely knowing that some matching leaves one vertex uncovered.
The criterion also gives quick necessary checks. A factor-critical graph must have odd order, and it must be connected. Neither check is sufficient on its own: an odd-order connected graph can still fail to have a perfect matching after some vertex is deleted. To establish factor-criticality, one must provide the required matching for every vertex, or invoke a proved result that guarantees them.
Common mistake: finding just one near-perfect matching. Consider the graph with \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,31,45\}\), a disjoint triangle and edge. The set \(\{12,45\}\) is a matching of size \(2\), leaving vertex \(3\) uncovered. That proves only that one vertex can be exposed. If vertex \(4\) is deleted, vertex \(5\) is isolated in \(G-4\), so \(G-4\) has no perfect matching. The graph is not factor-critical. In particular, the existence of a near-perfect matching does not establish the “for every vertex” condition.
A parity check can rule out factor-criticality just as quickly. For example, if \(C_4\) has one vertex deleted, three vertices remain. A matching covers vertices in pairs, so no matching can cover all three. Thus \(C_4\) is not factor-critical. This contrasts with an odd cycle, where deleting any vertex leaves an even number of vertices arranged in a path that can be paired consecutively.
Check Your Understanding
Use the deletion criterion, and distinguish a matching for one chosen vertex from matchings that work for every vertex.
- State the vertex-deletion criterion for factor-criticality and prove its two directions.
- Why must every factor-critical graph have odd order?
- List a perfect matching after deleting vertex \(3\) from the 7-cycle in the example.
- For the chorded 5-cycle, which edge in the displayed matching after deleting vertex \(2\) is the added chord?
- Why does the disjoint triangle and edge have a near-perfect matching but fail to be factor-critical?