# A 3-regular graph with fewer than 3 bridges has a perfect matching

I've been trying to learn some graph theory on my own and I've come across this statement but no proof. It is apparently called Petersen's theorem but when I looked that up for a proof, it only proves in the case of no bridgess.

I've been trying to figure out how to prove this version of the statement but I'm quite stuck. Pointers would be appreciated. I'm thinking Tutte's theorem is the way to go based on the proof for the bridgeless case but I don't see how to do it when it's not bridgeless.

Let $\mathrm{odd}(H)$ denote the number of odd components of the graph $H$.

Let $G$ be a connected cubic graph with no more than two cut-edges. Assume by way of contradiction that $G$ has no perfect matching.

Since the number of vertices of $G$ is even, if $G$ has no perfect matching then a maximum size matching in $G$ must miss at least two vertices and so, by theorem Tutte-Berge theorem, there is a subset $S$ of $V(G)$ such that $|S|\le\mathrm{odd}(G\setminus S)-2$. Each odd component of $G\setminus S$ has an odd number of vertices of odd degree and therefore each odd component of $G\setminus S$ is joined to $S$ by an odd number of edges. If this odd number is one, the corresponding edge must be a cut-edge. By our hypothesis it follows all but at most two components of $G\setminus S$ are joined to $S$ by at least three edges, hence the odd components are joined to $S$ by at least $$3(\mathrm{odd}(G\setminus S)-2)+2\ge3|S|+2$$ edges. But the number of edges in $G$ ending on vertices in $S$ is at most $3|S|$, and we have arrived at a contradiction.

Remark: The Tutte-Berge theorem asserts that the number of vertices not covered by a matching of maximum size is $\max_{S\subseteq V(G)}\{\mathrm{odd}(G\setminus S)-|S|\}$

• I hadnt seen the Tutte-Berge theorem before. Sweet result thank you for bringing it to my attention =] Commented Oct 9, 2013 at 4:32
• You can do this with just Tutte's theorem and a litle bit of care, but the above version was lying around... Commented Oct 9, 2013 at 12:00
• Even if you can its nice to see a new result like the Tutte-Berge theorem. Commented Oct 9, 2013 at 18:48
• @ChrisGodsil excuse me sir... can you please prove the part |S|≤odd(G∖S)−2 without using Tutte-Berge theorem? ( i mean isn't there a proof for this question with just Tutte theorem? ) Commented May 12, 2016 at 12:26
• @Arman Malekzade: you can, see my comment above. Commented May 12, 2016 at 17:12