5
$\begingroup$

It is well known that the Petersen Graph is not Hamiltonian. I can show it by case distinction, which is not too long - but it is not very elegant either.

Is there a simple (short) argument that the Petersen Graph does not contain a Hamiltonian cycle?

$\endgroup$
2
  • $\begingroup$ The case distinction can be reduced immensely if you are allowed to use the fact that the Petersen graph is 3-arc-transitive. $\endgroup$
    – Jernej
    Jan 7, 2013 at 16:04
  • $\begingroup$ how can we show it is 3 arc transitive. I proved it is enough to show it has one orbit on 3-arcs. But I am not good at combinatorics arguments so I would love a hint. $\endgroup$
    – H_B
    Feb 24, 2016 at 18:41

5 Answers 5

10
$\begingroup$

If you can use the symmetry (as Jernej suggests), the case argument has a lot going for it.

There is a proof using interlacing. Observe that if $P$ has a Hamilton cycle then its line graph $L(P)$ contains an induced copy of $C_{10}$. Eigenvalue interlacing then implies that $\theta_r(C_{10}) \le \theta_r(L(P))$. But $\theta_7(C_{10}) \approx -0.618$ and $\theta_7(L(P))=-1$. [I have forgotten who this argument is due to. There are a number of variants of it too.]

$\endgroup$
4
$\begingroup$

Motivated from the wikipedia page I will add an answer to the question by myself. It is still a little case distinction, but it is small.

We know that the Petersen graph is 3-regular and has girth 5. Suppose it has a Hamiltonian cycle $H$ and we draw the graph such that the $H$ is drawn as cycle. The edges that are not in $H$ are chords of $H$. If there would be two chords that do not intersect, then these two chords are part of two disjoint 5 cycles. But in this case the two chords and the two edges of $H$ not in the 5-cycles form a 4-cycle. Hence all chords cross pairwise. The only possibility for this is shown in the second picture. Clearly, we have a 4-cycle. Hence, we have a contradiction.

enter image description here

$\endgroup$
4
$\begingroup$

Assume there exists a Ham. cycle. Color the vertices along the cycle alternately $5$ Red and $5$ Blue. Each vertex now has at least two neighbors of the opposite color.

But starting with two adjacent vertices of the same color (must exist on a non-bipartite graph), there is only one way to complete a $2$-coloring, with at least two neighbors of the opposite color to every vertex. It turns out that $6$ vertices get one color and $4$ get the other -a contradiction.

$\endgroup$
4
$\begingroup$

Another easy argument is by using the edge chromatic number which is 4 for the Petersen graph.If it Hamiltonian, then removing the Hamiltonian cycle leaves a perfect matching. In this case 3 colors would be sufficient for edge coloring: 2 for the cycle and 1 for the matching.

$\endgroup$
3
$\begingroup$

if it had a hamiltonian circle we will find a complete matching... so if we check all 6 matching of petersen graph we can see after removing a complete matching from petersen the second graph isn't one circle. this is proving that petersen graph dosn't have a hamiltonian circle.

$\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.