New answers tagged hamiltonian-path
4
The complete digraph of $n$ nodes, $K_n$ has $n(n-1)$ edges. Describe a digraph of $n$ nodes with $n(n-1)-\delta$ edges as a digraph "with $\delta$ edges removed".
A proof by induction
The following is an outline to prove by induction that every digraph of $n$ nodes with $n-2$ edges removed contains a Hamiltonian cycle.
The base case, when $n=2$ or ...
2
If you choose a Hamiltonian cycle at random, the expected number of edges missing is strictly less than $1$.
1
You just need to add $n$ (where $n$ is the order of the graph) vertices with no additional edges.
0
Double the graph size: make two clones of the input $G_1,G_2$ and now create the (not connected) graph $\hat G$ that will consist of the two clones $G_1,G_2$. Now a half-hamiltonian path in $\hat G$ is either going through all $G_1$ or all $G_2$ (but not both, since they are not connected) and thus would be a hamiltonian path in $G$.
Top 50 recent answers are included
