Proving every 3-Regular graph with no cut-edge has a 1-factor

1.8k Views Asked by At

I have the proof in my textbook, but I'm stuck on a line (or two).

Here's some context:

Let $S \subseteq V(G)$. Count the edges between $S$ and the odd components of $G-S$, $o(G-S)$. Since $G$ is 3 regular, each vertex of $S$ is incident to at most three such edges. If each odd component $H$ of $G-S$ is incident to at least 3 such edges, then $3o(G-S) \leq 3|S|$ and hence $o(G-S) \leq |S|$, as desired.

Q: I don't understand this sentence: 'If each odd component $H$ of $G-S$ is incident to at least 3 such edges, then $3o(G-S) \leq 3|S|$'. Because $H$ is incident to at at least 3 edges between $S$ and $H$, why do we $3o(G-S) \leq 3|S|$?

1

There are 1 best solutions below

2
On BEST ANSWER

Count the number of edges $N$ between $S$ and odd components in two ways. On the one hand, since the graph is $3$-regular, it is at most $3|S|$. On the other hand, if each of the $o(G-S)$ odd components is incident to at least $3$ such edges, then it is at least $3o(G-S)$. We conclude that $3o(G-S) \leq N \leq 3|S|$.