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

We know the maximum number of edges for a directed graph ${K_n}$ of n nodes would be ${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-1)^2+1}$ - (${(n-1)^2+1}$) = ${n-2}$.

Any ${G_n}$ can be created from ${𝐾_n}$ by deleting exactly ${𝑛−2}$ edges from ${𝐾_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?

Thanks

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?