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.
Is it true that if a graph is n-regular that it must have n+1 vertices?
1
$\begingroup$
graph-theory
-
1No, 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