3
$\begingroup$

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?

$\endgroup$
8
  • $\begingroup$ There are some inconsistencies in your post, like confusing edges and nodes, and uneeded repetitions. Could you please correct them? $\endgroup$ – Nathaniel Jun 6 at 9:11
  • $\begingroup$ 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. $\endgroup$ – j_random_hacker Jun 6 at 10:16
  • 1
    $\begingroup$ This site is not for time-sensitive questions. $\endgroup$ – Yuval Filmus Jun 6 at 15:33
  • $\begingroup$ 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). $\endgroup$ – Hendrik Jan Jun 7 at 14:23
  • 1
    $\begingroup$ @HendrikJan So, at most $n-2$ edges can be omitted. That is the bound given in the question. $\endgroup$ – John L. Jun 8 at 0:23
4
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ This is great! Simple and comprehensive. Thank you! $\endgroup$ – Amal Sailendran Jun 8 at 22:38
2
$\begingroup$

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

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

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.