# Is this graph Hamiltonian?

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?

• There are some inconsistencies in your post, like confusing edges and nodes, and uneeded repetitions. Could you please correct them? – Nathaniel Jun 6 at 9:11
• I highly recommend reading Jeff Erickson's notes on induction. Yes, it's 30 pages, but induction is a key skill and I haven't seen a friendlier introduction. – j_random_hacker Jun 6 at 10:16
• This site is not for time-sensitive questions. – Yuval Filmus Jun 6 at 15:33
• I do not understand this bound. If I omit all $n-1$ outgoing edges from one of the nodes of $K_n$ then the graph no longer is Hamiltonian (if we expect a cycle in that definition). – Hendrik Jan Jun 7 at 14:23
• @HendrikJan So, at most $n-2$ edges can be omitted. That is the bound given in the question. – John L. Jun 8 at 0:23

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

• This is great! Simple and comprehensive. Thank you! – Amal Sailendran Jun 8 at 22:38

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

• $\quad$Neat!$\quad$ – John L. Jun 6 at 16:50
• That's a completely different method, using elementary probability theory. – Yuval Filmus Jun 6 at 17:49