Discrete Mathematics for Computer Science

Paths and Cycles 343

(b) First, observe that the edges (1, k), (k, j), (1, m), and (m, j) must be included in any
Hamiltonian cycle by condition 2. Clearly, this is impossible, because these four edges
form a cycle with a smaller total number of vertices than the number of vertices in the
graph, which contradicts condition 5. U
The next example involves a graph that is very famous, because it is a counterexample
to a number of important conjectures about the structure of cubic graphs.

Example 6.

(a) Prove that the Petersen graph shown here is non-Hamiltonian.
(b) Prove that by removing any single vertex and its incident edges, the resulting graph is
Hamiltonian.

6

5 10 2

7

8

4 3

Petersen graph.

Solution.

(a) Suppose the Petersen graph has a Hamiltonian cycle. Two of the edges incident to
vertex 1 must be in the Hamiltonian cycle by condition 3. There are three possibilities:
i. (1, 2) and (1, 5)
ii. (1, 2) and (1, 6)
iii. (1, 6) and (1, 5)
Cases ii and iii can be dealt with using a single argument because of the symmetry of
the graph. We will show that Case i is impossible and leave the proof that Case ii is
impossible as Exercise 26 in Section 6.6.
Case i: Suppose (1, 2) and (1, 5) are contained in the Hamiltonian cycle. It follows
by condition 4 that (1, 6) can be deleted from further consideration. We must finish a
Hamiltonian cycle in the graph in Figure 6.12.

6

5 10 7 2

Figure 6.12 Start of Hamiltonian cycle.