$Project Greater Ed Logo$

Paths

Discrete Mathematics Paths and Circuits Paths

Paths and Circuits Primer

Suppose you are a real-estate agent and you have a customer who wants to tour 50 one-story ranches in one weekend. Thus, you want to get through houses as quickly as possible, taking the customer through each room exactly once (i.e. without repeating a room), whenever possible. Below is a rudimentary floor plan of a house that you will be touring.

To simplify this diagram a bit, we could represent each room as a vertex in a graph, and use edges to represent doorways connecting adjacent rooms.

So, to solve your house-tour problem for this house, starting at any vertex, we need to determine if it’s possible to visit every room without repeating rooms (ignoring walking back through rooms to the exit after the tour is over). After some thought, you decide on the following route.

Therefore, this house can be (relatively) optimally toured.

Many optimization (i.e. “best way of doing something”) problems (especially with algorithms and data structures in computer science) can be reduced to this sort of a graph-theoretical “optimal path” problem. Thus, developing some theory proves useful in solving many of these problems.

Walk

Let $G$ be a graph, and let $v$ and $w$ be vertices in $V(G)$. Then a walk from $v$ to $w$ is an alternating sequence of adjacent vertices and edges, starting with $v$ and ending with $w$.

Walks are usually written in the form $$\begin{align}ve_1v_1e_2v_2e_3v_3…v_{n-1}e_nw\end{align}$$

where $e_1$ connects vertices $v$ and $v_1$, $e_2$ connects vertices $v_1$ and $v_2$, etc., all the way up through $e_n$ connecting vertices $v_{n-1}$ and $w$, where $n$ is some natural number, called/corresponding to the length of the walk (i.e. the number of edges from the starting point $v$ to the ending point $w$.

Note that walks can pass through repeated edges and/or vertices. Similarly, they can also start and end at the same place. Such a walk is called a closed walk. A walk that starts and ends at the same vertex without traversing an edge is called a trivial walk. Nothing in the definition prevents such inefficiencies. This is contrasted with the next definitions.

Path and Simple Path

Let $G$ be a graph, and let $v,w\in V(G)$. A path from $v$ to $w$ is a walk from $v$ to $w$ with no repeated edges.

A simple path from $v$ to $w$ is a path with no repeated vertices.

Since simple paths cannot have repeated vertices, they also cannot have repeated edges, nor can they start and end at the same location.

A quick Note on Connectedness

In a previous topic, we discussed examples of graphs that were, in a sense, “disconnected,” i.e. the whole graph looks like “two separate graphs” simply drawn side-by-side. The next definition makes precise the notions of connectedness and disconnectedness.

Connected Graph

A graph $G$ is said to be connected provided that for every pair of vertices $v,w\in V(G)$ there is a walk from $v$ to $w$. If a graph is not connected, then we say it is disconnected.

In teh drawing below, the graph on the left is a connected graph, whereas the graph on the right is disconnected because there is not a walk between every pair of nodes you pick.

Often we want to talk about the individual connected parts of a graph, such as the three separate parts in the graph on the right, above. The next definition makes this notion of “connected parts” of a graph precise.

Connected Component of a Graph

Let $G$ be a graph and let $H$ be a subgraph of $G$. $H$ is said to be a connected component of $G$ provided that $H$ is itself connected, and that there is no (larger) connected subgraph of $G$ that also has $H$ as a subgraph.

Intuitively, the connected components of a graph are the “largest individual connected subgraphs” of the entire graph/diagram. The connected components of the graph from the last example are circled in the image below.

A Few Examples

To illustrate the above definitions, take a look at the following graph.

(Note the following videos are intentionally without sound)

Note that the yellow indicates duplicated edges and vertices.

Note that there may be many walks (infinitely many, in most cases) between two points. The above is just one example.

Note that there are many examples of paths between $v$ and $w$ (but not infinitely many in finite graphs); the above is merely one example.

Quick Reference Table

	Repeated Vertex Allowed?	Repeated Edge Allowed?	Can Start and End at Same Point?
Walk	Yes	Yes	Yes
Path	Yes	No	Yes
Simple Path	No	No	No

Euler Paths

Suppose you are given a graph, such as the one below, and you are asked whether or not there is a way to find a path that traverses every edge exactly once. Such a path is often called an Euler(ian) Path.

To find such a path, one could start at vertex $v_1$ and follow the walk given by the sequence

$$v_1e_1v_2e_4v_3e_6v_6e_3v_2e_7v_5e_8v_3e_9v_4e_{10}v_5e_5v_6e_2v_1$$

The short video below (without sound) illustrates this path in action!

Note that not all graphs have an Euler path. The graph below is such an example

(Give the above graph to a middle school kid who thinks they’re smart and ask them to find a way to trace over all the edges sequentially without repeats. It will keep them busy for a while.)

A natural question to ask is “when do graphs have an Euler path and when can’t they?” The next theorem is remarkably powerful for answering this question.

Theorem

Let $G$ be a connected graph. $G$ has an Euler path if and only if exactly zero or two vertices have odd degree.

To sketch why this works, suppose we have a graph $G$ that has at least one vertex $v$ with odd degree and that $G$ also has an Euler path. Said path must traverse every edge in $E(G)$ exactly once (without repeats). Thus, at vertex $v$ every time we visit $v$, we take one edge toward $v$ and one edge out leaving $v$. So for $v$ to have odd degree and for us to traverse every edge exactly once, our Euler path must either start or end at $v$. But if it starts or ends at $v$, then it must end or start at some other vertex $w$, giving that vertex odd degree as well. So if we start at $v$ and end at, say, $w$, if there is another vertex $q$ of odd degree, we will not be able to traverse every edge adjacent to $q$ (because we’d either have to start or end there as well, which is impossible). So if $G$ has one vertex of odd degree, it can only have one other vertex of odd degree as well.

Now if $G$ has no vertices with odd degree and also has an Euler path, then for every vertex there is an outbound edge for every inbound edge (and vice versa), which means nothing stops us from traversing every edge in $E(G)$.

Note

It is one thing to know (by the above theorem) that a given graph has an Euler path. It is another thing altogether to find it!

$v_1e_1v_2e_{12}v_3e_5v_7e_3v_2e_{12}e_{13}$

Note that there are infinitely many answers to this. See if the explanation below matches your rationale for the answer you got!

A walk can have repeated edges. A path cannot. So we want a walk with repeated edges! Any starting point and ending point will do, and any walk length is fine. The repeated edge in the above answer is $e_{12}$.

$v_1e_2e_{10}e_3v_2e_9v_1e_8v_7$

You probably got an answer different from this. See explanation to ensure that your rationale for the answer you came up with is the same as the one given.

Paths can have repeated vertices whereas simple paths cannot. The above answer repeats the vertex $v_1$ but does not repeat any edges, ensuring that we have a path but not a simple path.

Has an Euler path!

$v_2v_4v_5v_6v_1v_3v_6v_2v_5$

There are other ways of doing this.

By the theorem above! All but the vertices $v_2$ and $v_5$ have even degree, so we have exactly two vertices with odd degree. To find a path, apply the same logic as in the proof/explanation for why the above theorem is true!

No Euler path.

More than two vertices with odd degree!

Does not have an Euler path! Go ahead and try to find one! If you do try this, you will see why you can’t find one.

The graph is not connected! Can’t apply the theorem because it applies only to connected graphs.

Previous Lesson

Back to Lesson

Next Topic