0
$\begingroup$

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)

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Big reputation wallet Brian!! You must be brilliant. $\endgroup$ – peeyush.cray Dec 14 '13 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$ – Brian M. Scott Dec 14 '13 at 22:39
  • $\begingroup$ ^ wish you happy long retired life sir... $\endgroup$ – anir123 Dec 17 '15 at 20:05
  • $\begingroup$ @Mahesha999: Thank you very much. $\endgroup$ – Brian M. Scott Dec 17 '15 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$ – Jon Garrick Apr 22 '17 at 7:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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