Let n be the number of vertices in a graph What are the rest

Let n be the number of vertices in a graph. What are the restrictions on n>3 such that G and its complement G\' can both have Euler cycles? Do all graphs with n vertices have Euler cycles?

Solution

An Eulerian cycle, also called an Eulerian circuit, Euler circuit, Eulerian tour, or Euler tour, is a trail which starts and ends at the same graph vertex. In other words, it is a graph cycle which uses each graph edge exactly once.

i.e. each vertex should have an even degree. Hence all graphs with n vertices can have Euler cyles if each vertex has degree even.Suppose that a graph has an Euler path

P

.

For every vertex

v

other than the starting and ending vertices,

the path

P

enters

v

the

same

number of times that it

leaves

v

(say

s

times).

Therefore, there are 2

s

edges having

v

as an endpoint.

Therefore, all vertices other than the two endpoints of

P must be even vertices.

The Criterion for Euler Paths

Suppose that a graph has an Euler path

P

.

For every vertex

v

other than the starting and ending vertices,

the path

P

enters

v

the

same

number of times that it

leaves

v

(say

s

times).

Therefore, there are 2s edges having v as an endpoint.

Therefore, all vertices other than the two endpoints of

P must be even vertices.

omplement 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.

As each vertex in G has even vertices, in H each vertex will be connected to other vertices. If they are even then

G\' have Euler cycles.

I