Skip to main content

Section 3.2 Walking Around Graphs

Puzzle 281.

On the table rest 8 dominoes, as shown below. If you were to line them up in a single row, so that any two sides touching had matching numbers, what would the sum of the two end numbers be?

How might you use graph theory to solve the puzzle above? One thing to try would be to create a graph consisting of six vertices, one for each value that appears on the dominoes. Then connect the vertices if their numbers belong to the same domino. This seems reasonable, but then how would you represent the line of matched up dominoes the puzzle requests?

Say you start with domino \((4,6)\text{.}\) That is an edge in our graph. Next we need to place a domino with a 6 on it (or a 4, but let's say the 4 will be an endpoint). This amounts to selecting another edge, one that is incident to the vertex 6. Say we pick \((6,5)\text{.}\) The edge we must select after that will need to be incident to vertex 5. And so on.

The edges we select in the graph need to be linked up. It makes sense to think about the selection of edges as traveling through the graph, moving along edges from vertex to vertex. Let's capture this notion carefully.

Definition 3.2.1.

A walk in a graph \(G = (V,E)\) is a sequence of vertices \(v_0, v_1, v_2, \ldots, v_n\) such that \(\{v_i, v_{i+1}\} \in E\) for all \(0 \le i \lt n\text{.}\) That is, consecutive vertices in the sequence are adjacent in the graph.

A trail is a walk that does not repeat any edges. If the trail starts and ends at the same vertex (i.e., \(v_1 = v_n\)) then it is called a circuit

A path is a trail that does not repeat any vertices, except perhaps for \(v_0 = v_n\text{.}\) In the case that \(v_0 = v_n\text{,}\) the path is called a cycle.

Do these definitions capture what a walk/trail/path should mean in a graph? All three of these describe ways in which to move around in the graph, perhaps tracing along the edges without lifting up your pencil.

Note: some sources give slightly different definitions for these concepts. For example, sometimes a walk is defined as a alternating sequence of vertices and edges \(v_1e_1v_2e_2v_3\cdots e_{n-1}v_n\) with the requirement that \(v_i\) is incident to \(e_i\text{,}\) which is incident to \(v_{i+1}\text{.}\) We have not named our edges, so this definition would not make sense. Another common way to define path is as a subgraph isomorphic to \(P_n\) for some \(n\text{.}\) This is almost equivalent to our definition, except that we allow our paths to possibly be isomorphic to \(C_n\) for some \(n\) as well. Some sources use path where we use walk and use simple path where we use path.

Walks and paths are useful for considering all sorts of graph theoretic concepts. For example, you might want to find the distance between two vertices. This would be defined as the shortest path starting at one and ending at the other (where the length of a path is the number of edges in it). If you have a notion of distance, you can define the center and radius of a graph. Graphs are connected provided between any two vertices, there is a path (or equivalently, a walk).

Subsection 3.2.1 Euler paths and circuits

To solve the domino problem, as well as the Bridges of Kƶnigsberg, we need to consider walks that use every edge exactly once.

Definition 3.2.2.

A walk in a graph that uses every edge exactly once is called an Euler path. An Euler path that starts and ends at the same vertex is called an Euler circuit.

Although it is tradition, Euler path is a bad name. These should be called an Euler trail or Euler walk, since by our definitions, an Euler path is usually not a path at all. An Euler circuit is also sometimes called an Euler tour.

Activity 282.

Our goal is to find a quick way to check whether a graph (or multigraph) has an Euler path or circuit.

(a)

Which of the graphs/multigraphs below have Euler paths? Which have Euler circuits?

(b)

List the degrees of each vertex of the (multi)graphs above. Is there a connection between degrees and the existence of Euler paths and circuits?

(c)

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?

(d)

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

(e)

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?

So what does it take for a graph to have an Euler path or circuit? 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 multigraph 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.

So there is clearly a connection between the parity of vertex degrees and Euler paths and circuits. Here are two theorems the describe that connection.

Note that these theorems answer the bridges of Kƶnigsberg problem. The 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.

Subsection 3.2.2 Proofs for Euler Paths and Circuits

Let's try to prove TheoremsĀ 3.2.3 and TheoremĀ 3.2.4. Actually, we really only need to prove one of these, and the other one should follow from it.

Activity 283.

Suppose we have already proved TheoremĀ 3.2.3, that a graph has an Euler circuit if and only if every vertex has even degree. Suppose now we want to prove TheoremĀ 3.2.4, that a graph has an Euler path if and only if it has at most two odd degree vertices.

(a)

Given a graph with an Euler path, how can you get a graph that definitely has an Euler circuit? How did this affect the number of odd degree vertices?

Hint

Add something to your graph so you can ā€œfinishā€ the Euler path. Don't forget to consider the case that the start and end vertex are already adjacent.

(b)

Given a graph with at most two odd degree vertices, build a graph that has only even degree vertices. If you have an Euler circuit of your new graph, what would that Euler circuit become if you looked at your original graph?

Hint

If there are no odd degree vertices, you are done. If there are two, you could connect them with an edge, except maybe they are already adjacent. What could you do then?

(c)

What do each of the above tasks demonstrate? That is, write a proof of TheoremĀ 3.2.4 assuming TheoremĀ 3.2.3. Make sure you specify how each ā€œdirectionā€ (implication and converse) of the proof is established by the tasks above.

Good, so we only need to prove TheoremĀ 3.2.3.

Activity 284.

Which of the two implications will be easier to prove? State both implications and say specifically what it would take to prove each. Say what would be required both for doing a direct proof and a proof by contrapositive.

Activity 285.

Suppose you had a graph and were given an Euler circuit for that graph. How might you represent that Euler circuit? If you listed each edge in order, where each edge was given as a pair of vertices, how many times would each vertex appear in the list? What have you just shown?

The other direction is harder. If you know every vertex has even degree, you must now show there is an Euler circuit. One thing you could do is to give a procedure for building one. But then you must prove that this procedure is correct. We will come back to this question when we look at mathematical induction.

Subsection 3.2.3 Hamilton 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 Hamilton paths which start and stop at the same vertex.

Example 3.2.5.

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

While a complete classification for which graphs have Hamilton paths is hard, there are some simpler things we can say. The following is one example.

Activity 286.

Consider the following graph:

(a)

Find a Hamilton path. Can your path be extended to a Hamilton cycle?

(b)

Is the graph bipartite? If so, how many vertices are in each ā€œpartā€?

(c)

Use your answer to part (b) to prove that the graph has no Hamilton cycle.

(d)

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.