GATE CSE 2007 | Question: 23

Question

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

Comments

Directly one can solve it.
If a vertex has degree k, its complement has n-k-1 degree. (n vertices) (result is given in Korth book exercise)
In the cyclic graph, all vertex has degree 2. C20 vertex has complement has degree 25-2-1= 22.
All degree even hence we must have euler circuit.

---

for clarification to option C:

$G \cup G^{c}=K_{n}$

$d\left(C_{25}\right)+d\left(C_{25'}\right)=d\left(K_{25}\right)$

$2+d\left(C_{25'}\right)=24$

$d\left(C_{25'}\right)=22$

$where\ d: degree$

 

---

@smsubham

bro, having even degree is necessary condition but not sufficient condition because graph should also be connected. Due to this point option A is incorrect. Please correct me if i am wrong.

Answer 1

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 Might be a Euler Cycle but we need to check graph is connected or not.

Now Question comes it is connected or not :

It is connected because, there is a theorem which says, "Let $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] (Alternate Proof: We can also prove this theorem using contradiction. Suppose we have two disconnected components, then the least component (component with minimum vertices) has to have $ \leq \frac{n}{2}$ vertices. Now we can try to maximize the degree of any vertices in the least component, which can be at most $\frac{n}{2}-1 (=\frac{n-2}{2})$, but we already know that the minimum degree is $\frac{n-1}{2}$, hence contradiction. )

Here degree of each vertex is $22$, which is, of course, greater than $\frac{25-1}{2}=12 $.

Hence, Graph must be Euler graph.

Option C

Comments

Is Euler and Eulerian one and the same thing as in graphs, circuits?

Source: Eulerian graph Euler graph

---

@vijay that is sufficient and not the necessary condition

---

Your inference is wrong I guess, first of all, Dirac’s theorem states if G is connected and degree of every vertex is at least n/2 , then it is Hamiltonian .

What's I think as follows : Since there are 25 vertices and it is cycle graph so it has 25 edges, now we can count no of edges present in complement of C-25 , which comes out to be 278, and surely it has to be connected, why because to connect 25 vertices you need atleast 24 edges , assuming of course it is undirected simple graph, and you have much more number of edges to satisfy the constraints,so it has to be connected 

Answer 2

Euler Graph-For a graph to be Euler it must have Euler Line.

Euler Line-It is a closed walk(yes closed walk and not closed path because as per definition of a path you are not allowed to re-visit a vertex) which covers all the edges of graph G.

Now since a Euler graph always has a Euler line, we have a closed walk(walk in which initial and terminal vertices are same), and all the vertices in this closed walk are of degree 2. So, needless to say, every vertex in a Euler graph must have Even degree. For one edge enters and one edge leaves this walk.

So, all in all for a graph to be Euler it must certainly have 2 conditions

(1)It must be connected. (Otherwise, you cannot form Euler Line)

(2)All vertices must have even degree.

Okay now let's check options one by one

(A)Any k-regular graph where k is an even-number:

Okay, we have one condition satisfied for Graph to be Euler but here it is not told whether the graph is connected or not?. So with surety, we cannot comment about this graph being Euler.So, this option is rejected.

(B)A complete graph on 90 vertices: This graph would have the degree of every vertex = 90-1=89 which is odd and yes the graph is connected but we don't have even degree for all vertices. So this option rejected.

(C)The complement of a cycle on 25 vertices.

The Complement of a graph G is defined as a graph G` with |V(G)|=|v(G`)|

and |E(G`)| = $\frac{n(n-1)}{2}$ - |E(G)|.

So this graph G` here would have

$\frac{25(24)}{2}-25$ edges

which evaluates to 275 edges.

Now, the degree of all vertices of this graph would be 24-2=22.

We need to check whether this graph is connected or not.

For a complete graph on n vertices, we have $\frac{(n-1)!}{2}$ distinct cycles covering all vertices.

(Ref: https://math.stackexchange.com/questions/249817/how-many-hamiltonian-cycles-are-there-in-a-complete-graph-k-n-n-geq-3-why )

So for K₂₅ we must be $\frac{24!}{2}$having  cycles from which we are removing only 1 so complement of a cycle on 25 vertices need to be connected.

Hence, the complement of a cycle on 25 vertices must be Eulerian.

Answer-(C)

Comments

I think you gave the definition for Eulerian Graph, not Euler’s Graph.

link: https://gateoverflow.in/3317/Gate-it-2008-question-27?show=331895#c331895

---

A cycle graph with 25 edges, every vertex has degree = 2
and in complete graph, every vertex has degree = 24 (i.e each vertex is connected to every other vertex)

So the degree of a vertex in complement of graph  = degree of a vertex in complete graph – degree of a vertex in cycle graph => 24 - 2 i.e 22. 

Please add this to your answer.

 

 

---

Cn+Cn’=Kn. where Kn is Complete Graph, Cn is Cycle Graph and Cn’ is Complement of Cycle Graph. N=25 so, Eech vertices having degree 24 for Kn. Cn having Degree 2.  2+Cn’=24.

Cn’=24-2=>22. it means every vertices of Cn’ is 22. and 22 is even so cn’ must be connected.

Answer 3

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  

Comments

can u provide mathematical explnation for option C .

[E] + [E (IN COMPLEMENT)]= N(N-1)/2  ,i know further not getting.

---

@Prajwal Bhat can u explain plz what does this mean "the complement of a cycle on vertices."

Answer 4

In this answer, I want to present another proof for Option C being Euler Graph.

If a vertex $u$ has degree $d$ in graph $G$ then in $\overline{G},$ $degree(u) = (n-1) – d.$

Since, every vertex in $C_n$ has degree $2$, so, degree of every vertex in $\overline{C_n}$ in $n-3.$

So, degree of every vertex in $\overline{C_{25}}$ in $22.$

Theorem :

If $C_n$ is cycle graph on $n$ vertices then $\overline{C_n}$ is connected if $n \geq 5.$

Proof :

Take any two vertices $a,b$ in $\overline{C_n}.$ We show that they will be connected by a path.

Case 1 : $a,b$ are Not adjacent in $C_n :$

In this case, $a,b$ will be adjacent in $\overline{C_n}.$ So, they are connected by a path (of length one)

Case 2 : $a,b$ are adjacent in $C_n :$

Since $n \geq 5$ and every vertex in $C_n$ has degree 2, also $a,b$ are adjacent, so, there is at least one vertex, say  $x$ which is Not adjacent to $a,b$, So, in $\overline{C_n}$, $ax,bx$ will be edges, so, we have a path between $a,b.$

Hence proved. 

---

Since, we can manually check that $\overline{C_3}$, $\overline{C_4}$ are disconencted, so, we can say the following theorem :

Theorem :

If $C_n$ is cycle graph on $n$ vertices then $\overline{C_n}$ is connected if and only if $n \geq 5.$

---

So, $\overline{C_{25}}$ is connected and has even degree for every vertex, so, it is Euler graph.

We can generalize it as follows :

Complement of a cycle on $n$ vertices has Euler Circuit if and only if $n$ is odd and $n\geq 5.$

Comments

@Deepak Poonia Sir, thank you for the proof!