# MTH 325: Discrete Structures for Computer Science 2

## Guided Practice 13: Hamilton Paths

### Overview

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.

### Learning Objectives

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

### Resources for learning

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

### Exercises

All the exercises for this Guided Practice are found on the Google Form located at: https://goo.gl/9P2dX7

### Submission and grading

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.