# Discrete Mathematics: An Active Approach to Mathematical Reasoning

## Section10.2Paths and Circuits

The origin story for this section is the Konigsberg Bridge Problem, which involves seven bridges, as pictured in Figure 10.2.1. The story is that the challenge of Konigsberg was to try to traverse all the bridges, without repeating one, and return to where you started. Euler found a way to represent the problem as a graph, also pictured. The vertices are the land masses and the edges are the bridges. This representation makes it easier to try to answer the question. Before moving on, try to solve the bridge problem by finding a route through the graph that starts and ends at some vertex and traverses each edge exactly once.

### Definition10.2.2.

For each of the following terms we have a list of vertices and edges, $$v_0e_1v_1e_2\cdots e_nv_v\text{,}$$ that represent a way to traverse through the graph. So, for example, $$v_0$$ must be an endpoint of $$e_1\text{,}$$ $$v_1$$ must be an endpoint of $$e_1$$ and $$e_2\text{,}$$ etc. For each of the following terms we indicate whether we can repeat vertices and/or edges in the list.
• A walk from $$v$$ to $$w$$ has $$v=v_0, w=v_n\text{.}$$ It can repeat edges and vertices. It can begin at any vertex and end at any vertex.
• A trail from $$v$$ to $$w$$ has $$v=v_0, w=v_n\text{.}$$ It cannot repeat edges. It can begin at any vertex and end at any vertex.
• A path from $$v$$ to $$w$$ has $$v=v_0, w=v_n\text{.}$$ It cannot repeat edges or vertices. It can begin at any vertex and end at any vertex.
• A closed walk must start and end at the same vertex $$v\text{,}$$ $$v=v_0, v=v_n\text{.}$$ It can repeat edges and vertices.
• A circuit must start and end at the same vertex $$v\text{,}$$ $$v=v_0, v=v_n\text{.}$$ It cannot repeat edges. It can repeat vertices.
• A simple circuit must start and end at the same vertex $$v\text{,}$$ $$v=v_0, v=v_n\text{.}$$ It cannot repeat edges or vertices, except for the initial and terminal vertex.
If it is clear which vertices we must use, we often just use the edges, $$e_1e_2\cdots e_n\text{,}$$ to describe paths, circuits, walks, etc.
The trivial walk is just the single vertex $$v\text{.}$$ This is also the trivial circuit.
Consider the graph $$G\text{.}$$
For each list of vertices and edges, decide if it is a walk, trail, path, closed walk, circuit, simple circuit.
1. $$\displaystyle v_2e_2v_1e_5v_4e_6v_2e_2v_1$$
walk
2. $$\displaystyle v_2e_2v_1e_5v_4e_6v_2e_1v_1$$
walk, trail
3. $$\displaystyle v_2e_2v_1e_5v_4e_6v_2$$
walk, trail, closed walk, circuit, simple circuit
4. $$\displaystyle v_2e_2v_1e_5v_4e_6v_2e_1v_1$$
walk, trail
5. $$\displaystyle v_2e_2v_1e_1v_2e_3v_3e_4v_2$$
walk, trail, closed walk, circuit

### Definition10.2.5.

Two vertices, $$v, w\text{,}$$ are connected if there is a walk from $$v$$ to $$w\text{.}$$

### Definition10.2.6.

A graph, $$G\text{,}$$ is connected if given any two vertices $$v, w\text{,}$$ there is a walk from $$v$$ to $$w\text{.}$$
Basically, a graph is connected if it is in one piece. Figure 10.2.4 is an example of a connected graph. The example in Figure 10.1.3 with the isolated vertex, is an example of a graph that is not connected.
We state several propositions in this section without proof. You are encouraged to sketch examples of graphs to try to verify the propositions for yourself.

### Activity10.2.1.

Draw several examples of connected graphs. Verify for yourself that if $$G$$ is connected then any two distinct vertices of $$G$$ can be connected by a simple path.

