2
$\begingroup$

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 ?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – angryavian Aug 31 '14 at 22:55
  • 1
    $\begingroup$ 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. $\endgroup$ – Ross Churchley Sep 1 '14 at 5:26
  • $\begingroup$ @ross So simple, but I did not get it, thanks! $\endgroup$ – Peter Sep 1 '14 at 9:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.