Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
What is the average degree? You could use Dirac's theorem. –  hbm Feb 26 at 0:24

3 Answers 3

up vote 1 down vote accepted

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.

share|improve this answer

To force a Hamiltonian cycle in an undirected graph on $n$ vertices would require at least $ {{n-1}\choose 2} + 2 $ edges, which is one more than the number of edges in a complete graph on $(n-1)$ vertices plus one edge connecting that graph to the $n$'th vertex.

For $n=17$ that is $122$, so unless there is a better construction of a very dense non-Hamiltonian graph, $129$ edges are more than enough. $129$ is the minimum number needed to force the applicability of Dirac's theorem but that is a stronger requirement.

Update. There is no "better construction". That $ {{n-1}\choose 2} + 1 $ is the maximum size of a non-Hamiltonian graph was proved by Ore (Arc coverings of graphs) in 1961 and uniqueness of the maximal graph was proved by Bondy (Variations on the Hamiltonian theme) in 1972. Therefore, $122$ edges are necessary and sufficient when $n=17$.

share|improve this answer

The graph is $7$ edges short from being complete so the minimum degree is $16 - 7 = 9$. Hence you can apply Dirac theorem.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.