Show or refute that there can be a odd number of vertices with even degree in Graph G

Question

I am having a bit of trouble with the below question

Show or refute that there can be an odd number of vertices of even degree in an undirected Graph G.

In my opinion this is possible for a circular graph with odd number of vertices, but I am not sure how to proof that. I tried to proof that via induction, where for a graph with only one vertex and no edges the claim is true. Also when adding two vertices to the graph so that the number of vertices stays odd and also adding two edges to the graph to connect the vertices the claim is still true, since every vertex now has a degree of two, but I am not sure if that's the right inductive step.

I appreciate any help!

I know this has been on the site many times already. But meanwhile, you may want to google The Handshaking Lemma.... — Mike, Apr 11 '22 at 19:02
Simple counterexamples are your friend... like the Triangle graph $K_3$ or any other complete graph on an odd number of vertices. Now ask the same question about an odd number of vertices of odd degree... — Joffan, Apr 11 '22 at 23:26

score 1 · Answer 1 · answered Apr 11 '22 at 19:36

Any odd cycle graph (for example, $C_3$) is sufficient for an existence proof. You don't need induction. The proof is as follows: Take $G=C_3$, which has three vertices, each of degree two.

The handshaking lemma instead applies to a similar statement with the words "odd" and "even" interchanged.

Show or refute that there can be a odd number of vertices with even degree in Graph G

1 Answers1