2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ But it's false that any $2$-edge-connected graph has a perfect matching, e.g., consider any odd cycle. $\endgroup$ – Casteels Dec 15 '16 at 21:45
  • $\begingroup$ 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. $\endgroup$ – JohnK Dec 15 '16 at 22:27
  • $\begingroup$ Ok so take any even cycle. $\endgroup$ – Casteels Dec 15 '16 at 22:36
  • $\begingroup$ 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). $\endgroup$ – Casteels Dec 15 '16 at 22:38
  • $\begingroup$ 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? $\endgroup$ – JohnK Dec 15 '16 at 22:56
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.