Proof with induction on $n$ so that the complete graph $K_n$ has $(n-1)!$ hamilton cycle for all $n \geq 3$.

609 Views Asked by At

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

1

There are 1 best solutions below

0
On

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