5.2. Hamiltonian decomposition
Let us consider the restrictive version of the Traveling Salesman Problem: there are only two travel costs, 1 and ∞ (expressing the impossibility of the journey), then the question is whether or not the graph formed by the edges with travel cost 1 contains a Hamilton cycle.
It is interesting that even this very strong simplicity the TSP remains intractable. There is no effective algorithm to solve it.
If the travel cost between any two cities is the same,
then the salesman finds immediately a least expensive tour: starting from the
head office, any permutation of the cities delivers
the desired cycle.
If our salesman has been in his duty since a long time it is boring to travel always on the same road. Therefore he decides not to take the same road again while there is a road has not seen yet. Is it always possible, or he cannot keep his decision?
If we suppose
that each city is connected to each other, then the solution depends on a
possible decomposition into disjoint
cycles.
Theorem 5.10. For the complete
graph
is decomposable
into edge disjoint hamiltonian paths iff n is even.
Proof. Let us denote the
size of a graph G by .
-
First, we suppose that we have
a complete graph . Then
A Hamilton path in a graph with n
vertices has edges.
Therefore, n must be even.
-
Now, we suppose that n is even, and . We will construct
Hamilton paths.
For each vertex .
In the construction a vertex will be exactly once either a start- or an endvertex in Hamilton paths:

Figure 5.4. A complete graph K6 and its decomposition.
Using the idea followed in the previous proof, the next theorem is easy provable.
Theorem 5.11. For the complete graph
is decomposable
into edge disjoint hamiltonian cycles iff n is odd.