New answers tagged


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 ...


If you choose a Hamiltonian cycle at random, the expected number of edges missing is strictly less than $1$.


You just need to add $n$ (where $n$ is the order of the graph) vertices with no additional edges.


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