Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Which of the following graphs has an Eulerian circuit? a) Any k regular graph where k is an even number b) A complete graph on 90 vertices c) The complement of a cycle on 25 vertices d) None of the above

I have tried my best to solve this question, let check for option a, for whenever a graph in all vertices have even degrees, it will simply have an Eulerian circuit.

Since, in k-regular graph, every vertex has has exactly k degrees and if k is even, every vertex in the graph has even degrees, but k -regular graph need not to be connected, hence k-regular graph may not contain Eulerian circuit. But I have tried my best to draw a k regular graph which is disconnected, but not able to do so.

For b, because every vertex has degree 89, so it does not contain Eulerian circuit.

For c, the complement of a cycle on 25 vertices will contain each vertices with degree 22, so it must contain Eulerian circuit.

Please support for option a)

share|cite|improve this question
up vote 1 down vote accepted

Here is a $2$-regular graph that is not connected:

             o---o   o---o  
             |   |   |   |  
             o---o   o---o

Your reasoning about (b) and (c) is correct; (c) is the only one that must have an Euler circuit.

share|cite|improve this answer
Big reputation wallet Brian!! You must be brilliant. – peeyush.cray Dec 14 '13 at 22:38
@peeyush.cray: No, but I’ve been doing mathematics for a long time, and since I’m retired, I’ve a lot of time to spend here. – Brian M. Scott Dec 14 '13 at 22:39
^ wish you happy long retired life sir... – PardonMeForMySuperPoorMaths Dec 17 '15 at 20:05
@Mahesha999: Thank you very much. – Brian M. Scott Dec 17 '15 at 21:44

Your Answer


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.