Introduction: Euler and Hamiltonian Paths and Circuits

Learning Objectives

  • Determine whether a graph has an Euler path and/ or circuit
  • Use Fleury’s algorithm to find an Euler circuit
  • Add edges to a graph to create an Euler circuit if one doesn’t exist
  • Identify whether a graph has a Hamiltonian circuit or path
  • Find the optimal Hamiltonian circuit for a graph using the brute force algorithm, the nearest neighbor algorithm, and the sorted edges algorithm
  • Identify a connected graph that is a spanning tree
  • Use Kruskal’s algorithm to form a spanning tree, and a minimum cost spanning tree

In the next lesson, we will investigate specific kinds of paths through a graph called Euler paths and circuits. Euler paths are an optimal path through a graph. They are named after him because it was Euler who first defined them.

By counting the number of vertices of a graph, and their degree we can determine whether a graph has an Euler path or circuit. We will also learn another algorithm that will allow us to find an Euler circuit once we determine that a graph has one.