I have this question:
Alice and Bob are discussing a graph that has $17$ vertices and $129$ edges. Bob argues that the graph is Hamiltonian, while Alice says that he’s wrong. Without knowing anything more about the graph, must one of them be right? If so, who and why, and if not, why not?
I figured that since $\frac{129}{17}$ is only ~$7.5$ which is the average degree and for a graph to be Hamiltonian every degree has to be at least $\frac{n}{2}$, which is $\frac{17}{2}$ ~$8.5$ that the graph cannot be Hamiltonian since there are not enough edges to satisfy the condition, but this was marked wrong. Does anyone know why?
Best Answer
The complete $K_{17}$ would have ${17\choose 2}=136$ edges. So we are missing only $7$ edges. Thus every vertex has degree at least $16-7=9>\frac{17}2$.