We were introduced to the idea of bridges, which are edges that when removed increases the number of connected components in a graph. This makes sense in that this describes what happens when we disconnect the graph. It is a bit vague though. We can prove something a bit more specific (and maybe kind of obvious).
Let $G$ be a connected graph. If $(u,v) \in E$ is a bridge, then $G - (u,v)$ (the subgraph of $G$ with only the edge $(u,v)$ deleted) has exactly two components and $u$ and $v$ are in different components.
Since $(u,v)$ is a bridge, we know that $G - (u,v)$ has at least two components. Let $X$ be the set of vertices that in the same component as $u$. Choose some vertex $x \not \in X$. Then $x$ is not in the same component as $u$. Since $G$ was connected, $G$ contained a path between $u$ and $x$ while there are no paths in $G - (u,v)$. Thus, any path from $u$ to $x$ must have contained the edge $(u,v)$. These paths must have the form $uv v_2 \cdots v_{n-1} x$.
Then $v v_2 \cdots v_{n-1} x$ is a path in $G - (u,v)$ and therefore $v$ and $x$ are in the same component. But recall that the choice of $x \not \in X$ was arbitrary. This means that there exists a path from $u$ to every vertex $x \not \in X$. Therefore, $G - (u,v)$ has two components, and $u$ and $v$ are in different components.
We can use this to get the following important characterization of bridges which is maybe not quite as obvious.
Let $G$ be a graph. An edge $e$ of $G$ is a bridge if and only if it is not contained in any cycle of $G$.
First, assume that $e = (u,v)$ is a bridge. Suppose that $e$ is in a cycle, say $u v v_2 \cdots v_{n-1} u$. Now consider $G - e$. Note that $v v_2 \cdots v_{n-1} u$ is a path between $u$ and $v$, so $u$ and $v$ are in the same component. But this contradicts Lemma 20.1. Therefore, $e$ is not in a cycle of $G$.
Now, assume that $e = (u,v)$ is not in a cycle. Suppose that $e$ is not a bridge. Then $u$ and $v$ are in the same component in the graph $G - e$. Therefore, there is a path between $u$ and $v$, say $u v_2 \cdots v_{n-1} v$. However, this means that $u v_2 \cdots v_{n-1} vu$ is a cycle in $G$, which is a contradiction. Therefore, $e$ is a bridge.
A consequence of this is the following useful result, which we won't prove in class.
Let $G = (V,E)$ be a graph and let $u,v \in V$ be vertices in $G$. If there are two distinct paths between $u$ and $v$, then $G$ contains a cycle.
Now that we've identified special kinds of edges that, in a sense, must be present in order to have a connected graph, we can ask which kinds of graphs are in a sense minimally connected. We can think of such graphs as forming the backbone of a more "full" graph. These graphs are called trees.
As computer scientists, we tend to think of trees when they're organized with the root at the top and growing downwards (apparently trees grow upside-down) as in family trees or organizational charts. However, the following definition gives us something more concrete to work with and we'll see that some results we've proven about cycles will come into play.
A graph $G$ is a tree if $G$ is connected and contains no cycles. A graph $G$ with no cycles is a forest.
The following are examples of trees.
Note that the definition of a tree is quite simple, but it has a clear connection with our discussion of bridges and connectivity. Since a tree has no cycles, this means that every edge in a tree is a bridge. In other words, removing any edge in the graph will disconnect it. This leads us to the following result.
A graph $G$ is a tree if and only if there is a unique path between any two vertices in $G$.
If we take the idea of a tree as minimally connected in another direction, then we can also conclude that adding edges will "beef up" the connectivity of the graph.
Let $T$ be a tree. Adding an edge between any two non-adjacent vertices creates a cycle.
How many edges does a "minimally connected" graph have? It turns out there is a definitive answer. First, we make an observation: trees will have many vertices of degree 1, which we call leaves. One can show that a tree has at least as many leaves as the maximum degree of the tree. However, for now, we claim something weaker: a tree that's not just a single vertex will have at least two leaves.
If a tree has more than one vertex, then it has at least two leaves.
We will use this claim in the following result, which we will provide a proof for.
A tree $T$ with $n$ vertices has $n-1$ edges.
We will show this by mathematical induction on $n$.
Base case. We have $n = 1$, and therefore, our graph contains $0 = 1 - 1$ edges, so our statement holds.
Inductive case. Let $k \in \mathbb N$ and assume that every tree $T'$ with $k$ vertices has $k-1$ edges. Now, consider a tree $T = (V,E)$ with $k+1$ vertices. Choose a leaf $v$ and consider its neighbour $u$. Consider the subgraph of $S = (V \setminus \{v\}, E \setminus \{(u,v)\})$ without $v$.
Notice that $S$ is a tree: removing $v$ and its incident edge did not disconnect the rest of the tree, nor did its removal create any cycles. Next, we observe that $S$ has $k$ vertices. By the inductive hypothesis, $S$ is a tree with $k$ vertices, so it has $k-1$ edges. Since we only removed one edge from $T$ to obtain $S$, $T$ must have $k = (k+1)-1$ edges as desired.
We can apply the idea of a tree as a minimally connected graph to say something about connectivity in graphs in general. One clear application is finding a minimal connected subgraph of the graph such that every vertex is connected. One can see how this might be useful in something like road network where you're trying to figure out what the most important roads to clear after a snowfall are.
A spanning subgraph which is also a tree is called a spanning tree.
Here is a graph, with one possible spanning tree highlighted.
A graph $G$ is connected if and only if it has a spanning tree.
Suppose $G$ has a spanning tree $T$. Then there exists a path between every pair of vertices in $T$ and therefore, there exists a path between every pair of vertices in $G$. Then by definition, $G$ is connected.
Now, suppose $G$ is connected. Consider the connected spanning subgraph $H$ of $G$ with the minimal number of edges. Suppose $H$ contains a cycle. Then we can remove an edge from this cycle, since no edge in a cycle is a bridge. Therefore, $H$ contains no cycles and since $H$ is connected, it is a tree.
An obvious computational problem is to find or construct spanning trees for a given graph. Many of you already know the algorithms that do this—it's breadth and depth first search. We are already familiar with BFS and DFS as algorithms that solve the connectivity problem: given two vertices $s$ and $t$, is there a path from $s$ to $t$?
This may not be something that you've considered before, particularly since we typically teach these as algorithms on directed graphs. Of course, the same algorithms work perfectly fine on undirected graphs. But notice that both of these algorithms visit every reachable vertex and only visit each vertex exactly once. This means that the traversal that these algorithms take is acyclic. And that we can reach every reachable vertex gives us an acyclic spanning subgraph for the component that contains $s$.