0

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.

Dan D
  • 213

2 Answers2

2

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.

JMoravitz
  • 79,518
0

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

Laars Helenius
  • 7,965
  • 1
  • 23
  • 35