Another question related to connectivity that we can ask is how fragile the graph is. For instance, if we imagine some sort of network (computer, transportation, social, etc.), this is the same as asking where the points of failure are in our network. Which edges do we need to take out to disconnect our graph?
Let $G = (V,E)$ be a graph and consider an edge $e \in E$. If removing $e$ increases the number of connected components, then $e$ is a cut edge or bridge.
Consider the following graph $G$. There are two obvious bridges here: $(a_3,c_2)$ and $(b_2,c1)$.
We would like to be able to identify which edges are bridges and their properties. The following lemma is one of those results that sounds incredibly obvious based on the definitions involved and our intuition.
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$ and 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 v_4 \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$.
For the forward direciton, we 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 19.3. Therefore, $e$ is not in a cycle of $G$.
For the reverse direction, we 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.
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.
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, 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.
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$. Then $S$ has $k$ vertices. By the inductive hypothesis, $S$ 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.