Anna and Carlos are talking about a graph with 17 vertices and 129 edges. One of them says that it must be a Hamiltonian graph, while the other say's it's not. With no other information about the graph, is one of them right? Or is it impossible to tell with no other information? Why or why not?

  • $\begingroup$ are you sure you wrote the question correctly? $\endgroup$ – Jorge Fernández Hidalgo Feb 24 '15 at 1:42
  • $\begingroup$ Yep, basically one of them is saying that the graph is Hamiltonian, while the other says it's not. $\endgroup$ – Alex Feb 24 '15 at 1:54
  • $\begingroup$ One of them is always correct then. $\endgroup$ – Jorge Fernández Hidalgo Feb 24 '15 at 1:54

One of them must always be correct. Suppose Anna says it is Hamiltonian and Carlos says it is not. If the graph is indeed Hamiltonian then Anna right. If it is not Hamiltonian then Carlos is right.

In this case we can prove Anna is right though, in fact the graph can have as little as $122$ edges (The number was presumambly left as $129$ so it could be solved with Dirac's theorem). $K_{17}$ has $136$ edges, so at most $14$ are missing. This reduces the sum of the degrees of two vertices by at most $15$. Therefore the sum of the degrees of any two vertices is at least $32-15=17\geq 17$. Ore's theorem proves the graph is Hamiltonian.

The bound is sharp, the graph on $121$ edges that removes $15$ edges from a single vertex is not Hamiltonian.

  • $\begingroup$ I was thinking that there's not enough info to get if it's Hamiltonian or not, since there's no algorithm for determining Hamiltonian graphs (unlike Eulerian graphs). $\endgroup$ – Alex Feb 24 '15 at 1:55
  • $\begingroup$ There is no "efficient" algorithm for determining whether an arbitrary graph is hamiltonian or not. But there are various results that tell us if each vertex has a lot of edges then it must be hamiltonian. Of course only a small fraction of hamiltonian graphs satisfy those conditions. $\endgroup$ – Jorge Fernández Hidalgo Feb 24 '15 at 1:57
  • $\begingroup$ What did you mean by 9 missing edges? $\endgroup$ – Alex Feb 24 '15 at 2:02
  • $\begingroup$ The graph in question has all of the edges of $K_{17}$ except for $9$. $\endgroup$ – Jorge Fernández Hidalgo Feb 24 '15 at 2:04
  • $\begingroup$ @TheirEmperorofIceCream, isn't it 7 missing edges? $\endgroup$ – Alex Feb 24 '15 at 2:04

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.