Instantly share code, notes, and snippets.

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