# $2$-edge-connected graph has perfect matching

My question was to prove using Tutte theorem that $3$-regular graphs and $2$-edge-connected graphs have perfect matching.

For the $3$-regular-matching, i found the solution by myself, using Tutte's thorem $q(G-S)$ $\leq$ $|$S$|$, for any $S$ in $V$. ( I took a odd component, and made the sum of vertex)

But for the $2$-edge-connected graphs i can't find the connection between the Tutte relation?

Any hints/ideas for the $2$-edge-connected part?

• But it's false that any $2$-edge-connected graph has a perfect matching, e.g., consider any odd cycle. – Casteels Dec 15 '16 at 21:45
• I put the question ambigue a bit, maybe. I don't need to prove for any, just that "$a$" 2-edge-connected graph has a perfect matching. – JohnK Dec 15 '16 at 22:27
• Ok so take any even cycle. – Casteels Dec 15 '16 at 22:36
• I think maybe what you are being asked is to prove that any graph that is both $3$-regular and $2$-edge-connected has a perfect matching. (Actually it's not true that any $3$-regular graph has a perfect matching). – Casteels Dec 15 '16 at 22:38
• Yes, i think that it its. Now i realise, the connection between 3-regular and 2-edge-connected. Any example of graph, of how to use tutte theorem? – JohnK Dec 15 '16 at 22:56

## 1 Answer

Let $$G$$ be a 3-regular 2-connected graph. Take any $$S\subseteq V(G)$$. We aim to show that $$q(G-S)\leq |S|$$. Here, $$q(G-S)$$ is the number of odd components of $$G-S$$. Tutte then gives the required 1-factor. Let $$C$$ be an odd component of $$G-S$$. Consider $$\sum_{v\in V(C)}deg(v)=3|C|.$$ This sum is clearly odd, since $$|C|$$ is odd. Any edge with both endpoints in $$C$$ contributes 2 to the sum, whereas any edge with only one endpoint in $$C$$ contributes 1. As such, edges totally contained in $$C$$ must contribute only an even part of the sum. Furthermore, any edge with only one endpoint in $$C$$ must have its other endpoint in $$S$$, since $$C$$ is disconnected from the rest of $$G$$ when $$S$$ is removed. This fact combined with the fact that the edges contained totally in $$C$$ contribute only an even portion of the sum gives us that there must be an odd number of edges from $$C$$ to $$S$$.

Since $$G$$ is 2-connected, there cannot be only one edge, so each $$C$$ must have at least 3 edges to $$S$$. The total number of edges with an endpoint in $$S$$ can be at most $$3|S|$$ since $$G$$ is 3-regular. As such, $$3q(G-S)\leq 3|S|$$ which gives $$q(G-S)\leq |S|$$ Tutte's theorem gives that $$G$$ must have a 1 factor.