Hamiltonian Graphs, Part I

In this previous lesson's we focused on the edges of a graph. In this one, we'll turn our attention to the vertices.

What You Should Learn The definition of Hamiltonian graphs and cycles. One of the ways graphs are categorized based on their vertices. (So far we've focused laregly on the edges.)

Graphs don't have to be limited to two dimensions.

Walks, trails, circuits, Eulerian graphs - All of these focused primarily on the edges of a graph. Specifically, how many times was each edge crossed. There's an implied connection to the vertices here: If each edge of a graph is crossed by a walk then each vertex has to be crossed also - some of them more than once even in the most retricted kinds of sequences. So what can we say about the vertices?

A graph is called Hamiltonian if it has a cycle that uses every one of the graph's vertices. A cycle that contains all the vertices of of a graph is called a Hamiltonian cycle.

Remember that a cycle has to start and stop at the same vertex and never crosses the same vertex twice. This makes a hamiltonian cycle a walk that crosses every vertex once and only once. (The picture on the bottom left is Sir William Rowan Hamilton.)

Notice that the definition doesn't say anything about the edges. In the graph to the right v₁, v₂, v₃, v₄, v₅ is a Hamiltonian cycle because it uses every vertex and only repeats the first/last one. It only uses 5 of the 8 edges but that's okay. This is what distinguishes a Hamiltonian graph from an Eulerian graph. (Remember that an Eulerian graph was one with an Eulerian circuit, i.e. one that has a walk that uses every edge exactly once and that starts/stops at the same vertex.)

This gives us the language that we need to mathematically state the Salesman's Problem: The Salesman's Problem has a solution if the associated graph is Hamiltonian.