Investigate!

An Euler path, in a graph or multigraph, is a walk through the graph which uses every edge exactly once. An Euler circuit is an Euler path which starts and stops at the same vertex. Our goal is to find a quick way to check whether a graph (or multigraph) has an Euler path or circuit.

  1. Which of the graphs below have Euler paths? Which have Euler circuits?

    A graph with six vertices.  Four vertices form a square, with another vertex centered inside the square, and the last vertex centered above the square.  Edges connect the corners of the square, and connect each corner to the center vertex.  The top two vertices of the square is adjacent to the vertex above the square.
    A graph with five vertices: four arranged in a square with the last one at the center of the square.  Edges connect neighboring vertices of the square, and the center vertex is adjacent to each vertex of the square.
    A graph with seven vertices.  Four vertices form the corners of a square, the remaining three are in a middle row, with one to the left, one in the center, and one to the right of the square.  Edges form the sides of the square.  Each vertex in the square is adjacent to the two middle-row vertices closest to it.
    Three vertices aligned in a vertical column left of a single vertex on the right.  Edges connect the vertex on the right to each vertex on the left.  Among the vertices on the left, two arced edges connect the bottom vertex to the center vertex, and two more connect the center vertex to the top vertex.
  2. List the degrees of each vertex of the graphs above. Is there a connection between degrees and the existence of Euler paths and circuits?

  3. Is it possible for a graph with a degree 1 vertex to have an Euler circuit? If so, draw one. If not, explain why not. What about an Euler path?

  4. What if every vertex of the graph has degree 2. Is there an Euler path? An Euler circuit? Draw some graphs.

  5. Below is part of a graph. Even though you can only see some of the vertices, can you deduce whether the graph will have an Euler path or circuit?

    Three vertices.  The center vertex is adjacent to the two on either side of it.  Each vertex has three dashed edges emanating downward (to illustrate that they go somewhere, but their other endpoints are not shown).
in-context