0
$\begingroup$

I need to show that the Petersen graph minus a vertex is hamiltonian, but now all I can think about is that its vertex degrees are in $\{2,3\}$ and that the order is $n=9$ but I do not know how to continue, can you please help me? Thanks in advance.

$\endgroup$
2
$\begingroup$

The Petersen graph is vertex-transitive, since it is isomorphic to the Kneser graph $KG(5,2)$.
If we remove any vertex, we clearly have a hamiltonian cycle:

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.