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?
Best 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.