GATE2007-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$

 

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

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.

---

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

HOW TO FIND DEGREE FOR COMPLEMENT GRAPH?

---

@Srestha @Vijay

How to find degree of complement graph ? Please explain..

---

@set2018 @Raju Kalagoni

Suppose we take a graph G which has 25 vertices, complement of graph G will contain same number of vertices but G' has all the edges which are not present in G.
So if we combine G and G' we get a complete graph of 25 edges i.e
No of edges in G + No of edges in G' = No of edges in K₂₅

Now in 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 degree of every vertex in complement of graph  =  24 - 2 i.e 22. 

---

got it..:) Thank you ....!

---

Why always complicated answers are chosen as the best answer??

---

Nice explanation!

---

@vijay for n=5 it the formula gives 6 edges but graph with 4 edges is also connected to 5 vertex. It is a one way statement

---

nice explanation @ mithlesh

---

Can we use Dirac's theorem to prove that G' is connected?

According to Dirac's thm, "If G is simple graph, with n vertices such that degree of each vertex is atleast >=n/2, than graph is hamiltonian"

.So if G ' is hamiltonian,then definitely connected.

---

Such a beautiful answer!

---

https://math.stackexchange.com/questions/130425/hamiltonian-path-detection good read to check if graph is connected or not.

---

@sunita24 

Nothings complicated in the answer if you have your basics cleared, n thats enough to understand it.

---

can anyone please clearify @tusharp @HeadShot 

A graph has euler circuit then it has also euler path ??

As mentioned for "euler circuit exactly two vertices should be odd degree" which does not satisfy ??

i read somewhere "for a graph to contain euler path it has maximum 2 odd  degree vertices"  is it correct?

 

---

How can be cycle graph be disconnected? So what is need here to prove that it is connected?? Please help I'm confuse

Answer 2

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 3

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

why are we considering cycle on n vertices with n edges only, i mean we can take more than n edges also right,

for examle if i have 25 vertices in graph, then cycle on 25 vertices can contain 26 edges also right, since it will remain a cycle!!

consider this cycle on 5 vertices

this is also a cycle , now when i take its complement,  degree of 3 vertices will be even right, but degree of 2 vertex will be odd (since max degree in a graph with 5 vertices can be 4), which violates the property of euler graph that all vertices should have the even degree(which is a necessary and sufficient condition);

therefore c also becomes false... isn't it?

---

@Gate fever-Complement of "A cycle on 25 vertices" 

I think here they clearly mean a simple cycle on 25 vertices and not more than that.

Take $K_4$(Complete graph on 4 vertices)-Can you say it "A cycle on 4 vertices"? NO.It has cycles of length 4 and cycles of length 3 also, but it a graph which contains such cycles and not a cycle on 4 vertices.

Here  a CYCLE on 25 Vertices implies they have given you the definition of what type the graph is and not what the graph contains.

Hope you got it.

---

yes , thanks

---

@Ayush Upadhyaya Sir, can explain please how 24-2 = 22 came here ? i am not getting this line-

 The degree of all vertices of this graph would be 24-2=22.

Thank you in Advance !

---

how 24-2  anyone ??

---

@Kuljeet Shan-Complete graph on 25 vertices would have degree of each vertex as 24.Now the cycle on 25 vertices would have degree of each vertex as 2.So, the complement of each vertex in the complement of a graph on 25 vertices would be 22.

---

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)

A disconnected graph can also be Euler on a condition that exactly one connected component consisting of more than one vertex (i.e. all "disconnected vertices" must be singleton).
For example, a graph G having 4 vertices: 3 forming a triangle and 1 is an isolated vertex, is a Euler graph.

Or some graph H having two isolated vertex, is also euler (remember that 0 is even. The circuit here is the "empty circuit". Since the graph has no edges, we've already passed every edge if we don't even move). 

Source: https://math.stackexchange.com/questions/1414667/is-it-possible-disconnected-graph-has-euler-circuit

Answer 4

C option

Answer 5

Option A) Any k-regular graph where k is even number

Comments

https://en.wikipedia.org/wiki/Regular_graph

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