Route inspection problem - Definition and Overview

Route inspection problem, Chinese postman problem:

In order for a graph to have a closed Eulerian path, it will certainly have to be connected. This problem is sometimes called the Chinese Postman Problem since it was first studied by the Chinese mathematician Mei Ko Kuan.

So suppose we have a connected graph G = (V, E), the following statements are equal:

1. All vertices in G have even valence (degree).
2. G consist of the edges from a disjoint union of some cycles, and the vertices from these cycles.
3. G has a Eulerian path.

1. → 2. can be shown by induction on the number of cycles.
2. → 3. can also be shown by induction on the number of cycles, and
3. → 1. should be immediate.

A semi Eulerian path (a path which is not closed but use all edges of G and all vertices of G just once) exists if and only if G is connected and exactly two vertices have non-even valence.

Hamiltonian Cycles

There is no clear way known to see if a given graph has a Hamiltonian cycle, it mostly boils down to check if it has a lot of edges.

All graphs G=(V, E) with n = |V| >= 3 have a Hamiltonian cycle if

v, u ∈ V : v != u => valence(v) + valence(u) >= n

(the valence of every two vertices which are not edge connected is more than or equal to the number of vertices in the graph).

It should, however, be noted, that this is only a condition that ensure that a Hamiltonian cycle exist, we cannot conclude the other way. For an example of a graph where this condition fails but which certainly has a Hamiltonian cycle, think of a cycle of more than 4 vertices (you can just travel around the edge, but the sum of every two non-edge-joined vertices is only 4).

External Links

• Chinese Postman Problem (http://mathworld.wolfram.com/ChinesePostmanProblem.html)