Skip to main content
\(\def\d{\displaystyle} \def\course{Math 228} \newcommand{\f}[1]{\mathfrak #1} \newcommand{\s}[1]{\mathscr #1} \def\N{\mathbb N} \def\B{\mathbf{B}} \def\circleA{(-.5,0) circle (1)} \def\Z{\mathbb Z} \def\circleAlabel{(-1.5,.6) node[above]{$A$}} \def\Q{\mathbb Q} \def\circleB{(.5,0) circle (1)} \def\R{\mathbb R} \def\circleBlabel{(1.5,.6) node[above]{$B$}} \def\C{\mathbb C} \def\circleC{(0,-1) circle (1)} \def\F{\mathbb F} \def\circleClabel{(.5,-2) node[right]{$C$}} \def\A{\mathbb A} \def\twosetbox{(-2,-1.5) rectangle (2,1.5)} \def\X{\mathbb X} \def\threesetbox{(-2,-2.5) rectangle (2,1.5)} \def\E{\mathbb E} \def\O{\mathbb O} \def\U{\mathcal U} \def\pow{\mathcal P} \def\inv{^{-1}} \def\nrml{\triangleleft} \def\st{:} \def\~{\widetilde} \def\rem{\mathcal R} \def\sigalg{$\sigma$-algebra } \def\Gal{\mbox{Gal}} \def\iff{\leftrightarrow} \def\Iff{\Leftrightarrow} \def\land{\wedge} \def\And{\bigwedge} \def\entry{\entry} \def\AAnd{\d\bigwedge\mkern-18mu\bigwedge} \def\Vee{\bigvee} \def\VVee{\d\Vee\mkern-18mu\Vee} \def\imp{\rightarrow} \def\Imp{\Rightarrow} \def\Fi{\Leftarrow} \def\var{\mbox{var}} \def\Th{\mbox{Th}} \def\entry{\entry} \def\sat{\mbox{Sat}} \def\con{\mbox{Con}} \def\iffmodels{\bmodels\models} \def\dbland{\bigwedge \!\!\bigwedge} \def\dom{\mbox{dom}} \def\rng{\mbox{range}} \def\isom{\cong} \DeclareMathOperator{\wgt}{wgt} \newcommand{\vtx}[2]{node[fill,circle,inner sep=0pt, minimum size=4pt,label=#1:#2]{}} \newcommand{\va}[1]{\vtx{above}{#1}} \newcommand{\vb}[1]{\vtx{below}{#1}} \newcommand{\vr}[1]{\vtx{right}{#1}} \newcommand{\vl}[1]{\vtx{left}{#1}} \renewcommand{\v}{\vtx{above}{}} \def\circleA{(-.5,0) circle (1)} \def\circleAlabel{(-1.5,.6) node[above]{$A$}} \def\circleB{(.5,0) circle (1)} \def\circleBlabel{(1.5,.6) node[above]{$B$}} \def\circleC{(0,-1) circle (1)} \def\circleClabel{(.5,-2) node[right]{$C$}} \def\twosetbox{(-2,-1.4) rectangle (2,1.4)} \def\threesetbox{(-2.5,-2.4) rectangle (2.5,1.4)} \def\ansfilename{practice-answers} \def\shadowprops{{fill=black!50,shadow xshift=0.5ex,shadow yshift=0.5ex,path fading={circle with fuzzy edge 10 percent}}} \newcommand{\hexbox}[3]{ \def\x{-cos{30}*\r*#1+cos{30}*#2*\r*2} \def\y{-\r*#1-sin{30}*\r*#1} \draw (\x,\y) +(90:\r) -- +(30:\r) -- +(-30:\r) -- +(-90:\r) -- +(-150:\r) -- +(150:\r) -- cycle; \draw (\x,\y) node{#3}; } \renewcommand{\bar}{\overline} \newcommand{\card}[1]{\left| #1 \right|} \newcommand{\twoline}[2]{\begin{pmatrix}#1 \\ #2 \end{pmatrix}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Section4.4Euler Paths and Circuits

Investigate!35

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?

  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?

If we start at a vertex and trace along edges to get to other vertices, we create a walk through the graph. More precisely, a walk in a graph is a sequence of vertices such that every vertex in the sequence is adjacent to the vertices before and after it in the sequence. If the walk travels along every edge exactly once, then the walk is called an Euler path (or Euler walk). If, in addition, the starting and ending vertices are the same (so you trace along every edge exactly once and end up where you started), then the walk is called an Euler circuit (or Euler tour). Of course if a graph is not connected, there is no hope of finding such a path or circuit. For the rest of this section, assume all the graphs discussed are connected.

The bridges of Königsberg problem is really a question about the existence of Euler paths. There will be a route that crosses every bridge exactly once if and only if the graph below has an Euler path:

This graph is small enough that we could actually check every possible walk that does not reuse edges, and in doing so convince ourselves that there is no Euler path (let alone an Euler circuit). On small graphs which do have an Euler path, it is usually not difficult to find one. Our goal is to find a quick way to check whether a graph has an Euler path or circuit, even if the graph is quite large.

One way to guarantee that a graph does not have an Euler circuit is to include a “spike,” a vertex of degree 1.

The vertex \(a\) has degree 1, and if you try to make an Euler circuit, you see that you will get stuck at the vertex. It is a dead end. That is, unless you start there. But then there is no way to return, so there is no hope of finding an Euler circuit. There is however an Euler path. It starts at the vertex \(a\text{,}\) then loops around the triangle. You will end at the vertex of degree 3.

You run into a similar problem whenever you have a vertex of any odd degree. If you start at such a vertex, you will not be able to end there (after traversing every edge exactly once). After using one edge to leave the starting vertex, you will be left with an even number of edges emanating from the vertex. Half of these could be used for returning to the vertex, the other half for leaving. So you return, then leave. Return, then leave. The only way to use up all the edges is to use the last one by leaving the vertex. On the other hand, if you have a vertex with odd degree that you do not start a path at, then you will eventually get stuck at that vertex. The path will use pairs of edges incident to the vertex to arrive and leave again. Eventually all but one of these edges will be used up, leaving only an edge to arrive by, and none to leave again.

What all this says is that if a graph has an Euler path and two vertices with odd degree, then the Euler path must start at one of the odd degree vertices and end at the other. In such a situation, every other vertex must have an even degree since we need an equal number of edges to get to those vertices as to leave them. How could we have an Euler circuit? The graph could not have any odd degree vertex as an Euler path would have to start there or end there, but not both. Thus for a graph to have an Euler circuit, all vertices must have even degree.

The converse is also true: if all the vertices of a graph have even degree, then the graph has an Euler circuit, and if there are exactly two vertices with odd degree, the graph has an Euler path. To prove this is a little tricky, but the basic idea is that you will never get stuck because there is an “outbound” edge for every “inbound” edge at every vertex. If you try to make an Euler path and miss some edges, you will always be able to “splice in” a circuit using the edges you previously missed.

Euler Paths and Circuits

  • A graph has an Euler circuit if and only if the degree of every vertex is even.

  • A graph has an Euler path if and only if there are at most two vertices with odd degree.

Since the bridges of Königsberg graph has all four vertices with odd degree, there is no Euler path through the graph. Thus there is no way for the townspeople to cross every bridge exactly once.

SubsectionHamilton Paths

Suppose you wanted to tour Königsberg in such a way where you visit each land mass (the two islands and both banks) exactly once. This can be done. In graph theory terms, we are asking whether there is a path which visits every vertex exactly once. Such a path is called a Hamilton path (or Hamiltonian path). We could also consider Hamilton cycles, which are Hamliton paths which start and stop at the same vertex.

Example4.4.1

Determine whether the graphs below have a Hamilton path.

Solution

The graph on the left has a Hamilton path (many different ones, actually), as shown here:

The graph on the right does not have a Hamilton path. You would need to visit each of the “outside” vertices, but as soon as you visit one, you get stuck. Note that this graph does not have an Euler path, although there are graphs with Euler paths but no Hamilton paths.

It appears that finding Hamilton paths would be easier because graphs often have more edges than vertices, so there are fewer requirements to be met. However, nobody knows whether this is true. There is no known simple test for whether a graph has a Hamilton path. For small graphs this is not a problem, but as the size of the graph grows, it gets harder and harder to check wither there is a Hamilton path. In fact, this is an example of a question which as far as we know is too difficult for computers to solve; it is an example of a problem which is NP-complete.

SubsectionExercises

1

You and your friends want to tour the southwest by car. You will visit the nine states below, with the following rather odd rule: you must cross each border between neighboring states exactly once (so, for example, you must cross the Colorado-Utah border exactly once). Can you do it? If so, does it matter where you start your road trip? What fact about graph theory solves this problem?

Solution

This is a question about finding Euler paths. Draw a graph with a vertex in each state, and connect vertices if their states share a border. Exactly two vertices will have odd degree: the vertices for Nevada and Utah. Thus you must start your road trip at in one of those states and end it in the other.

2

Which of the following graphs contain an Euler path? Which contain an Euler circuit?

  1. \(K_4\)
  2. \(K_5\text{.}\)
  3. \(K_{5,7}\)
  4. \(K_{2,7}\)
  5. \(C_7\)
  6. \(P_7\)
Solution

  1. \(K_4\) does not have an Euler path or circuit.
  2. \(K_5\) has an Euler circuit (so also an Euler path).
  3. \(K_{5,7}\) does not have an Euler path or circuit.
  4. \(K_{2,7}\) has an Euler path but not an Euler circuit.
  5. \(C_7\) has an Euler circuit (it is a circuit graph!)
  6. \(P_7\) has an Euler path but no Euler circuit.
3

Edward A. Mouse has just finished his brand new house. The floor plan is shown below:

  1. Edward wants to give a tour of his new pad to a lady-mouse-friend. Is it possible for them to walk through every doorway exactly once? If so, in which rooms must they begin and end the tour? Explain.

  2. Is it possible to tour the house visiting each room exactly once (not necessarily using every doorway)? Explain.

  3. After a few mouse-years, Edward decides to remodel. He would like to add some new doors between the rooms he has. Of course, he cannot add any doors to the exterior of the house. Is it possible for each room to have an odd number of doors? Explain.

4

For which \(n\) does the graph \(K_n\) contain an Euler circuit? Explain.

Solution

When \(n\) is odd, \(K_n\) contains an Euler circuit. This is because every vertex has degree \(n-1\text{,}\) so an odd \(n\) results in all degrees being even.

5

For which \(m\) and \(n\) does the graph \(K_{m,n}\) contain an Euler path? An Euler circuit? Explain.

Solution

If both \(m\) and \(n\) are even, then \(K_{m,n}\) has an Euler circuit. When both are odd, there is no Euler path or circuit. If one is 2 and the other is odd, then there is an Euler path but not an Euler circuit.

6

For which \(n\) does \(K_n\) contain a Hamilton path? A Hamilton cycle? Explain.

Solution

All values of \(n\text{.}\) In particular, \(K_n\) contains \(C_n\) as a subgroup, which is a cycle that includes every vertex.

7

For which \(m\) and \(n\) does the graph \(K_{m,n}\) contain a Hamilton path? A Hamilton cycle? Explain.

Solution

As long as \(|m-n| \le 1\text{,}\) the graph \(K_{m,n}\) will have a Hamilton path. To have a Hamilton cycle, we must have \(m=n\text{.}\)

8

A bridge builder has come to Königsberg and would like to add bridges so that it is possible to travel over every bridge exactly once. How many bridges must be built?

Solution

If we build one bridge, we can have an Euler path. Two bridges must be built for an Euler circuit.

9

Below is a graph representing friendships between a group of students (each vertex is a student and each edge is a friendship). Is it possible for the students to sit around a round table in such a way that every student sits between two friends? What does this question have to do with paths?

Solution

We are looking for a Hamiltonian cycle, and this graph does have one:

10

  1. Suppose a graph has a Hamilton path. What is the maximum number of vertices of degree one the graph can have? Explain why your answer is correct.

  2. Find a graph which does not have a Hamilton path even though no vertex has degree one. Explain why your example works.

11

Consider the following graph:

  1. Find a Hamilton path. Can your path be extended to a Hamilton cycle?
  2. Is the graph bipartite? If so, how many vertices are in each “part”?
  3. Use your answer to part (b) to prove that the graph has no Hamilton cycle.
  4. Suppose you have a bipartite graph \(G\) in which one part has at least two more vertices than the other. Prove that \(G\) does not have a Hamilton path.