How to prove that a graph has at least 2 degrees with an odd degree

Question

I have been given this question in my discrete mathematics course and i have no idea how to go about solving it.

Given a graph G
Following is known about G
a) G contains a cut vertex w
b) $d(w)=2$

How would I go about proving that G contains at least 2 vertices with an odd degree?

I was thinking about proof by contradiction but I am not sure.

Answer 1

Let $u$ and $v$ be the two neighbors of $w$. Suppose all vertices of $G$ are of even degree. Then $G-w$ has at least two connected components, and $u$ and $v$ lie in different components. Also as vertices of $G-w$, both $u$ and $v$ have odd degree. The component of $u$ is a graph with exactly one vertex of odd degree, which is impossible by the Handshaking Lemma.

This proves that $G$ has a vertex of odd degree. By the Handshaking Lemma, it must have at least two.

Answer 2

If a graph $G$ has a cut vertex $w$ ...

... then we remove $w$ and its stubs (aka half-edges, or edge endpoints) ...

... and observe that the vertex degrees are unchanged (except for $w$).

We note:

1. Edges in this graph go from one component to itself.
2. Edges have exactly two stubs.

Thus every component in this graph has an odd number of stubs. Thus every component has an odd-degree vertex (since the sum of even integers is even).

So there are at least $\mathrm{deg}(w) \geq 2$ odd-degree vertices in the original graph.

(Note that we didn't use the condition that $\mathrm{deg}(w)=2$, nor the Handshaking Lemma.)