I came up with this solution, but I'm not sure if it's right. Could you check if there is something missing?

In the Hamilton cycle, every visit to a node is only exactly one time.

Base case: $K_n$ graph when $n = 3$

$K_n = K_3$ will have three vertices of $1, 2, 3$. $K_{n+1}$

Induction hypothesis: let’s assume with $n = k$ and $p(k-1)$ is true for a graph of $K_n$, will show that $p(k - 1)!$ will also be true.

Induction steps:

o k-1 (k-1)!

o (k - 1) – 1 = (k-1)!

substitute $k$ with $(k - 1)$ every step

o (k – 1) – 1 = k – 2 = (k-1)!

o (k – 1) – 1 – 1 = k – 3 = (k-1)!

o (k – 1) – 1 – 1 – 1= k – 4 = (k-1)!

we've now proven by the principle of mathematical induction that it is true for $p(k - 1)!$ for all $n ≥ 3$.

  • $\begingroup$ The number of hamilton cycles is , strictly speaking $$\frac{(n-1)!}{2}$$ because the cycle $123$ , for example , coincides with the cycle $132$ $\endgroup$ – Peter Mar 7 '18 at 11:59

I don't think you really understand how induction works.

Your base case should show that the case for $n=3$ holds. So somehow you should show that the number of Hamiltonian cycles in $K_3$ is $(3-1)!=2!=2$.

Of course $K_3$ is just a triangle graph, so a simple cycle graph.

As noted in comments, to count $2$ cycles here implies that cycles you are talking about are distinct by ordered vertices - going one way around a cycle is different from going the other way around.

Then for the inductive step, you should make a statement for case $k$ (the hypothesis) and show that with that assumption, you can deduce the same statement for case $k+1$.

Considering $K_{k+1}$, you can form this by adding a vertex to $K_k$ and attaching it to every existing vertex. Now consider how many different ways this added vertex can be inserted into each cycle that you counted in $K_k$.


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.