# Greatest number of edges in a graph not containing a hamilton path

Inspired by the question, where the greatest number of edges in a hamiltonian graph was asked, I have a similar question, but for hamilton paths.

• How many edges can a simple undirected graph contain, if it has no hamilton path ?

It is clear that a graph can have $\binom {n-1}{2}$ edges without having a hamilton path (just take the complete graph with $n-1$ vertices and an isolated vertex). But does a graph with $\binom {n-1}{2}+1$ edges necessarily have a hamilton path ?

What if the graph has to be connected ? What is the maximum number of edges in this case ?

• Related to OP's question: are there any known thresholds in random graphs (similar to these thresholds for giant components and connectivity in the Erdős-Rényi model) for existence of a Hamilton path/circuit? – angryavian Aug 31 '14 at 22:55
• Every graph with at least $\binom{n-1}{2}+2$ edges has a Hamilton cycle. Deleting a single edge in such a graph still leaves you with a Hamilton path, so every graph with at least $\binom{n-1}{2}+1$ edges has a Hamilton path. – Ross Churchley Sep 1 '14 at 5:26
• @ross So simple, but I did not get it, thanks! – Peter Sep 1 '14 at 9:59