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?
-
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
2 Answers
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.
For the proof you're trying to find, try counting the number of incidences in two different ways.
-
0I interpreted that as 'exactly', but you're right, maybe it was meant as 'at least'. Curiously, I didn't consider this, even if I used to draw two cards when someone told me to "Draw one card". – 2012-12-05
-
0@Gregor: That appears to be a misunderstanding; I don't think it was maybe meant as 'at least' – 2012-12-05
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$.
-
0OK, I removed my comments. Note though that I was only referring to the content of the third of your spoiler blocks, the one that Anthony hadn't asked about. I usually wouldn't use spoiler text in answering a question that was actually asked, but of course you're free to do that. There are various different views on how to deal with homework questions; you can read a lot about that in [this meta thread](http://meta.math.stackexchange.com/questions/4154). I wasn't taking a stand on any of that and was only specifically talking about answering questions that weren't asked. – 2012-12-05
-
0Ok, thanks again! I'll try to do my best. From my ['home site'](http://tex.stackexchange.com/) I'm used to provide as detailed answer as possible, including possibly related things. – 2012-12-05