Prove that Petersen Graph is not Hamiltonian

In this article, we will prove that Petersen Graph is not Hamiltonian.

Petersen Graph: A Petersen Graph is a cubic graph of 10 vertices and 15 edges. Each vertex in the Petersen Graph has degree 3. There is no 3-cycle or 4-cycle in the Petersen Graph. The most common representation is Pentagon inside another Pentagon.

Hamiltonian Graph: A Hamiltonian Graph is a graph that contains a Hamiltonian Circuit. It means there exists a cycle in the graph that visits every vertex in the graph exactly once.

Petersen Graph

Proof

We will prove that the Petersen Graph is not Hamiltonian by contradiction.

Suppose there exists a Hamiltonian Circuit in Petersen Graph.
Following is the illustration of the Hamiltonian Circuit in Petersen Graph.

Hamiltonian circuit of 10 vertices

The cycle uses 10 edges. We still have 5 edges left. We must connect the vertices using 5 edges such that each vertex has degree 3.

Consider v0 ( vertex 0 ), we cannot connect v0 and v2 as it will result in a 3-cycle, v0 – v1 – v2 – v0. We cannot connect v0 and v8 as it also results in a 3-cycle. Similarly, we cannot connect v0 – v3 and v0 – v7 as it results in a 4-cycle. Petersen Graph doesn’t have any 3-cycle or 4-cycle.

The only option we have is v4 or v5 or v6.
Suppose we connect v0 and v4.

Hamiltonian circuit of 10 vertices

Now, consider vertex v5. It is impossible to connect any vertex to v5. This is because if we connect any vertex to v5, it will result in a 3-cycle or 4-cycle.

Example,
Suppose we connect v5 and v9, it will make a 4-cycle v5 – v9 – v0 – v4 – v5.
Suppose we connect v5 and v1, it will make a 4-cycle v5 – v1 – v0 – v4 – v5.

Basically connecting any vertex to v5 will result in 3-cycle or 4-cycle which contradicts the fact that Petersen Graph does not contain any 3-cycle or 4-cycle.

Therefore, our assumption that the Petersen Graph contains a Hamiltonian circuit is contradictory.

Thus, we can say that the Petersen Graph does not contain a Hamiltonian circuit. In other words, Petersen Graph is not Hamiltonian.

References

Discrete Mathematics and Its Applications by Kenneth H. Rosen
Petersen Graph

Leave a Comment

Your email address will not be published. Required fields are marked *