Petersen's theorem

We show that for every cubic, bridgeless graph G = (V, E) we have that for every set U ⊆ V the number of connected components in the graph induced by V − U with an odd number of vertices is at most the cardinality of U. Then by Tutte theorem G contains a perfect matching.

Let G_i be a component with an odd number of vertices in the graph induced by the vertex set V − U. Let V_i denote the vertices of G_i and let m_i denote the number of edges of G with one vertex in V_i and one vertex in U. By a simple double counting argument we have that

${\displaystyle \sum \nolimits _{v\in V_{i}}\deg _{G}(v)=2|E_{i}|+m_{i},}$

where E_i is the set of edges of G_i with both vertices in V_i. Since

${\displaystyle \sum \nolimits _{v\in V_{i}}\deg _{G}(v)=3|V_{i}|}$

is an odd number and 2|E_i| is an even number it follows that m_i has to be an odd number. Moreover, since G is bridgeless we have that m_i ≥ 3.

Let m be the number of edges in G with one vertex in U and one vertex in the graph induced by V − U. Every component with an odd number of vertices contributes at least 3 edges to m, and these are unique, therefore, the number of such components is at most m/3. In the worst case, every edge with one vertex in U contributes to m, and therefore m ≤ 3|U|. We get

${\displaystyle |U|\geq {\frac {1}{3}}m\geq |\{{\text{components with an odd number of vertices}}\}|,}$

which shows that the condition of Tutte theorem holds.

The theorem is due to Julius Petersen, a Danish mathematician. It can be considered as one of the first results in graph theory. The theorem appears first in the 1891 article "Die Theorie der regulären graphs".[1] By today's standards Petersen's proof of the theorem is complicated. A series of simplifications of the proof culminated in the proofs by Frink (1926) and König (1936).

In modern textbooks Petersen's theorem is covered as an application of Tutte's theorem.

• In a cubic graph with a perfect matching, the edges that are not in the perfect matching form a 2-factor. By orienting the 2-factor, the edges of the perfect matching can be extended to paths of length three, say by taking the outward-oriented edges. This shows that every cubic, bridgeless graph decomposes into edge-disjoint paths of length three.[2]
• Petersen's theorem can also be applied to show that every maximal planar graph can be decomposed into a set of edge-disjoint paths of length three. In this case, the dual graph is cubic and bridgeless, so by Petersen's theorem it has a matching, which corresponds in the original graph to a pairing of adjacent triangle faces. Each pair of triangles gives a path of length three that includes the edge connecting the triangles together with two of the four remaining triangle edges.[3]
• By applying Petersen's theorem to the dual graph of a triangle mesh and connecting pairs of triangles that are not matched, one can decompose the mesh into cyclic strips of triangles. With some further transformations it can be turned into a single strip, and hence gives a method for transforming a triangle mesh such that its dual graph becomes hamiltonian.[4]