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)


1 Answer 1


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.

  • $\begingroup$ Big reputation wallet Brian!! You must be brilliant. $\endgroup$ Commented Dec 14, 2013 at 22:38
  • $\begingroup$ @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. $\endgroup$ Commented Dec 14, 2013 at 22:39
  • 1
    $\begingroup$ ^ wish you happy long retired life sir... $\endgroup$
    – Mahesha999
    Commented Dec 17, 2015 at 20:05
  • $\begingroup$ @Mahesha999: Thank you very much. $\endgroup$ Commented Dec 17, 2015 at 21:44
  • $\begingroup$ @BrianM.Scott, For C). If all the vertices have degree $22$, then total number of vertices in the complement must be $23$, which implies total $253$ edges but the complement should have $275$ edges, right ? Where am I mistaken ? $\endgroup$ Commented Apr 22, 2017 at 7:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .