Is this graph Hamiltonian?

Question

My case is a directed graph with $n$ nodes with $(n-1)^2+1$ edges. I have done the following till now.

We know that the maximum number of edges for a directed graph $K_n$ on $n$ nodes is $n(n-1)$ edges. The graph in my problem statement is $G(V,E)$ with $|V| = n$ and $|E|$ = $(n-1)^2+1$.

Now, $n(n-1) - ((n-1)^2 + 1) = n-2$, so any such graph can be obtained from $K_n$ by deleting exactly $n-2$ edges from $K_n$.

Is my approach correct till now? How can I apply induction to prove the graph is Hamiltonian? I'm new to graph theory and inductions. As such, a comprehensive simple explanation would be much appreciated.

If not induction, is there any other way to prove this?

Answer 1

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 $n=3$ is obviously correct.

Suppose $n\gt3$. Let $G$ be such a graph. There are two cases.

• There is one node with exactly one edge from it or to it removed.
  Let that node be $u$. By induction hypothesis, there is one Hamiltonian cycle for the induced subgraph of the remaining nodes. Verify that cycle can be modified to pass $u$ as well, hence becoming a Hamiltonian cycle of $G$.
• Otherwise, for each node, either no edge from it or to it are removed, or at least two edges from it or to it are removed.
  Let $v$ be a node of the former kind and $w$ be a node of the latter kind. Let $G'$ be the induced subgraph of the remaining $n-2$ nodes. Since $2(n-2)\gt n-2$ and there are $2(n-2)$ possible edges between $w$ and a node in $G'$, there must be one edge of $G'$ that is between $w$ and some node of $G'$. By induction hypothesis, $G'$ contains a Hamiltonian cycle. Verify $C$ can be modified to include that edge as well as pass $v$, becoming a Hamiltonian cycle of $G$.

Explanation of Yuval's neat answer

Consider all (directed) Hamiltonian cycles in $K_n$. What is the total number of edges in them, with duplicity counted?

• Let $f$ be the number of all Hamiltonian cycles. Since each cycle contains $n$ edges, that total number is $nf$.
• The number of times an edge appearing in those cycles is the same for each edge, thanks to symmetry. Denote it by $p$. Since there are $n(n-1)$ distinct edges, that total number is $n(n-1)p$.

We have, $$ nf = n(n-1)p,\ \ \text{ i.e., }\ \ f= (n-1)p $$

Let us remove edges from $K_n$ so as to obtain the given graph $G$. Since removing an edge affects only Hamiltonian cycles in which that edge appears, removing $n-2$ edges will affect at most $(n-2)p$ Hamiltonian cycles. Since $f=(n-1)p > (n-2)p$, at least one Hamiltonian cycle will not be affected after removing $n-2$ edges. That is, there is at least one Hamiltonian cycle in $G$. $\quad\checkmark$

Stating the explanation in terms of probability and expectation, we shall obtain Yuval's answer.

---

The only facts about Hamiltonian cycle used in this proof are that it has $n$ edges and that the concept is symmetric to each edge. We have, in fact, proved the following remarkable proposition.

Given $n\ge2$, digraph $G$ of $n$ nodes with $n-2$ edges removed and digraph $D$ of $n$ nodes with $n$ edges, $G$ must contain a subgraph that is isomorphic to $D$.

Answer 2

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