Hypohamiltonian graphs
- Thread starter Evedark
- Start date
D
Deleted member 4993
Guest
Please show us what you have tried and exactly where you are stuck.I need to proof that petersen graph is hypohamiltonian graph
Please follow the rules of posting in this forum, as enunciated at:
https://www.freemathhelp.com/forum/threads/read-before-posting.109846/#post-486520
Please share your work/thoughts about this assignment.
pka
Elite Member
- Joined
- Jan 29, 2005
- Messages
- 11,982
Do you know of this LINK? This topic is one of the most esoteric in all of graph theory.
I taught courses that included large sections on graph theory; yet this topic never came up.
That link has a huge collection of references for your own research. I would be greatly surprised if you find anyone on this sort of board that has worked in this area. Good Luck though.
Cubist
Senior Member
- Joined
- Oct 29, 2019
- Messages
- 1,695
I found this question quite interesting, and I think I've proved it.
The left graph seems a fairly common way to draw the Petersen graph:-
On the right is the same graph rearranged (with the nodes labelled consistently in both). Please check that I got the labelling correct (if you decide to use this in a proof)!
To prove that there's no Hamiltonian cycle in the above graphs, consider it would have to go through all nodes, including node R. In the right image there's lots of symmetry around R. So I only considered potential cycles that go through DRG (since GRA, and ARD are the same by symmetry). I then argued that nodes E and F must be in the Hamiltonian cycle, in some order, if a cycle exists. Some fairly simple arguments follow from this. Can you proceed? (Or have you already found a different approach?)
When you start to consider removing any ONE node from the graph to show that it becomes Hamiltonian, the left image provides a good argument that you only need to consider the removal of nodes A or R due to the symmetry. (Maybe there's a way of narrowing this down further, but I'm not sure). But the R case is VERY easy anyway given the right image!
The left graph seems a fairly common way to draw the Petersen graph:-
On the right is the same graph rearranged (with the nodes labelled consistently in both). Please check that I got the labelling correct (if you decide to use this in a proof)!
To prove that there's no Hamiltonian cycle in the above graphs, consider it would have to go through all nodes, including node R. In the right image there's lots of symmetry around R. So I only considered potential cycles that go through DRG (since GRA, and ARD are the same by symmetry). I then argued that nodes E and F must be in the Hamiltonian cycle, in some order, if a cycle exists. Some fairly simple arguments follow from this. Can you proceed? (Or have you already found a different approach?)
When you start to consider removing any ONE node from the graph to show that it becomes Hamiltonian, the left image provides a good argument that you only need to consider the removal of nodes A or R due to the symmetry. (Maybe there's a way of narrowing this down further, but I'm not sure). But the R case is VERY easy anyway given the right image!