I am trying to figure out if a graph can be assumed Hamiltonian or not, or if it's indeterminable with minimal information:
A graph has 17 vertices and 129 edges.
Hamiltonian graphs are proved by, as long as the vertices are greater than or equal to 3 (which this is), then if the sum of the degrees of two non-adjacent vertices is greater than or equal to the vertices (17 in this case), the graph is Hamiltonian.
To me this looks like some type of pigeonhole principle proof. I need to determine if there can exist 2 non-adjacent vertices with degrees summing to 17 or greater.
Could anyone help me figure out how to think about this?
I've gathered that each vertex must be at least of degree 1 (or else the graph would be disconnected), and that at least one vertex will have more than one degree due to the pigeonhole concept.
From there I'm unsure how to approach it.
Thanks for any help.
Edit:
Doesn't Dirac's theorem state that the vertices degree must ALL be greater than or equal to n/2, in this case, 8.5, or maybe 9?
I hadn't considered that before, but that still leaves me with the same question, how can I prove (probably with pigeonhole) that each vertex will have at least 9?
Best Answer
Dirac's theorem says that the graph is Hamiltonian if every vertex has degree at least $9$. So suppose there is a vertex $v$ with degree $8$ or less.
If the remaining $16$ vertices form a complete graph, they each have degree $15$, except for the extra $8$ vertices connected to $v$ that have degree $16$. That graph has the most edges possible while remaining non-Diracian. Then, the number of edges is half the sum of the degrees, or $\frac{1}{2} (8 + 15\cdot 8 + 16 \cdot 8) = 128$ edges.