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?

  • 2
    $\begingroup$ It is not true that every Hamiltonian graph with $n$ vertices has every vertex of degree $n/2$. What is true is that every graph on $n$ vertices in which every vertex has degree $n/2$ is Hamiltonian. Please study these two statements carefully to understand the difference. $\endgroup$ – Casteels Apr 16 '15 at 18:56

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$.

  • $\begingroup$ alice is wrong... i should have known not to trust her... $\endgroup$ – Paddling Ghost Apr 16 '15 at 20:22

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.