Scroll to Top

Virtual Math Learning Center

Virtual Math Learning Center Texas A&M University Virtual Math Learning Center

Section 2.1 - Hamiltonian Circuits

Instructions

  • The first video below explains the concepts in this section.
  • This page also includes exercises that you should attempt to solve yourself. You can check your answers and watch the videos explaining how to solve the exercises.

Concepts

  • Definition of Hamiltonian paths and circuits
  • Method of trees for finding Hamiltonian circuits
  • Finding the lowest cost Hamiltonian circuit
  • Definition of complete graphs
  • Number of Hamiltonian circuits in complete graphs

If you would like to see more videos on the topic, click the following link and check the related videos.

Exercises

Directions: You should try to solve each problem first, and then click "Reveal Answer" to check your answer. You can click "Watch Video" if you need help with a problem.

1. Determine if the graph has a Hamiltonian path, Hamiltonian circuit, or neither. 

Hamiltonian path

If you would like to see more videos on this topic, click the following link and check the related videos.

2. Determine if the graph has a Hamiltonian path, Hamiltonian circuit, or neither.

Neither

If you would like to see more videos on this topic, click the following link and check the related videos.

3. Determine if the graph has a Hamiltonian path, Hamiltonian circuit, or neither.

Neither

If you would like to see more videos on this topic, click the following link and check the related videos.

4. Determine if the graph has a Hamiltonian path, Hamiltonian circuit, or neither.

Hamiltonian path and Hamiltonian circuit

If you would like to see more videos on this topic, click the following link and check the related videos.

5. Use the method of trees to find all Hamiltonian circuits starting at A.

ABCDEA, AEDCBA (mirror images)
ABEDCA, ACDEBA (mirror images)
 

If you would like to see more videos on this topic, click the following link and check the related videos.

6. Find the optimal Hamiltonian circuit using the method of trees. What is its total cost?

ABEDCA or ACDEBA (mirror images)
Total Cost: 17

If you would like to see more videos on this topic, click the following link and check the related videos.

7. Find the optimal Hamiltonian circuit using the method of trees. What is its total cost? 

A diamond weighted graph of vertices A through B with a loop at B

ABCDA or ADCBA (mirror images)
total cost: 12

If you would like to see more videos on this topic, click the following link and check the related videos.

8. Is the following graph complete?

A graph of a square with two diagonal edges

Yes, it is a complete graph.

If you would like to see more videos on this topic, click the following link and check the related videos.

9. Is the following graph complete?

A graph of a triangle with an extra vertex in the middle

Yes, it is a complete graph.

If you would like to see more videos on this topic, click the following link and check the related videos.

10. Is the following graph complete?

A pentagon shaped graph with no edges in the middle

No, it is not a complete graph.

If you would like to see more videos on this topic, click the following link and check the related videos.

11. Is the following graph complete?

A graph of a square two sets of edges along the border

No, it is not a complete graph.

If you would like to see more videos on this topic, click the following link and check the related videos.

12. How many Hamiltonian circuits (not counting mirror images separately) are there for a complete graph on 11 vertices?

\(\dfrac{11!}{2} = 19,958,400\)

If you would like to see more videos on this topic, click the following link and check the related videos.

13. How many Hamiltonian circuits starting at A are there for a complete graph on 8 vertices?

\(7!=5,040\)

If you would like to see more videos on this topic, click the following link and check the related videos.

14. How many Hamiltonian circuits starting at D are there for a complete graph on 8 vertices?

\(7!=5,040\)

If you would like to see more videos on this topic, click the following link and check the related videos.

15. How many Hamiltonian circuits are there for a complete graph on 9 vertices?

\(9!=362,880\)

If you would like to see more videos on this topic, click the following link and check the related videos.

16. How many Hamiltonian circuits (not counting mirror images separately) starting at B are there for a complete graph on 15 vertices?

\(\dfrac{14!}{2} = 43,589,145,600\)

If you would like to see more videos on this topic, click the following link and check the related videos.

17. How many Hamiltonian circuits (not counting mirror images separately) are there for a complete graph on 15 vertices?

\(\dfrac{15!}{2}=653,837,184,000\)

If you would like to see more videos on this topic, click the following link and check the related videos.

18. Use the brute force method (method of trees) to find all the Hamiltonian circuits (not counting mirror images separately) starting at A for a complete graph on 5 vertices.

ABCDEA
ABCEDA
ABDCEA
ABDECA
ABEDCA
ABECDA
ACBDEA
ACBEDA
ACDBEA
ACEBDA
ADBCEA
ADCBEA

If you would like to see more videos on this topic, click the following link and check the related videos.

Change the section

Prev Section Next Section Return to Course