Number of Circuits The following tasks are intended to

Chapter 14, Problem 14.1.138

(choose chapter or problem)

Number of Circuits The following tasks are intended to help you understand the formula for finding the number of unique Hamilton circuits in a complete graph. a) Draw a complete graph with three vertices labeled A, B, and C. Assume that you are starting at vertex A and wish to move to another vertex. How many choices do you have for moving to the second vertex? Once you choose the second vertex, how many choices do you have for moving to a third vertex? Multiply the number of choices you had from vertex A by the number of choices you had from the second vertex. Compare the number you obtained with the number of Hamilton circuits found by using 1n - 12!. b) Draw a complete graph with four vertices labeled A, B, C, and D. Assume that you are starting at vertex A and wish to move to a second vertex. How many choices do you have for moving to this second vertex? Once you choose the second vertex, how many choices do you have for moving to the third vertex? Once you choose the third vertex, how many choices do you have for the fourth vertex? Multiply the number of choices you had from each vertex together. Compare the number you obtained with the number of Hamilton circuits found by using 1n - 12!.c) Repeat this process for complete graphs with five and six vertices. d) Explain why 1n - 12! gives the number of Hamilton circuits in a complete graph with n vertices.