# Is it true that if a graph is n-regular that it must have n+1 vertices?

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 that $G$ must have an even number of vertices.

-
No, it's not true. Google images for "3-regular graph" shows many counterexamples. A very famous one is the Petersen graph. – Gregor Bruns Dec 5 '12 at 21:11

I'm not sure how much detailed answer you want. So this is a hint, and the proof itself is hidden: Consider simple graph (no parallel edges, no loops on a vector) on $n$ vertices and think how many edges from a vertex can exist. As well, what if $n=0$?

Well, if you consider the empty graph, than it is $k$-regular and has $0$ vertices, but that's another point.

--

Generally, a non-empty $k$-regular graph has to have at least $k+1$ vertices.

--

Moreover, if $k$ is odd and you don't allow loops, the number of vertices $n$ must be even. That's because for number of edges $m$ satisfies $2m=\sum_{v\in V} d(v)$ (each edge is counted on $2$ vertices) and hence $2m=kn$.

-
It seems from your last sentence that you're asking whether an $n$-regular graph must have exactly $n+1$ vertices (rather than at least $n+1$ vertices). If so, as Gregor commented, the answer is no.