# Answer to Question #15595 in Discrete Mathematics for Sujata Roy

Question #15595

The complete graph k6 has how many different Hamiltonian circuits?

a) 6

b) 720

c) 120

d) 60

a) 6

b) 720

c) 120

d) 60

Expert's answer

1) Fix the vertex.

2) From each vertex we can go to another, so start on fix

vertex. We have 5 ways for start. Next we have 4 (5 - 1 from starting point to

this point) ways, next 3, 2, 1.

So, we have 5*4*3*2*1 circuits and 6 ways to

choose first vertex.

Answer 6*5*4*3*2*1=720 - b)

2) From each vertex we can go to another, so start on fix

vertex. We have 5 ways for start. Next we have 4 (5 - 1 from starting point to

this point) ways, next 3, 2, 1.

So, we have 5*4*3*2*1 circuits and 6 ways to

choose first vertex.

Answer 6*5*4*3*2*1=720 - b)

## Comments

## Leave a comment