### Activity10.2.2.

Draw several examples of graphs with a circuit. Verify for yourself that if $$v$$ and $$w$$ are part of a circuit and one edge is removed then there still exists a path from $$v$$ to $$w$$ in $$G\text{.}$$

### Activity10.2.3.

Draw several examples of connected graphs containing a nontrivial circuit. Verify for yourself that if $$G$$ is connected and contains a nontrivial circuit then an edge of the circuit can be removed without disconnecting $$G\text{.}$$

### Definition10.2.10.

An Euler circuit for a graph $$G$$ is a circuit that contains every vertex and every edge of $$G\text{.}$$
An Euler circuit must start and end at the same vertex and include every vertex and every edge. It can repeat vertices, but it cannot repeat edges. If you look back at the Konigsberg bridge problem, you can see that to solve the bridge problem is to find an Euler circuit for the associated graph. Were you able to find such a circuit?
Is it possible to find an Euler circuit for the graph in Figure 10.2.12?
Yes. For example $$e_1e_5e_2e_3e_6e_4\text{.}$$
Is it possible to find an Euler circuit for the Konigsberg bridge graph in Figure 10.2.13?
No.

### Activity10.2.4.

Draw the complete bipartite graphs $$K_{2, 3}\text{,}$$ $$K_{2, 4}\text{,}$$ $$K_{3, 3}$$ and $$K_{4, 4}\text{.}$$ Determine if each of these graphs has an Euler circuit.
We want to decide when a graph has an Euler circuit. The following two theorems completely characterize when a graph has an Euler circuit.
Although we will not prove this formally, the basic idea is that to create an Euler circuit for each vertex you need to be able to arrive at the vertex along an edge and then leave the vertex along a different edge. In the case of the inital vertex, you need to be able to leave the vertex and then return.
Theorem 10.2.14 tells us that the Konigsberg bridge graph cannot have an Euler circuit since we have vertices of odd degree.
Theorem 10.2.15 tells us that the graph in Figure 10.2.12 has an Euler circuit since all vertices have even degree, and the graph is connected. The graph in Figure 10.1.3 does not have an Euler circuit since it is not connected (although every vertex has even degree).

### Activity10.2.5.

Verify Theorem 10.2.14 and Theorem 10.2.15 on $$K_{2, 3}\text{,}$$ $$K_{2, 4}\text{,}$$ $$K_{3, 3}$$ and $$K_{4, 4}\text{.}$$

### Definition10.2.16.

An Euler path from $$v$$ to $$w$$ is a sequence of adjacent edges and vertices that starts at $$v$$ and ends at $$w$$ passing through every vertex of $$G$$ at least once and traversing every edge exactly once.
An Euler path is a path that covers every edge and vertex of $$G$$ without repeating edges.

### Activity10.2.6.

Draw a graph that has an Euler path but not an Euler circuit.
We've been focusing on traversing a graph by covering each edge exactly once, but what if we want to traverse each vertex exactly once?

### Definition10.2.18.

A Hamiltonian circuit for $$G$$ is a simple circuit that includes every vertex of $$G\text{.}$$
A Hamiltonian circuit starts and ends at the same vertex, passes through all other vertices without repeating, does not repeat edges, but does not need to use all the edges. For example, in the Konigsberg bridge graph Figure 10.2.13, we have Hamiltonian circuit $$v_1e_5v_4e_7v_3e_3v_2e_1v_1\text{.}$$

### Activity10.2.7.

Draw the complete bipartite graphs $$K_{2, 3}\text{,}$$ $$K_{2, 4}\text{,}$$ $$K_{3, 3}$$ and $$K_{4, 4}\text{.}$$ Determine if these graphs have an Hamiltonian circuit.

Use the following graph for questions about $$G\text{.}$$

#### 1.

