Saturday, 2 January 2016

Euler Paths and Euler Circuits

An Euler circuit of a graph G is a simple circuit that contains every edge of G.
A connected multigraph has an Euler circuit if and only if each of its vertices has even degree.

There are several Euler circuits in the above graph. (a,b,e,c,d,e,a) and (d,c,e,b,a,e,d) are examples. Any path that doesn’t start at ‘e’ could be an Euler circuit.


An Euler path of graph G is a simple path containing every edge of G.
A connected multigraph has an Euler path but not an Euler circuit if and only if it has exactly two vertices of odd degree.

The above graph has two vertices (a and b) of odd degree; thus, it contains an Euler path (but not an Euler circuit). (b,e,d,c,a,b,d,a) and (a,c,d,e,b,d,a,b) are examples.

0 comments:

Post a Comment

UGC NET Computer Science

Computer GK App