Euler, Hamiltonian Graph & Connected Component
Eulerian Graph:
A circuit in a connected graph is an Euler circuit if it contains every edge of the graph exactly once. A
connected graph with an Euler circuit is called an Euler graph or Eulerian graph.
In figure dceabc represents an Euler trail since it contains all the edges exactly once and vertex c is
repeated but start and end vertex are not the same. It is not an Euler circuit as starting and ending at the
same vertex is not possible without repeating an edge cd.
Note:
1. A non-empty connected graph G is Eulerian iff its vertex are all of even degree.
2. The connected graph contains an Euler trail but not an Euler circuit iff it has exactly 2 vertices of
odd degree.
To determine whether a graph G has an Euler circuit, we note the following points.
1. List the degree of all vertices in the graph.
2. If any value is zero, the graph is not connected and hence it can not have Euler path or Euler circuit.
3. If all the degrees are even, then G has both Euler trail and Euler circuit.
4. If exactly two vertices are odd degree, then G has Euler trail but no Euler circuit.
Example. Let G be a graph of fig. Verify that G has an Euler circuit.
Sol. We observe that G is connected all the vertices are having even degree
Thus G has a Euler circuit. By inspection, we find the Euler circuit.
CS206 Page 1
Hamiltonian Graphs:
CS206 Page 2
Hamiltonian Graphs:
A circuit in a graph G that contains each vertex in G exactly once, except for the starting and ending vertex
that appears twice is known as Hamiltonian cycle.
A graph G is called a Hamiltonian cycle if it contain a Hamiltonian cycle.
A Hamiltonian path is a simple path that contains all vertices of G where the end points may be distinct.
Note:
1. (Dirac's theorem) A simple connected graph G with vertices is Hamiltonian if for
every vertex v in G.
2. A simple connected graph with n vertices and m edges is Hamiltonian if .
CS206 Page 3
Connected Component in Graph:
CS206 Page 4
CS206 Page 5
Notes:
1. If a graph (Connected or disconnected) has exactly two vertices of odd degree, there must be a path
joining these two vertices.
2. The minimum number of edges in a connected graph with vertices is
3. The minimum number of edges in a simple graph (not necessarily connected) with vertices is
, where k is the number of connected component of the graph.
4. A simple graph with vertices and components cannot have more than edges.
CS206 Page 6