True or false: $$v_1e_2v_3e_5v_2e_7v_2$$ is a path in $$G\text{,}$$ Figure 10.2.19.
• True.

• It repeats $$v_2\text{.}$$
• False.

• It repeats $$v_2\text{.}$$

#### 2.

True or false: $$v_1e_2v_3e_5v_2e_7v_2$$ is a closed walk in $$G\text{,}$$ Figure 10.2.19.
• True.

• It starts and ends at different vertices.
• False.

• It starts and ends at different vertices.

#### 3.

True or false: $$v_1e_2v_3e_5v_2e_7v_2e_1v_1$$ is a circuit in $$G\text{,}$$ Figure 10.2.19.
• True.

• False.

#### 4.

True or false: $$v_1e_2v_3e_5v_2e_7v_2e_1v_1$$ is a simple circuit in $$G\text{,}$$ Figure 10.2.19.
• True.

• It repeats $$v_2\text{.}$$
• False.

• It repeats $$v_2\text{.}$$

#### 5.

True or false $$v_4e_3v_2e_6v_4$$ is a simple circuit in $$G\text{,}$$ Figure 10.2.19.
• True.

• False.

#### 6.

True or false: $$G\text{,}$$ Figure 10.2.19, has an Euler circuit.
• True.

• There are vertices of odd degree.
• False.

• There are vertices of odd degree.

#### 7.

True or false: $$G\text{,}$$ Figure 10.2.19, has an Euler path.
• True.

• A path can start at $$v_1\text{,}$$ end at $$v_4\text{.}$$
• False.

• A path can start at $$v_1\text{,}$$ end at $$v_4\text{.}$$

#### 8.

True or false: $$G\text{,}$$ Figure 10.2.19, has a Hamiltonian circuit.
• True.

• For example, $$e_2e_5e_6e_4\text{.}$$
• False.

• For example, $$e_2e_5e_6e_4\text{.}$$

### ExercisesExercises

#### 1.

In the graph below, determine whether the following walks are trails, paths, closed walks, circuits, simple circuits, or just walks.
1. $$\displaystyle v_0e_1v_1e_{10}v_5e_9v_2e_2v_1$$
2. $$\displaystyle v_4e_7v_2e_9v_5e_{10}v_1e_3v_2e_9v_5$$
3. $$\displaystyle v_2$$
4. $$\displaystyle v_5v_2v_3v_4v_4v_5$$
5. $$\displaystyle v_2v_3v_4v_5v_2v_4v_3v_2$$
6. $$\displaystyle e_5e_8e_{10}e_3$$

#### 2.

Consider the following graph.
1. How many paths are there from $$v_1$$ to $$v_4\text{?}$$
2. How many trails are there from $$v_1$$ to $$v_4\text{?}$$
3. How many walks are there from $$v_1$$ to $$v_4\text{?}$$

#### 3.

Each of (a)-(c) describes a graph. In each case answer yes, no or not necessarily to whether the graph has an Euler circuit. Justify your answer.
1. $$G$$ is a connected graph with 5 vertices of degrees 2, 2, 3, 3, and 4.
2. $$G$$ is a connected graph with 5 vertices of degrees 2, 2, 4, 4, and 6.
3. $$G$$ is a graph with 5 vertices of degrees 2, 2, 4, 4, and 6.

#### 4.

Determine whether the following graph has an Euler circuit. If it does, describe it, if it doesn’t, explain why not.

#### 5.

Determine whether the following graph has an Euler circuit. If it does, describe it, if it doesn’t, explain why not.

#### 6.

Find a Hamiltonian circuit for the graph below.

#### 7.

Show that the following graph does not have a Hamiltonian circuit.

#### 8.

Give two examples of graphs that have Euler circuits but not Hamiltonian circuits. Your graphs must have a different number of edges from each other.

#### 9.

Give two examples of graphs that have Hamiltonian circuits but not Euler circuits. Your graphs must have a different number of edges from each other.