In the last lesson, we learned about Euler paths, which are paths in a graph that traverse all the edges of a graph exactly once. We can ask a similar question about whether there is a path in a graph that visits each vertex exactly once. That kind of path is called a Hamilton path. This lesson focuses on developing some rules for knowing whether Hamilton paths exist in a graph. This turns out to be a much harder problem than finding Euler paths! So we will be working toward 2-3 theoretical results that give some conditions under which Hamilton paths exist.
Please note that only some of this content is discussed in your text. The rest we will develop on our own.
BASIC objectives: These are the things you should be able to do, not necessarily perfectly but with some fluency, before you come to class.
- State the definition of an Hamilton path or circuit, and determine whether a given path or circuit meets the definition.
- Find a Hamilton path or circuit in a graph if one exists, and state it as a sequence of edges.
ADVANCED objectives: These are the things that we will work on during and after class.
- State and/or prove theoretical results on the existence of Hamilton paths.
- Apply the concept of Euler paths and circuits to practical problems about paths and networks.
Reading: Read the very short sub-section in 4.4 about Hamilton paths.
Video: From Sarada Herke's YouTube channel:
- Hamilton graphs and problem set (8:28) The three problems at the end are ones we will examine in class.
All the exercises for this Guided Practice are found on the Google Form located at: https://goo.gl/9P2dX7
Please submit the Google Form linked above no later than 11:59pm EDT on the date it is due. Please see the calendar for that date.
You will receive a Pass grade on the assignment if the form is submitted on time, each exercise has an answer, and each answer represents a good-faith effort to give a correct response. Blank exercises or responses that do not show effort (such as "I don't know" or "I couldn't figure this out") will result in a No Pass grade.