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.

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

1 Answer 1

up vote 0 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|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

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.