The Guarantee for Bridgeless Cubic Graphs
A cubic graph has degree \(3\) at every vertex. A perfect matching pairs all its vertices using edges, with no vertex left unmatched. Petersen’s perfect matching theorem says that if a finite cubic graph has no bridge, then such a pairing always exists. The proof uses a degree count on the components left after deleting an arbitrary set of vertices: every odd component must send at least three edges to the deleted set, while that set has only three incident edges per vertex available.
All graphs in this tutorial are finite and simple. A matching is a set of edges no two of which share an endpoint; it is perfect if every vertex is an endpoint of one of its edges. A graph is cubic if every vertex has degree \(3\). A bridge is an edge whose deletion increases the number of connected components, and a graph is bridgeless if it has no bridges. For \(S\subseteq V(G)\), \(G-S\) denotes the subgraph induced by the vertices outside \(S\). Write \(o(G-S)\) for the number of connected components of \(G-S\) that have an odd number of vertices.
We will use Tutte’s theorem, established in the earlier material on Tutte’s condition: a finite graph \(G\) has a perfect matching if and only if \(o(G-S)\le |S|\) for every subset \(S\subseteq V(G)\). Thus it suffices to verify this inequality for an arbitrary \(S\). The key point is to get a lower bound on the number of edges leaving each odd component of \(G-S\).
Counting the Boundary of an Odd Component
For a vertex set \(X\subseteq V(G)\), let \(\partial X\) be the set of edges with exactly one endpoint in \(X\). If \(C\) is a component of \(G-S\), then every edge leaving \(C\) has its other endpoint in \(S\): an edge from \(C\) to another component of \(G-S\) would join those components.
Proof. Sum the degrees in \(G\) of the vertices in \(C\). Each edge with both endpoints in \(C\) contributes \(2\) to this sum, and each edge in \(\partial C\) contributes \(1\). There are no other contributions, so \(3|V(C)|=2|E(G[V(C)])|+|\partial C|\). Since \(|V(C)|\) is odd, \(3|V(C)|\) is odd, while \(2|E(G[V(C)])|\) is even. Therefore \(|\partial C|\) is odd. In particular, it is not zero. If it were \(1\), its only edge would separate the nonempty set \(V(C)\) from the rest of the graph when deleted, so that edge would be a bridge. Bridgelessness rules this out. The positive odd integer \(|\partial C|\) is therefore at least \(3\). \(\square\)
The case \(S=\varnothing\) is included. If an odd component \(C\) were then an entire component of \(G\), it would have \(|\partial C|=0\), contradicting the parity equation in the proof. In particular, every component of a cubic graph has even order. The lemma also applies when \(S=V(G)\): there are no components of \(G-S\), so its assertion has no instances.
Proof of Petersen’s Theorem
Proof. Let \(G\) be a finite bridgeless cubic graph. If \(G\) has no vertices, the empty set of edges is a perfect matching, so assume \(V(G)\ne\varnothing\). Fix any set \(S\subseteq V(G)\), and write \(q=o(G-S)\). If \(q=0\), then \(q\le |S|\) holds because \(|S|\ge0\). Now suppose \(q>0\), and list the odd components of \(G-S\) as \(C_1,\dots,C_q\).
By the lemma, each satisfies \(|\partial C_i|\ge3\). No edge can belong to two of these boundaries: such an edge would either join two distinct components of \(G-S\), which is impossible, or would have its other endpoint in \(S\), in which case its endpoint outside \(S\) belongs to just one component. Also, every boundary edge has one endpoint in \(S\). The total number of these edges is therefore at most the sum of the degrees of the vertices in \(S\), which is \(3|S|\). Edges with both endpoints in \(S\) contribute to that degree sum but not to the boundaries, so this is an upper bound even when \(S\) contains edges. Consequently, $$ 3q\le \sum_{i=1}^{q}|\partial C_i|\le 3|S|. $$ Dividing by \(3\) gives \(o(G-S)=q\le |S|\). Since \(S\) was arbitrary, \(G\) satisfies Tutte’s condition. Tutte’s theorem now gives a perfect matching in \(G\). \(\square\)
This argument also explains why disconnected graphs cause no difficulty. The odd components are counted across all components of \(G-S\), and their boundaries are still disjoint subsets of the edges incident with \(S\). If \(S=\varnothing\), the parity argument already shows that there are no odd components, as required by Tutte’s condition.
Worked Examples
Worked Example: The Complete Graph \(K_4\)
Let \(G\) have \(V(G)=\{1,2,3,4\}\) and \(E(G)=\{12,13,14,23,24,34\}\). Each vertex has degree \(3\), and no edge is a bridge: after any edge is deleted, its endpoints remain connected by a two-edge path through one of the other vertices. The edges \(12\) and \(34\) form a perfect matching: they are disjoint and cover all four vertices.
We can also check Tutte’s condition for every possible size of \(S\). Because every permutation of the four vertices preserves this graph, the component count depends only on \(|S|\). For \(|S|=0\), \(G-S=K_4\), so \(o(G-S)=0\). For \(|S|=1\), the remaining graph is \(K_3\), so \(o(G-S)=1\). For \(|S|=2\), the remaining graph is \(K_2\), so \(o(G-S)=0\). For \(|S|=3\), the remaining graph is one isolated vertex, so \(o(G-S)=1\). For \(|S|=4\), the remaining graph is empty, so \(o(G-S)=0\). Each value is at most \(|S|\).
Check: The exhibited matching has two edges, and its endpoints are exactly \(1,2,3,4\). The five component counts satisfy \(0\le0\), \(1\le1\), \(0\le2\), \(1\le3\), and \(0\le4\), respectively.
Worked Example: A Single Vertex Deleted from the Triangular Prism
Let \(G\) have vertex set \(\{1,2,3,4,5,6\}\) and edge set \(\{12,23,31,45,56,64,14,25,36\}\). Each of \(1,2,3\) has two neighbors in the triangle \(1,2,3\) and one in the triangle \(4,5,6\); the same degree count holds for \(4,5,6\). Thus \(G\) is cubic. It has no bridge: each triangle edge lies on its triangle, and each of \(14,25,36\) lies on a cycle using two of these joining edges and a path in each triangle.
Take \(S=\{1\}\). The remaining vertices are \(\{2,3,4,5,6\}\), with remaining edges \(23,45,56,64,25,36\). They form one connected component: \(2\) is joined to \(3\) and \(5\); \(5\) is joined to \(4\) and \(6\); and the listed edges connect all five vertices. This component is odd, so \(o(G-S)=1\). Its boundary consists of \(12,13,14\), hence has size \(3\), exactly the lower bound in the lemma. A perfect matching is \(\{14,25,36\}\): its edges have six distinct endpoints, which are all the vertices.
Check: Here \(3o(G-S)=3\) and \(3|S|=3\), so the boundary-count inequality is tight. The three matching edges cover \(1,4,2,5,3,6\), with no repeated vertex.
Worked Example: The Cube Graph
Let \(G\) have vertex set \(\{000,001,010,011,100,101,110,111\}\), and join two vertices by an edge exactly when their binary strings differ in one position. Each string has three choices of position to change, so \(G\) is cubic. It is bridgeless: for any edge, changing a different position at each endpoint gives a four-cycle containing that edge. The four edges \(\{000,100\},\{001,101\},\{010,110\},\{011,111\}\) form a perfect matching. Each pair differs in the first position, and the eight endpoints are all distinct.
For a boundary-count check, take \(S=\{000\}\). The remaining vertices are connected: each of \(001,010,100\) is adjacent to a vertex among \(011,101,110\), and these latter vertices are joined to one another through such edges. More explicitly, the remaining graph contains the cycle \(001,011,010,110,100,101,001\), which visits all six of those vertices, and the remaining vertex \(111\) is adjacent to \(011,101,110\). Thus \(G-S\) has one component of order \(7\), so \(o(G-S)=1\). Its boundary edges are \(000\!-\!001\), \(000\!-\!010\), and \(000\!-\!100\), giving \(|\partial C|=3\).
Check: The component order is \(7\), which is odd, and \(3o(G-S)=3=3|S|\). The four listed matching edges cover all eight vertices exactly once.
Why the Bridge Hypothesis Matters
The proof relies on two separate facts. Cubicity gives the parity equation \(3|V(C)|=2|E(G[V(C)])|+|\partial C|\), forcing the boundary of an odd component to have odd size. Bridgelessness rules out the only smaller positive odd possibility, namely a boundary of size \(1\). Together they give the lower bound \(3\), which matches the \(3\) incident edges available per vertex of \(S\).
A common mistake is to use only that an odd component has a nonempty boundary. That gives \(|\partial C|\ge1\), and summing would yield only \(q\le3|S|\), not Tutte’s required \(q\le|S|\). For example, in the triangular-prism calculation with \(S=\{1\}\), the one odd component has boundary size \(3\), not merely \(1\). The stronger estimate gives \(3q=3\le3|S|=3\), hence \(q\le|S|\); the weaker estimate would give only \(q=1\le3\), which does not establish the needed comparison in general.
The proof does not construct a matching edge by edge. Instead, it verifies an exact existence criterion, Tutte’s condition. This is useful in general matching theory: a local degree count and a restriction on edge cuts can certify a global pairing, even when no bipartition or direct pairing rule is available.
Check Your Understanding
Use the boundary count and the theorem’s hypotheses to answer the following.
- For an odd component \(C\) of \(G-S\) in a cubic graph, derive the parity of \(|\partial C|\) from the degree sum.
- Why does \(|\partial C|=1\) contradict bridgelessness?
- Explain why the boundaries of distinct components of \(G-S\) are disjoint sets of edges.
- In the prism example, list the three edges in the boundary of the component remaining after deleting vertex \(1\).
- What bound on \(o(G-S)\) follows if one uses only \(|\partial C|\ge1\), and why is it insufficient for Tutte’s condition?