1
$\begingroup$

In other words if a graph is $3$-regular does it need to have $4$ vertices? I ask because I have been asked to prove that if $n$ is an odd number and $G$ is an $n$-regular graph then $G$ must have an even number of vertices.

  • 1
    No, it's not true. Google images for "3-regular graph" shows many counterexamples. A very famous one is the Petersen graph.2012-12-05
  • 0
    @GregorBruns I bet $K_{3,3}$ is even more famous than the Petersen graph.2017-01-25

2 Answers 2