GATE CSE
First time here? Checkout the FAQ!
x
+15 votes
1.5k views

Which of the following graphs has an Eulerian circuit?

  1. Any $k$-regular graph where $k$ is an even number.
  2. A complete graph on 90 vertices.
  3. The complement of a cycle on 25 vertices.
  4. None of the above
asked in Graph Theory by Veteran (64.6k points)  
edited by | 1.5k views

4 Answers

+32 votes
Best answer

A connected Graph has Euler Circuit $\iff$ all of its vertices have even degree
A connected Graph has Euler Path $\iff$ exactly 2 of its vertices have odd degree

(a) k-regular graph where k is even number. 
a k-regular graph need not be connected always. Example : The given below graph is a $2$ regular graph is not a Euler graph. This is so because there is no single walk which covers all edges.

(b) the complete graph of $90$ vertices
In such a graph every vertex will have an odd degree = 89, Hence it cannot have a Euler path/Circuit.

(c) to get degree of all vertices of the complement of cycle on 25 vertices we need to subtract the degree of a complete graph of 25 vertices with degree of vertices in the original given graph i.e. cycle on 25 vertices.

Degree of complement $= 24 - 2 = 22$. Since, every degree is Even, and it is connected also, therefore Graph has a Euler Cycle.

It is connected because, there is a theorem which says, "$G$ be a graph with $n$ vertices and if every vertex has a degree of at least $\frac{n-1}{2}$ then $G$ is connected." [check this]

Here Degree of each vertex is $22$, which is of course greater that $\frac{25-1}{2}\left (=12 \right )$.

answer = Option C

answered by Boss (5.4k points)  
edited by
one thing euler is closed walk..so start and end always at the same vertex.change this

, a Eulerian trail (or Eulerian path) is a trail in a graph which visits every edge exactly once. Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail which starts and ends on the same vertex

It is aying in your link,I am telling just that....

"An Euler path starts and ends at different vertices."this case is only in the case if the graph has two odd vertices..A special case..

"For the existence of Eulerian trails it is necessary that zero or two vertices have an odd degree; this means the Königsberg graph is not Eulerian. If there are no vertices of odd degree, all Eulerian trails are circuits. If there are exactly two vertices of odd degree, all Eulerian trails start at one of them and end at the other. A graph that has an Eulerian trail but not an Eulerian circuit is called semi-Eulerian."

from your link

 

 

In a cycle graph with 25 vertices there will be 25 edges.
In the complete graph with 25 vertices there will be 25*24/2 = 300 edges
Hence complement graph will have 300-25=275 edges

To make sure that a graph with n vertices is connected there will be more than
 (n-1)(n-2)/2 edges means at least 24*23/2 +1 = 277 edges are required to make sure that a graph with 25 vertices is connected. But our complemented graph has only 275 edges, doesn't it mean that complemented graph of 25 vertex cycle graph, may be disconnected??
@Vijay
We can check connectivity of option C using Ore's theorem, which says
"If deg $v$ + deg $w$ ≥ $n$ for every pair of distinct non-adjacent vertices v and w of G
then G is Hamiltonian."

So G is not only connected, it is hamiltonian also.

There is a one more important theorem which I mentioned in the answer itself, u can check edited answer too.
@sachin  what is the problem with vijay explanation plz tell me  i did not get where i m wrong
@Sachin is correct with his explanation! later i got it
@vijay  why ur previous explanation is wrong plz explain
@Habib,

In one of the post in facebook computer science group you explained D as correct option.
nice explanation to option "C"

At least one of the graphs G or its complement G' is connected. Both can't be disconnected at the same time.

If the cycle is connected, then obviously it's complement will be connected.

But if the cycle is not connected, then definitely it's complement will be connected according to the rule.

So in both the cases, the complement of a cycle with 25 vertices will always be connected.

+3 votes

Option is C

A) does not confirm that regular graph should be connected or not.

B)Degree of the each vertices will be 89 since it is complete graph.

C)The complement of the cycle graph with 25 graph where the degree of each vertex will be 24(even) so according to the theorem for the existence of Euler's circuit all the vertices should be of even degree  

answered by Veteran (11.9k points)  
can u provide mathematical explnation for option C .

[E] + [E (IN COMPLEMENT)]= N(N-1)/2  ,i know further not getting.
+1 vote
C option
answered by (125 points)  
–4 votes
Option A) Any k-regular graph where k is even number
answered by Junior (639 points)  
https://en.wikipedia.org/wiki/Regular_graph

Here is example of 2 Regular Graph which do not have euler circuit.
Answer:

Related questions



Top Users Sep 2017
  1. Habibkhan

    7166 Points

  2. Warrior

    2640 Points

  3. Arjun

    2574 Points

  4. rishu_darkshadow

    2520 Points

  5. A_i_$_h

    2280 Points

  6. nikunj

    1980 Points

  7. manu00x

    1846 Points

  8. makhdoom ghaya

    1770 Points

  9. Bikram

    1744 Points

  10. SiddharthMahapatra

    1718 Points


26,144 questions
33,726 answers
79,957 comments
31,116 users