Eulerian circuit


The complement of a cycle on 25 vertices. is Eulerian circuit? How?

Graph Theory & combinatorics

First we need to understand few things –

In graph theory, an Eulerian trail (or Eulerian path) is a trail in a finite 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.

Euler proved that a necessary condition for the existence of Eulerian circuits is that all vertices in the graph have an even degree .(Can you proove it,try it!!)

The cycle graph with n vertices is called Cn. The number of vertices in Cn equals the number of edges, and every vertex has degree 2; that is, every vertex has exactly two edges incident with it.

In graph theory, the complement or inverse of a graph G is a graph H on the same vertices such that two distinct vertices of H are adjacent if and only if they are not adjacent in G. That is, to generate the complement of a graph, one fills in all the missing edges required to form a complete graph, and removes all the edges that were previously there.

So degree of complement of cycle on 25 vertices = 24 - 2( connect vertices which were not connected)

Since its even,so it has Eulerian circuit.

Bonus:This is a gate question,it has a interesting part:Any k-regular graph where k is an even number need not be eulerian circuit,why?


in a cycle graph with 25 vertices there will be 25 edges.
in the complete graph with 25 vertices there will be 2524/2=300 edges
hence compliment graph will have 300-25=275 edges
to make sure that a graph with n verticesis connected there will be more than(n-1)(n-2)/2 edges means at least 24
23/2+1=277 edgesare required to make sure that a graph with 25 vertices is connected .but our complimented graph has only 275 edges.
that means a complimented graph with 25 vertex cycle graph,may be disconnected.