So my question is this. My instructor says that when trying to prove that a Hamilton circuit doesn't exist, you should pick a vertex that's "easy to work with" I.E. a vertex with the least branching paths. They then said that I should show all possible cases with these branching paths/"where there isn't symmetry" to show that a Hamilton circuit doesn't exist. "What does where there isn't symmetry mean?". How can I tell how many cases I need to show to prove a Hamilton circuit doesn't exist in general?
My best guess for the graph above is. Pick vertex h. Then f-h-i isn't the same as g-h-i (obviously) so make one case starting with f-h-i and another case with g-h-i. So you need to make two cases and have both these cases show that a Hamilton circuit is impossible to construct to prove that a Hamilton circuit doesn't exist. So there are two cases in total you need to show starting from h. Am I correct? How do I know how many cases I need to show starting from a vertex? Can someone explain what "where there isn't symmetry?" means? Is it just more branching paths that go to different areas/"different looking" areas of the graph? What constitutes a case to prove the nonexistence of a Hamilton circuit in general?
Best Answer
By symmetry any two of the vertices $c,d,f,h,j$, and $l$ can be interchanged by an automorphism of the graph, as can any two of $b,e,g,i,m$, and $k$; $a$ and $n$, on the other hand, can only be exchanged for each other, so I’d start with one of them, say $a$.
Any Hamilton circuit through $a$ must use exactly two of the edges $ab,ag$, and $am$, and the symmetry of the graph means that it doesn’t matter which two we consider: the three diamonds are interchangeable. Suppose, then, that we have a Hamilton circuit that includes the path $mab$. In order to include $g$, it must then include $hgf$. But then it must include exactly one of the edges $fi$ and $hi$, and that is impossible: if it includes $fi$, the path will have a dead end at $h$, and if it includes $hi$, the path will have a dead end at $f$. Thus, the graph has no Hamilton circuit.