# Anna and Carlos are discussing a graph with 17 vertices and 129 edges

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?

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

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.
• The graph in question has all of the edges of $K_{17}$ except for $9$. – Jorge Fernández Hidalgo Feb 24 '15 at 2:04