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?