I am currently taking discrete mathematics and we are learning about Graph Theory. The section on disproving the existence of Hamilton circuits from graphs seems to be quite difficult especially if the graph is complex.
So far I have found a few strategies that help. This is assuming that the graph does not have any obvious indicators that a Hamilton circuit cannot exist.
Written in a particular order.
- First draw all the edges that a graph must contain (this would normally include edges incident to vertices that are of degree 2)
- Then look for symmetry in order to narrow down the choices of what edges will be assumed
- Finally begin assuming edges and start with the edges incident to vertices with the least degree. From then on, assume with the intention of further constraining the graph in order to see if indeed a hamilton circuit does exist.
Even after all that, it is very difficult to disprove that a graph cannot have a Hamilton circuit.
Are there any more tips in disproving that Hamilton circuits exist in a given graph? It should be said that an efficient solution is required, we can obviously brute force our way to the answer but the professor will not allow such a method during the exams.
In any Hamiltonian for (f), node $a$ must have its "next" node among $\{d,e,f\}$. The same argument holds for $b$, $c$, $g$, $h$, $i$ instead of $a$. This means that the three middle row nodes play the role of next node six times - contradicting the fact that they must appear only once.
In (h), by symmetry we may assume that node $m$ is covered wlog by $gmk$. Then to $l$ is covered wlog by $kl$. Then we must have $lf$, then $fcd$ to cover $c$, then $dji$ to cover $j$, then $icb$ to cover $c$, then lastly we need both $bag$ and $bhg$ - contradiction.