CMSC 27100 — Lecture 20

Bridges

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: $(2,10)$ and $(6,11)$.

We would like to be able to identify which edges are bridges and their properties. Something we can immediately make more specific is the following result.

Let $G$ be a connected graph. If $(u,v) \in E$ is a bridge, then $G - (u,v)$ (i.e., the subgraph of $G$ with only the edge $(u,v)$ deleted) has exactly two components and $u$ and $v$ are in different components.

Notice that the definition of a bridge only says that removing it will increase the number of components. This lemma makes this more specific by telling us exactly what will happen to the graph and the vertices incident to the bridge.

Since $(u,v)$ is a bridge, we know that $G - (u,v)$ has at least two components by definition. Let $X$ be the set of vertices that are in the same component as $u$. Choose some vertex $w \not \in X$, so $w$ is not in the same component as $u$ in $G - (u,v)$.

Since $G$ was connected, $G$ contained a path from $u$ to $w$, while there are no paths in $G - (u,v)$. Thus, any path from $u$ to $w$ must have contained the edge $(u,v)$. Since a path cannot repeat vertices or edges, any such path must have the form $uv v_2 \cdots v_{n-1} w$.

Then $v v_2 \cdots v_{n-1} w$ is a path in $G - (u,v)$. Therefore, $v$ and $w$ are in the same component. But recall that the choice of $w \not \in X$ was arbitrary. This means that there exists a path from $v$ to every vertex $w \not \in X$ in $G - (u,v)$.

Therefore, $G - (u,v)$ has two components: one containing all vertices in $X$ and the other containing all vertices in $V \setminus X$. Furthermore, $u \in X$ and $v \in V \setminus X$ so they are in different components.

We can use this to get the following important characterization of bridges.

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$.

Notice that this is an equivalence: it is easy to see that this says that a bridge is not in a cycle, but the converse is also true. That is, if can tell whether an edge is a bridge by figuring out whether or not it is involved in a cycle.

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.3. 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 (but you can try on your own).

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.

Trees

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 “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 is a tree, though it is not drawn in the “usual” way we think of.

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$.

Observe that the highlighted path is the only such path between these two pair of vertices.

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.

Notice that the highlighted edges are all edges that were not originally in the graph.

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.

The leaves of this tree are denoted in green.

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.

It is worth taking a moment to observe that this inductive proof is a bit unlike some of the other ones we’ve done in the course so far. Namely, this proof performs induction not on the structure of interest, graphs, but on the natural numbers. In a way, this makes sense, because graphs are not naturally recursive—they do not have a recursive definition.

But if that’s the case, how can we perform induction? It is actually quite a common technique to perform induction on the size of something: the length of a string, the cardinality of a set, the number of vertices in a graph. One reason for this is that many people are not comfortable with performing induction on structures, but are quite happy to perform induction on natural numbers.

Then is there a way to interpret induction on the size of an object in the way that we’ve been discussing? We can observe that the thing that all of these objects have in common are they are discrete structures. This means that we can construct these objects via a discrete series of steps. In a sense, it’s this process that we’re performing induction on: to get to an object of size $k+1$, we need to build off of an object of $k$ (or smaller).

This also illuminates why certain statements are phrased and ordered the way they are. Recall that the inductive case of the induction axiom is \[\forall k (P(k) \rightarrow P(k+1)).\] This translates directly in our proof above:

Let $k \in \mathbb N$. Assume that every tree $T'$ with $k$ vertices...

But where many students make a mistake is in what follows. In our proof above, we consider $T$ with $k+1$ vertices. But many students will say something like

Consider a tree $T'$ with $k$ vertices. Add a new vertex and edge to any vertex of $T'$ to obtain a tree $T$ with $k+1$ vertices.

Why is that wrong? This goes back to what an inductive proof is trying to do. When we perform induction on $n$, we are trying to prove something about $n$. But what is $n$? We have to look at the definition, which has cases. So $n$ might satisfy the base case and we need to say something about that, and then $n$ might satisfy the inductive case, so we need to say something about that.

In the case of graphs, after we’ve established an arbitrary $k$, we consider $n = k+1$, and therefore, we need to consider all graphs with $k+1$ vertices. This is a universally quantified statement, so this means we must consider an arbitrary graph with $k+1$ vertices. We cannot start with a graph with $k$ vertices.

The impulse to start with a graph with $k$ vertices is not totally unnatural, for the reason that for many students, this is exactly how induction was taught to them. If you learn induction as “assume for $k$ and use it to prove something for $k+1$” and that is the only kind of induction you do, then you’re going to keep using that one hammer.

But now, we’ve seen a wide variety of recursive structures: natural numbers, of course, but also strings, lists, trees, and formulas. The difference between natural numbers and all of these other structures is that there is only one way to go from $k$ to $k+1$, but for everything else, there are many other possibilities to account for. This is the situation we are in with graphs: it is not obvious that we can account for every graph of $k+1$ vertices if we start with a graph with $k$ vertices without being extremely thorough.