Petersen's theorem

Remarks

The proof uses Tutte's theorem. It is enough to show that, for each set $S$ of vertices, the graph $G - S$ has at most $\abs{S}$ components with an odd number of vertices. If $C$ is such an odd component, the degrees in $C$ add up to $3\abs{C}$, which is odd, so an odd number of edges joins $C$ to $S$. This number is not $1$, since $G$ has no bridge, so it is at least $3$. Since at most $3\abs{S}$ edges end in $S$, there are at most $\abs{S}$ odd components. For example, the Petersen graph is cubic and bridgeless, and its five spokes form a perfect matching. The hypothesis on bridges is needed: there are cubic graphs with bridges that have no perfect matching. The theorem also holds for cubic multigraphs without bridges, with the same proof.

Going deeper

For a student

Petersen's theorem is a standard application of Tutte's theorem, by a counting argument on edges leaving odd components. Removing a perfect matching from a bridgeless cubic graph leaves a $2$-factor, a disjoint union of cycles. This is a starting point for edge colouring of cubic graphs. A cubic graph has chromatic index $3$ exactly when it has a perfect matching whose complement consists of even cycles.