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.
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.
Proof
We will prove that the Petersen Graph is not Hamiltonian by contradiction.
Suppose there exists a Hamiltonian Circuit in Petersen Graph. There are 10 vertices in the Petersen Graph. This implies that the Petersen Graph must contain a 10-cycle that visits each vertex exactly once. The following is the illustration of a 10-cycle sub-graph in the Petersen Graph.
The above sub-graph uses 10 edges. We still have 5 edges left. We should be able to join the vertices using the remaining 5 edges such that the resulting graph will be Petersen Graph.
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 contain any 3-cycle or 4-cycle.
We can connect v0 to v4 or v5 or v6.
Suppose we connect v0 and v4.
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
Nice proof