CMSC-27100

Discrete Math

Winter Quarter, 2019

Home Lectures Policies

---

Piazza

Lecture 25: Graph Theory: Connectivity

\( \newcommand{\set}[1]{\{#1\}} \newcommand{\comprehension}[2]{\{#1\,\vert\,#2\}} \newcommand{\size}[1]{\left\vert#1\right\vert} \newcommand{\true}{\top} \newcommand{\false}{\bot} \newcommand{\limplies}{\rightarrow} \newcommand{\divides}{\mathbin{\vert}} \newcommand{\mult}{\mathbin{\cdot}} \newcommand{\xor}{\oplus} \newcommand{\union}{\cup} \newcommand{\intersect}{\cap} \newcommand{\complement}[1]{\overline#1} \newcommand{\powerset}{\mathcal{P}} \newcommand{\ixUnion}{\bigcup} \newcommand{\ixIntersect}{\bigcap} \newcommand{\Div}{\mathrm{div}} \newcommand{\gcd}{\mathrm{gcd}} \newcommand{\divmod}{\mathop{\mathbf{divmod}}} \newcommand{\div}{\mathop{\mathbf{div}}} \newcommand{\mod}{\mathop{\mathbf{mod}}} \newcommand{\ceiling}[1]{\lceil#1\rceil} \newcommand{\floor}[1]{\lfloor#1\rfloor} \DeclareMathOperator{\Pr}{Pr} \DeclareMathOperator{\rng}{rng} \DeclareMathOperator{\lcm}{lcm} \DeclareMathOperator{\deg}{deg} \DeclareMathOperator{\E}{E} \DeclareMathOperator{\V}{V} \DeclareMathOperator{\T}{T} \DeclareMathOperator{\O}{O} \newcommand{\abs}[1]{\left\lvert#1\right\rvert} \newcommand{\indeg}{\mathop{\deg^-}} \newcommand{\outdeg}{\mathop{\deg^+}} \)

Today's lecture follows section 10.4 of Rosen, with a few bits of my own.

We often think of a graph as a map: the vertices are locations, the edges represent roads that we can take from one location to another. As such, we're often interested in appending edges, thereby creating paths that connect one location to another.

Definition 25.1 A path in a graph $G=(V,E)$ is a finite sequence of edges $e_1,e_2,\ldots,e_n$ in $E$ for which there exists an associated vertex sequence $v_0,v_1,\ldots,v_n$ of vertices in $V$ such that each $e_i$ has endpoints $v_{i-1},v_i$. We say that such a path has length $n$. Note that in simple graphs, we can specify a path via the sequence $v_0,v_1,\ldots,v_n$, as the implied edge between $v_{i-1}$ and $v_i$ is unique. Note that we will consider trivial (or degenerate) paths, i.e., paths of length $0$, which we think of as being specified by a vertex $v_0$. A non-trivial path is a circuit (or cycle) if it begins and ends at the same vertex. Paths are said to pass through the intermediate points $x_1,\dots,x_{n-1}$, and to traverse their edges. A trail is a path without repeated edges (note that it may have repeated vertices). Note that Rosen uses “simple path” as a synonym for trail, whereas some authors reserve “simple path” for paths that do not repeat a vertex (except that the first and last vertex may be equal). Caveat emptor.

Of particular interest are minimum length paths, especially through social networks. E.g, consider the collaboration graphs in mathematics and (separately) cinema, where the vertices are individuals, and there's an edge connecting two individuals if they collaborated together (i.e., co-authored a scholarly paper, or acted in the same movie). Such paths are often surprisingly short, e.g., generally speaking, mathematicians know their own Erdös number (the length of the shortest path in the collaboration graph between them and the celebrated combinatorialist Paul Erdös), just as actors often know their Bacon number (the distance to Keven Bacon). FWIW, Erdös was a better mathematician than Bacon an actor. Within acquaintance graph of living adult humans, it is widely believed that there is a path of length at most six between almost any two individuals.

Definition 25.2 An undirected graph is connected if there is a path between every pair of vertices, otherwise it is disconnected.

Theorem 25.3 If two vertices in a graph are connected, then they are connected by a trail.

Proof Let $u$ and $v$ be vertices in a graph $G=(V,E)$. Consider the path of minimum length. If it duplicates an edge, we can create a shorter path by collapsing the two duplicated edges together, contradicting minimal length.

$\Box$ Theorem 25.3

One of the first results in graph theory was proven in response to the “Königsberg Bridge Problem.” The city of Königsberg had a complex topography. It was build on both sides of the Pregolya River, which contained two central islands. The smaller, but more central of the two (where the city's Cathedral was located) was connected to the north and south banks of the river by two bridges each, and to the east island by a fifth bridge. In addition, the east island was connected to the north and south bank by one bridge each.

We can represent this via a graph with multiple edges as follows:

The question was whether or not their existed a path through the town which crossed each bridge exactly once, and which returned to its starting point. Such tours are now called “Eulerian Tours,” after the famous mathematician who proved the following theorem, settling the Königsberg bridge problem:

Theorem 25.5 A graph $G=(V,E)$ contains an Eulerian tour if and only if every vertex has even degree.

Proof Interestingly, we only need the easy “only if” part of the problem to dispense with the Königsberg bridge problem, because it contains only vertices of odd degree! Note that a path, in passing through a point, must traverse two of the edges incident to it. If we have a non-starting vertex, and traverse every edge, we've traversed an even number of edges through a single point. As for the starting point, the last edge must return to where the first edge started, and so the beginning and end of the path also contribute an even number of edges through that point.

For the if part, pick a path of maximal length. It must be a cycle (i,e., a path that begins and ends at the same vertex, because otherwise there are a odd number of edges used at its starting and ending node, so so there's an unused incident edge which can be used to extend the path either way). If this path doesn't traverse every edge, chose a point on the path all of whose incident edges haven't been used (such a vertex must exist: the graph is connected, and so there exists a path from the start node to every other node). Start a new path there, not sharing any edge with the original path. By the same argument as before, it must return to its starting node. We can then splice the two cycles together at their common point, contradicting maximality.

$\Box$ Theorem 25.5

In the time since Euler lived, Königsberg has changed hands after the second world war, and is now Kaliningrad, part of Russia. And the duplicate edges between the two banks and the central island are no more: those bridges are gone. The topography is simpler, and yet, even so, there is still no tour:

Note that because paths can have length $0$, be reversed, and and composed, being connected by a path is respectively reflexive, symmetric, and transitive, i.e., it is an equivalence relation. A subgraph of a graph that consists of a single equivalence class of edges under the connectivity relation, together with all of the associated edges, is a connected component of the graph.

A representation of graphs that is particularly useful in dealing with paths is graphs is the adjacency matrix, which for an $n$-vertex graph $G=(V,E)$ where $V=\set{v_1,v_2,\ldots,v_n}$ is the $n\times n$ matrix $A$ in which

\begin{equation*} A_{i,j} = \begin{cases} 1, &\text{if there is an edge connecting $v_i$ and $v_j$}\\ 0, &\text{otherwise} \end{cases} \end{equation*}

We modify this definition for multi-graphs so that $A_{i,j}$ is the number of edges connecting $v_i$ and $v_j$, and for directed graphs by counting an edge only if it is oriented from $v_i$ to $v_j$. Note that the adjacency matrix is necessarily symmetric for undirected graphs.

Note that we can think of the entries of $A_{i,j}$ as counting the number of paths of length $1$ from $v_i$ to $v_j$, as paths of length one are merely edges. Likewise, the $n \times n$ identity matrix $I = A^0$ can be thought of as encoding the paths of length $0$. A moments reflection shows that $(A^2)_{i,j}$ is the number of paths of length $2$ from $v_i$ to $v_j$, as the dot product basically sums over intermediate vertices $v_k$ the number of paths from $v_i$ to $v_k$ times the number of paths from $v_k$ to $v_j$. Reasoning inductively, we can easily see that $(A^k)_{i,j}$ will be the number of paths of length $k$ from $v_i$ to $v_j$. Matrix methods have great utility in the study of graphs, despite the overhead of matrix representations of graphs.

Connectedness

Robustness is a real concern in network design. A router, or a computer can go down. An intersection can be blocked by an accident. Bad things happen to good networks. We often use graphs to model networks, and graph properties to assess network robustness.

Definition 25.7 Let $G=(V,E)$ be a graph, and $v\in V$ be a vertex. If removing $v$ and the edges incident to it increases the number of connected components, the $v$ is a cut vertex or articulation point. Likewise, if $e\in E$ is an edge such that removing it from $G$ results in increasing the number of connected components, then $e$ is a cut edge or bridge.

Definition 25.8 A connected graph with a cut vertex is separable, otherwise it is nonseparable.

Graphs can be disconnected by eliminating edges as well as vertices. Googling "internet interruption backhoe" results in 97 thousand hits at writing, and first page title like, “The Backhoe: A Real Cyberthreat - Wired,” “The Backhoe, The Internet's Natural Enemy - Slashdot,” and “Urban Dictionary: Fiber-seeking Backhoe.” It's a hard world for edges out there, too.

Definition 25.9 Let $G=(V,E)$ be a connected graph. A set $V' \subseteq V$ is a vertex cut if removing $V'$ and all of the edges incident to it results in a disconnected graph, or a graph with a single vertex. For graphs $G$ that are noncomplete, we define $\kappa(G)$ to be the size of the smallest vertex cut. For complete graphs on $n$ vertices, we define $\kappa(G) = n-1$.

Definition 25.11 A graph $G=(V,E)$ is $k$-connected if there is no edge cut of size less than $k$.

Definition 25.12 Let $G=(V,E)$ be a connected graph, and let $E'\subset E$ be a set of edges such that $(V,E\setminus E')$ is not connected. Then $E'$ is an edge cut of $G$. We define $\lambda(G)$ to be the size of the minimum edge cut. As a special case, we define $\lambda(G) = 0$ for the graph with one vertex and no edges.

Theorem 25.13 For all graphs $G=(V,E)$,

\begin{equation*} \kappa(G) \leq \lambda(G) \leq \min_{v\in V} \deg(v) \end{equation*}

This is a bit tricker than it looks. We'll deal with simple graphs here. The $1$ element simple graph is a special case easily dealt with: $\kappa(G) = \lambda(G) \min_{v\in V} \deg(v) = 0$. We can isolate a vertex by removing all of the edges connected to it, so $\lambda(G) \leq \min_{v\in V} \deg(v)$ is immediate. We can also eliminate an edge by the simple expedient of eliminating an end point. This requires a bit of care, though, as we might end up eliminating the component we mean to separate! To avoid this, designate two vertices, one each from the two components to be created by the edge cut, and make sure not to delete them!

Connectedness in Directed Graphs

Very similar definitions works for directed graphs

Definition 25.14 A path in a directed graph $G=(V,E)$ is a finite sequence of edges $e_1,e_2,\ldots,e_n$ in $E$ for which there exists an associated vertex sequence $v_0,v_1,\ldots,v_n$ of vertices in $V$ such that each $e_i$ is a directed edge from $v_{i-1}$ to $v_i$. Note the specificity here: the edges that make up a path have to connect from tail to head.

Some basic terminology: a graph $G' = (V',E')$ is a subgraph of a graph $G = (V,E)$ if $V' \subseteq V$ and $E' \subset E$. The subgraph induced by a set $V' \subset V$ is the largest subgraph of $G$ with vertex set $V'$, i.e., it includes all of the edges in $G$ which connect vertices in $E'$.

Definition 25.15 A directed graph $G=(V,E)$ is strongly connected if there is a directed path from $a$ to $b$ and from $b$ to $a$ for all $a,b \in V$. Such a graph is weakly connected if the undirected graph that results from replacing each directed edge with the corresponding undirected edge is connected.

As in the undirected case, we can impose a path-based equivalence notion on the vertices of a directed graph, but this time, we'll say that $a$ and $b$ are equivalent if there is a directed pat from $a$ to $b$ and a directed path from $b$ to $a$. Much as before, this relation is easily seen to be an equivalence relation, and so we define the strongly connected components of a graph $G=(V,E)$ to be maximal subgraphs which are strongly connected as graphs.

---

© 2016–2019 Stuart A. Kurtz
Last modified: March 13, 2019