Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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

2 Answers 2

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$.

share|improve this answer
    
OK, 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. I wasn't taking a stand on any of that and was only specifically talking about answering questions that weren't asked. –  joriki Dec 5 '12 at 22:28
    
Ok, thanks again! I'll try to do my best. From my 'home site' I'm used to provide as detailed answer as possible, including possibly related things. –  yo' Dec 5 '12 at 22:30

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.

share|improve this answer
    
I 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". –  Gregor Bruns Dec 5 '12 at 21:20
    
@Gregor: That appears to be a misunderstanding; I don't think it was maybe meant as 'at least' –  joriki Dec 5 '12 at 21:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.