# Graph Theory – Traversability

A graph is traversable if you can draw a path between all the vertices without retracing the same path. Based on this path, there are some categories like Euler’s path and Euler’s circuit which are described in this chapter.

## Euler’s Path

An Euler’s path contains each edge of ‘G’ exactly once and each vertex of ‘G’ at least once. A connected graph G is said to be traversable if it contains an Euler’s path.

### Example

Euler’s Path = d-c-a-b-d-e.

## Euler’s Circuit

In an Euler’s path, if the starting vertex is same as its ending vertex, then it is called an Euler’s circuit.

### Example

Euler’s Path = a-b-c-d-a-g-f-e-c-a.

## Euler’s Circuit Theorem

A connected graph ‘G’ is traversable if and only if the number of vertices with odd degree in G is exactly 2 or 0. A connected graph G can contain an Euler’s path, but not an Euler’s circuit, if it has exactly two vertices with an odd degree.

Note − This Euler path begins with a vertex of odd degree and ends with the other vertex of odd degree.

### Example

Euler’s Path − b-e-a-b-d-c-a is not an Euler’s circuit, but it is an Euler’s path. Clearly it has exactly 2 odd degree vertices.

Note − In a connected graph G, if the number of vertices with odd degree = 0, then Euler’s circuit exists.

## Hamiltonian Graph

A connected graph G is said to be a Hamiltonian graph, if there exists a cycle which contains all the vertices of G.

Every cycle is a circuit but a circuit may contain multiple cycles. Such a cycle is called a Hamiltonian cycle of G.

## Hamiltonian Path

A connected graph is said to be Hamiltonian if it contains each vertex of G exactly once. Such a path is called a Hamiltonian path.

### Example

Hamiltonian Path − e-d-b-a-c.

Note −

• Euler’s circuit contains each edge of the graph exactly once.
• In a Hamiltonian cycle, some edges of the graph can be skipped.

### Example

Take a look at the following graph −

For the graph shown above −

• Euler path exists – false
• Euler circuit exists – false
• Hamiltonian cycle exists – true
• Hamiltonian path exists – true

G has four vertices with odd degree, hence it is not traversable. By skipping the internal edges, the graph has a Hamiltonian cycle passing through all the vertices.