Tutte's Theorem on cubic graphs

Question

Hello I was wondering if someone could help me understand this proof. We are trying to prove a 3-regular graph with at most two cut-edges has a 1 factor. Now I am having several difficulties that I haven't been able to bridge. For example I can see how every odd component must send an odd number of edges to S but I can't see how we know that there are an even number of odd-degree vertices ( I think this is from the Handshake Lemma but not sure) and also why the total number of vertices is odd. Finally I can't see how the inequality is justified too.

Answer 1

The proof is not very clear on what these statements are referring to. Let me clarify.

Since $G$ is a cubic graph, each odd component of $G-S$ must have an odd number of edges into $S$. Indeed,

(The "indeed" is meant to indicate that the previous sentence hasn't been proved yet; we're about to prove it now. To do this, we're going to consider an odd component $G_i$ of $G-S$, and show that there is an odd number of edges from $G_i$ into $S$.)

there must be an even number of odd degree vertices,

This is true by the handshake lemma for any graph, you're right, The thing we're applying it to here in particular is an odd component $G_i$ of $G-S$. The vertex degree of a vertex $v \in V(G_i)$ is at most $3$; it starts at $3$, and decreases for each edge $v$ has to $S$.

the total number of vertices is odd,

This is true because we're looking at an odd component. $G_i$ has an odd number of vertices by assumption.

each edge going into $S$ decreases degree of one vertex by one.

in $G$, the degrees of all the vertices start at $3$. A vertex in $G_i$ has edges only to other vertices in $G_i$ and to $S$. For each edge it has to $S$, it has one fewer edge to other vertices in $G_i$ (or in other words, its degree in $G_i$ is one less).

---

To say it all differently, consider the sum $$ \sum_{v \in V(G_i)} \deg_G(v) $$ where we are summing the degrees in $G$. On one hand, $\deg_G(v) = 3$ for every $v$, so this sum simplifies to just $3|V(G_i)|$, which is an odd number. On the other hand, each edge inside $G_i$ is counted twice by the sum (one for each endpoint). Each edge between $G_i$ and $S$ is counted once. So $$ 3|V(G_i)| = \sum_{v \in V(G_i)} \deg_G(v) = 2 |E(G_i)| + |E(G_i, S)|. $$ The quantity $|E(G_i,S)|$, the number of edges from $G_i$ to $S$, is odd, because it's the difference of an odd number $3|V(G_i)|$ and an even number $2|E(G_i)|$.