Let G be connected simple graph, where all the vertices have even degree. Prove the following formula.

Question

Let $G=(V,E)$ an undirected graph.
Let $W(G)$ be the number of connected components in $G$.

Prove

$$\forall v\in V\ \ W(G-v) \leq \frac{\deg(v)}{2}$$ Where $W(G-v)$ is the number of connected component in $G$ after removinf from the vertex $v$ it.

Answer 1

1. If a vertex $v$ is removed from a graph where every vertex has even degree, then there are precisely $d_G(v)$ odd-degree vertices.

2. However, by the Handshaking Lemma, every graph has to have an even number of odd-degree vertices. This implies that each component of $G \setminus \{v\}$ has to have an even number of the $d_G(v)$ odd-degree vertices.

3. Every component of $G \setminus \{v\}$ must have at least one of the $d_G(v)$ vertices that are adjacent to $v$ in $G$ [which now all have odd degree], and in turn, each vertex can be in only one component of $G \setminus \{v\}$.

4. So 2. and 3. together imply that each component of $G \setminus \{v\}$ must have at least two neighbours of $v$ [and that each neighbour of $G$ in $v$ is in one component of $G$].

Can you finish from here.