Ch 9. Graphs
9.2 Connected Graphs
A path in a graph is a sequence of vertices and edges
[latex]P = (v_{0}, e_{1}, v_{1}, e_{2}, v_{2}, \dots, e_{k}, v_{k})[/latex]
where each edge [latex]e_{i}[/latex] connects vertex [latex]v_{i-1}[/latex] to [latex]v_{i}[/latex], and all vertices [latex]v_{i}[/latex] are in the vertex set [latex]V[/latex] of the graph [latex]G = (V, E)[/latex].
Example 9.8
In a graph with vertices [latex]A[/latex], [latex]B[/latex], [latex]C[/latex], [latex]D[/latex] and edges [latex]AB[/latex], [latex]BC[/latex], [latex]CD[/latex], the path from [latex]A[/latex] to [latex]D[/latex] is
[latex]P = (A, AB, B, BC, C, CD, D)[/latex]
An undirected graph [latex]G = (V, E)[/latex] is connected if there exists a path between every pair of distinct vertices [latex]v_{i}, v_{j} \in V[/latex].
Example 9.9
Let [latex]V = \{ A, B, C, D \}[/latex] and [latex]E = \{ AB, BC, CD \}[/latex] as in Example 9.8. Every vertex is reachable from every other vertex, so the graph is connected.
If vertex [latex]D[/latex] had no edges, the graph would be disconnected.
A subgraph [latex]G’ = (V’, E’)[/latex] of a graph [latex]G = (V, E)[/latex] is a graph such that
[latex]V’ \subseteq V[/latex]
[latex]E’ \subseteq E[/latex]
Every edge in [latex]E’[/latex] connects vertices in [latex]V’[/latex]
Example 9.10
Let [latex]G[/latex] have vertices [latex]V = \{ A, B, C, D \}[/latex] and edges [latex]E = \{ AB, BC, CD \}[/latex]. A subgraph [latex]G’[/latex] could be [latex]V’ = \{ A, B, C \}[/latex] and [latex]E’ = \{ AB, BC \}[/latex].
A component of a graph [latex]G[/latex] is a maximal connected subgraph. That is, a subgraph [latex]C = (V_{C}, E_{C})[/latex] such that [latex]C[/latex] is connected. No additional vertex or edge from [latex]G[/latex] can be added to [latex]C[/latex] without losing connectivity.
Example 9.11
Let [latex]G[/latex] have vertices [latex]V = \{ A, B, C, D, E \}[/latex] and edges [latex]E = \{ AB, BC, DE \}[/latex]. Then
Component 1 [latex]= C_{1} = \{ A, B, C \}[/latex]
Component 2 [latex]= C_{2} = \{ D, E \}[/latex]
Here are a few more definitions used when working with connected graphs. A simple path is a path in which all vertices and edges are distinct. A cycle (or circuit) is a path that starts and ends at the same vertex. A simple cycle is a cycle in which all vertices, except the start and end vertices, are distinct.
Example 9.12
Consider a graph [latex]G = (V, E)[/latex] with
[latex]V = \{ A, B, C, D, E, F \}[/latex]
[latex]E = \{ AB, BC, CD, DE, EF, FA, AC, BD \}[/latex]
The path [latex]P_{1} = A \rightarrow B \rightarrow D \rightarrow E[/latex] is a simple path.
The path [latex]P_{2} = A \rightarrow B \rightarrow C \rightarrow D \rightarrow B \rightarrow A[/latex] is a cycle that is not simple since the intermediate vertex [latex]B[/latex] is repeated.
The path [latex]P_{3} = A \rightarrow C \rightarrow D \rightarrow E \rightarrow F \rightarrow A[/latex] is a simple cycle since all intermediate vertices are distinct.
An Euler cycle (or Eulerian circuit) in a graph [latex]G = (V, E)[/latex] is a cycle that
Starts and ends at the same vertex
Traverses every edge in [latex]E[/latex] exactly once
Formally, it is a sequence
[latex](v_{0}, e_{1}, v_{1}, e_{2}, \dots, e_{m}, v_{0})[/latex]
such that [latex]E = \{ e_{1}, \dots, e_{m} \}[/latex] and each edge is used exactly once. (Euler is pronounced “Oiler”)
Example 9.13
Define a graph [latex]G = (V, E)[/latex] with
[latex]V = \{ A, B, C, D, E, F \}[/latex]
[latex]E = \{ AB, BC, CD, DE, EF, FA, AC, CE, EB, BD, AD \}[/latex]
An example of an Euler path is
[latex]A \rightarrow B \rightarrow C \rightarrow D \rightarrow E \rightarrow B \rightarrow D \rightarrow A \rightarrow C \rightarrow E \rightarrow F \rightarrow A[/latex]
This path starts with [latex]A[/latex], ends with [latex]A[/latex], and uses every edge exactly once.
The degree of a vertex [latex]v \in V[/latex] in an undirected graph [latex]G = (V, E)[/latex] is the number of edges incident to [latex]v[/latex] and is denoted [latex]\text{deg}(v)[/latex].
Example 9.14
In a graph with edges [latex]\{ AB, AC, AD \}[/latex]
[latex]\text{deg}(A) = 3[/latex]
[latex]\text{deg}(B) = \text{deg}(C) = \text{deg}(D) = 1[/latex]
In areas such as route planning and circuit design, it is often necessary to determine whether a graph contains an Euler cycle. The following theorem provides a precise and elegant criterion to achieve this.
Theorem 9.1: Euler Cycle Characterization
An undirected graph [latex]G = (V, E)[/latex] has an Euler cycle if and only if [latex]G[/latex] is connected and every vertex in [latex]G[/latex] has even degree.
Proof
We first prove the following statement: An undirected graph [latex]G = (V, E)[/latex] has an Euler cycle if
-
- [latex]G[/latex] is connected
- every vertex in [latex]G[/latex] has even degree
- Let [latex]G = (V, E)[/latex] be an undirected graph that has an Euler cycle, and for contradiction, suppose [latex]G[/latex] is not connected. Then there exists at least one vertex [latex]v \in V[/latex] that is not reachable from the starting point of the Euler cycle; but the Euler cycle must traverse every edge, and therefore must visit every vertex that is incident to an edge. If [latex]v[/latex] is unreachable, then its incident edges cannot be part of the cycle. This contradicts the assumption that the cycle includes every edge; therefore, [latex]G[/latex] must be connected.
- Now consider how the Euler cycle interacts with each vertex. Every time the cycle enters a vertex via an edge, it must also leave via another edge, except possibly at the start or end vertex. Thus, edges at each vertex are used in pairs: one to enter, one to exit. This means the degree of each vertex must be even because each traversal uses two edges per visit, and the total number of edge uses at a vertex must be visible by [latex]2[/latex]. Even for the starting or ending vertex, the cycle enters and exits once, so it still uses an even number of edges. Therefore, every vertex must have an even degree.
We next prove the converse statement: An undirected graph [latex]G = (V, E)[/latex] is connected, and every vertex in [latex]G[/latex] has even degree if [latex]G[/latex] has an Euler cycle.
We will prove this using mathematical induction (Section 3.6). Suppose [latex]G[/latex] is connected, and every vertex in [latex]G[/latex] has even degree.
Basis Step: Let [latex]G[/latex] be a cycle with [latex]3[/latex] vertices. Each vertex has degree [latex]2[/latex], and the graph is connected. The cycle itself is an Euler cycle.
Inductive Step: Assume that any connected graph with [latex]k[/latex] edges and all vertices of even degree has an Euler cycle. Let [latex]G[/latex] be a connected graph with [latex]k + 1[/latex] edges and all vertices of even degree.
Choose any vertex [latex]v \in V[/latex]. Follow a path starting at [latex]v[/latex], always choosing unused edges, until you return to [latex]v[/latex]. This is possible because each vertex has an even degree, and the path forms a cycle, which we will call [latex]C[/latex].
Now, remove the edges of [latex]C[/latex] from [latex]G[/latex], which forms a subgraph [latex]G’[/latex]. Each vertex in [latex]G’[/latex] still has an even degree, and each connected component of [latex]G’[/latex] is either empty or satisfies the inductive hypothesis. By recursively (see Section 5.4) finding Euler cycles in each component and merging them into C at shared vertices, we see that [latex]G[/latex] has an Euler cycle.
[latex]\square[/latex]
Example 9.15
Let [latex]G[/latex] be a graph with vertices [latex]V = \{ A, B, C, D, E \}[/latex] and edges [latex]E = \{ AB, BC, CD, DE, EA, AC, BD \}[/latex].
There is a path between every pair of vertices, so [latex]G[/latex] is connected. The degrees of the vertices are [latex]\text{deg}(A) = \text{deg}(B) = \text{deg}(C) = \text{deg}(D) = 3[/latex] and [latex]\text{deg}(E) = 2[/latex]. Not all vertices have even degrees, so no Euler cycle exists.
The following theorem provides a quick way to verify whether a graph is correctly constructed. If the sum of degrees doesn’t equal twice the number of edges, something is wrong: either edges are missing, or degrees are miscounted.
Theorem 9.2: Total Degree of an Undirected Graph
Let [latex]G = (V, E)[/latex] be an undirected graph. Then the sum of the degrees of all vertices in [latex]G[/latex] is equal to twice the number of edges in the graph
[latex]\Sigma_{v \in V} \text{deg}(v) = 2|E|[/latex]
Proof
Each edge in an undirected graph connects two vertices. When counting degrees, each edge contributes [latex]1[/latex] to the degree of each endpoint. Therefore, each edge contributes [latex]2[/latex] to the total degree count. Denote [latex]V = \{ v_{1}, v_{2}, \dots, v_{n} \}[/latex] as the set of vertices and [latex]E = \{ e_{1}, e_{2}, \cdots, e_{m} \}[/latex] as the set of edges. Then
[latex]\Sigma^n_{i=1} \text{deg}(v_{i}) =[/latex] Total number of edge points [latex]= 2m = 2|E|[/latex]
This holds regardless of how the edges are arranged, including loops (which contribute [latex]2[/latex] to the degree of a single vertex).
[latex]\square[/latex]
Example 6.16
Consider the graph [latex]G[/latex] with vertices [latex]V = \{ A, B, C, D \}[/latex] and edges [latex]E = \{ AB, AC, AD, BC, CD \}[/latex].
Counting the degrees gives [latex]\text{deg}(A) = 3[/latex], [latex]\text{deg}(B) = 2[/latex], [latex]\text{deg}(C) = 3[/latex], and [latex]\text{deg}(D) = 2[/latex]. The sum of degrees is [latex]10[/latex]. There are [latex]5[/latex] edges and [latex]5 \cdot 2 = 10[/latex]. The sum of the degrees equals the number of edges multiplied by [latex]2[/latex], so the graph is correctly constructed.
The following theorem is important because it provides a clear and practical criterion for determining whether a graph can be traversed in a way that uses every edge exactly once and starts and ends at different vertices. This type of traversal is called an Euler trail or Euler path.
Theorem 9.3: Existence of an Euler Trail
An undirected graph [latex]G = (V, E)[/latex] has an Euler trail that contains all edges and vertices if and only if [latex]G[/latex] is connected and exactly two vertices in [latex]G[/latex] have odd degree.
Proof
We first prove the following statement: An undirected graph [latex]G = (V, E)[/latex] has an Euler cycle that contains all edges and vertices if
-
- [latex]G[/latex] is connected
- exactly two vertices in [latex]G[/latex] have odd degree
- Suppose [latex]G[/latex] has an Euler trail and let the trail start at vertex [latex]v_{0}[/latex] and end at vertex [latex]v_{n}[/latex]. Since the trail visits every edge, the graph must be connected.
- Since the trail uses every edge exactly once, every time a vertex is visited (except the start and end), it must be entered and exited via distinct edges, which contributes [latex]2[/latex] to its degree. Therefore, all intermediate vertices must have even degree. The start and end vertices may have odd degree (one extra edge used to enter or exit). Thus, there are exactly two vertices with odd degree: the start and end.
We next prove the converse statement: An undirected graph [latex]G = (V, E)[/latex] is connected, and exactly two vertices in [latex]G[/latex] have odd degree if [latex]G[/latex] has an Euler trail.
Suppose [latex]G[/latex] is connected and has exactly two vertices in [latex]G[/latex]. Let the two vertices with odd degree be [latex]v_{0}[/latex] and [latex]v_{n}[/latex]. We construct a trail from [latex]v_{0}[/latex] to [latex]v_{n}[/latex]. Beginning at [latex]v_{0}[/latex], at each step, choose an unused edge to continue the trail. Since all other vertices have even degrees, we can always leave a vertex after entering it. The trail ends at [latex]v_{n}[/latex], where the last edge is used. This trail uses every edge exactly once and visits all vertices since the graph is connected.
[latex]\square[/latex]
Example 9.17
Let [latex]G[/latex] be a graph with vertices [latex]V = \{ A, B, C, D \}[/latex] and edges [latex]E = \{ AB, AC, AD, BC, CD \}[/latex] as in Example 9.16.
Vertices [latex]A[/latex] and [latex]C[/latex] have odd degrees, and [latex]B[/latex] and [latex]D[/latex] have even degrees. There is a path between every pair of vertices, so [latex]G[/latex] is connected.
To construct an Euler trail, start at [latex]A[/latex] which has an odd degree and follow the trail [latex]A \rightarrow B \rightarrow C \rightarrow D \rightarrow A \rightarrow C[/latex]. This ends at [latex]C[/latex] which has an odd degree, and all edges are used exactly once.
The final theorem presented in this section is important because it guarantees that even in complex or messy graphs, we can always extract a clean, non-redundant cycle, that is, a simple cycle, which is easier to analyze and work with.
Theorem 9.4
Let [latex]G = (V, E)[/latex] be an undirected graph. If [latex]G[/latex] contains a cycle, then it contains a simple cycle.
Proof
Let a cycle in [latex]G[/latex] be defined as a sequence of vertices and edges
[latex]C = (v_{0}, e_{1}, v_{1}, e_{2}, v_{2}, \cdots, e_{k}, v_{k})[/latex]
such that [latex]v_{0} = v_{k}[/latex], each edge [latex]e_{i}[/latex] connects [latex]v_{i-1}[/latex] to [latex]v_{i}[/latex], and [latex]k \geq 3[/latex]. Suppose this cycle is not simple, meaning some vertex [latex]v_{i}[/latex] appears more than once in the sequence, excluding the start and end vertices. Let [latex]v_{i}[/latex] be the first repeated vertex in the cycle, other than [latex]v_{0} = v_{k}[/latex]. Then there exists a subsequence
[latex](v_{i}, e_{i+1}, v_{i+1}, \dots, e_{j}, v_{j})[/latex]
such that [latex]v_{i} = v_{j}[/latex], and no vertex between [latex]v_{i}[/latex] and [latex]v_{j}[/latex] is repeated. This subsequence forms a simple cycle, because it starts and ends at the same vertex [latex]v_{i}[/latex], all intermediate vertices are distinct, and all edges are distinct. Thus, any cycle that is not simple contains a smaller simple cycle.
[latex]\square[/latex]
Example 9.18
Consider the graph G with vertices [latex]V = \{ A, B, C, D \}[/latex] and edges [latex]E = \{ AB, AC, AD, BC, CD \}[/latex] as in Example 9.16.
Go ahead and trace the cycle [latex]A \rightarrow B \rightarrow C \rightarrow D \rightarrow A \rightarrow C[/latex]. This cycle revisits vertex [latex]C[/latex], so it is not simple.
Now extract the simple cycle from the repeated segment to get the cycle [latex]C \rightarrow D \rightarrow A \rightarrow C[/latex]. This is a simple cycle, since it starts and ends at [latex]C[/latex], and all intermediate vertices are distinct.
Real-World Example 9.2: Urban Road Network Optimization
Consider a city’s road network represented as an undirected graph, where vertices represent intersections and edges represent roads connecting intersections.
Urban planners often face the challenge of designing efficient routes for street sweepers, snowplows, or garbage trucks. These vehicles must visit every road exactly once (to avoid redundancy), cover all intersections, and minimize fuel and time costs.
This is a classic application of Euler trails and Euler cycles. If every intersection has an even degree (i.e., an even number of roads meet), and the network is connected, then an Euler cycle exists. The vehicle can start and end at the same location.
If exactly two intersections have odd degree, and the network is connected, then an Euler trail exists. The vehicle can start at one odd-degree intersection and end at the other.
Additionally, if the network contains cycles, planners can identify simple cycles to optimize traffic flow and detect redundant routes.
To see how this network works, consider a city district with 12 intersections and 18 roads. After modelling the network as a graph, planners find that all intersections are connected and that two intersections have odd degrees. An Euler trail exists, so the street sweeper can start at one odd-degree intersection and end at the other, covering every road exactly once.
