0
$\begingroup$

This question already has an answer here:

Do there exist any 3-regular graphs with an odd number of vertices? I'm starting a delve into graph theory and can prove the existence of a 3-regular graph for any even number of vertices 4 or greater, but can't find any odd ones.

$\endgroup$

marked as duplicate by JMoravitz, Math1000, Harish Chandra Rajpoot, Claude Leibovici, Daniel W. Farlow Feb 29 '16 at 9:15

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

2
$\begingroup$

The following is useful:

The Handshaking Lemma:$$\sum_{v\in V} \deg(v) = 2|E|$$

Corrollary: The number of vertices of odd degree in a graph must be even.

Corrollary 2: No graph exists with an odd number of odd degree vertices.

$\endgroup$
0
$\begingroup$

An odd number of odd vertices is impossible in any graph by the Handshake Lemma.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.