CMSC 27100 — Lecture 18

Graph Theory

Graphs are a discrete structure that represent relations, both in the mathematical sense (a subset of pairs of some domain) and in the real-world sense.

Typically, the notion of “graphs” is associated with either graphical charts of data or from calculus in the form of visualizing functions in some 2D or 3D space. However, if you’ve taken a CS class before, you will likely have also encountered graphs as a data structure.

Graphs have a natural visual representation: we represent things as circles, which we call nodes or vertices, and we represent a relationship between two things by drawing a line or arrow between them, which we call edges.

Seeing this, it would not be surprising to learn that the development of graph theory is closely linked to the mathematical formalization of chemistry. The term graph has its origins here, as a short form for “chemicograph”.

Perhaps some of the most obvious graphs in our lives nowadays are those related to the Internet:

Graphs also have lots of non-network applications in computer science.

Graphs also model many real-world phenomena.

You’ll be familiar with the concept of graphs if you’ve taken courses in the introductory CS sequence. There, you are introduced to graphs as a data structure. Here, we’ll be considering graphs as a mathematical object. As we’ve been seeing, this is actually not so different, except that we don’t really have any “implementation details” to think about.

A graph $G = (V,E)$ is a pair with a non-empty set of vertices $V$ together with a set of edges $E$. An edge $e \in E$ is an unordered pair $(u,v)$ of vertices $u,v \in V$.

The following graph is called the Petersen graph. The Petersen graph is a particularly interesting graph, not just because it looks neat, but because it happens to be a common counterexample for many results in graph theory.

One way to define the Petersen graph is by considering the 2-element subsets of a set of five objects. We take the vertices to be the subsets and we define an edge between two vertices if the subsets are disjoint. That is, the Petersen graph is the graph $G = (V,E)$, where $V = \{S \subseteq \{0,1,2,3,4\} \mid |S| = 2\}$ and $E = \{(u,v) \mid u \cap v = \emptyset\}$.

From the definition, we immediately get that the edge set $E$ is a relation on $V \times V$. Furthermore, for undirected graphs, the edge relationship is always symmetric: $(u,v) \in E \rightarrow (v,u) \in E$. However, we don’t treat these two pairs as different edges—they are considered one and the same.

One can define graphs more generally and then restrict consideration to our particular definition of graphs, which would usually be then called simple graphs. Instead, what we do is start with the most basic version of a graph, from which we can augment our definition with the more fancy features if necessary (it will not be necessary in this course).

For example, the above examples indicate that we can have a version of graphs in which edges have a direction, or where the edge relation is not enforced to be symmetric. These are directed graphs.

More general definitions of graphs also allow for things like multiple edges between vertices or loops.

Other enhancements may include equipping edges with weights or even generalizing edges to hyperedges that relate more than two vertices.

Two vertices $u$ and $v$ of a graph $G$ are adjacent if they are joined by an edge $(u,v)$. We say the edge $(u,v)$ is incident to $u$ and $v$. The degree of a vertex $v$ in $G$, denoted $\deg(v)$, is the number of its neighbours.

In other words, adjacency is about the relationship between two vertices, while incidence is about the relationship between a vertex and an edge.

The following results are some of the first graph theory results, proved by Leonhard Euler in 1736.

Let $G = (V,E)$ be an undirected graph. Then $$\sum_{v \in V} \deg(v) = 2 \cdot |E|.$$

Every edge $(u,v)$ is incident to exactly two vertices: $u$ and $v$. Therefore, each edge contributes 2 to the sum of the degrees of the vertices in the graph.

Recall the Petersen graph. It has $\binom 5 2 = 10$ vertices. How many edges does it have? Consider the 2-element subset $\{0,1\}$ of $\{0,1,2,3,4\}$. How many other 2-element subsets are disjoint with it? These must be 2-element subsets that do not contain $0$ or $1$. This means there are only three elements left to form subsets from: $\binom 3 2 = 3$. Now apply this argument for all subsets we find that every subset has three other ones it is disjoint with. In other words, the degree of every vertex in this graph is $3$. So we have \[\sum_{v \in V} \deg(v) = \sum_{v \in V} 3 = 10 \times 3 = 30,\] which gives us $|E| = 15$.

Now, let’s look at some examples of some well-known graphs.

The complete graph on $n$ vertices is the graph $K_n = (V,E)$, where $|V| = n$ and $$E = \{(u,v) \mid u,v \in V\}.$$ That is, every pair of vertices are neighbours.

The cycle graph on $n$ vertices is the graph $C_n = (V,E)$ where $V = \{v_1, v_2, \dots, v_n\}$ and $E = \{(v_i,v_j) \mid j = i + 1 \bmod n\}$. It’s named so because the most obvious way to draw the graph is with the vertices arranged in order, on a circle.

The $n$-(hyper)cube graph is the graph $Q_n = (V,E)$, where $V = \{0,1\}^n$ (i.e., binary strings of length $n$) and $(u,v)$ is an edge if, for $u = a_1 a_2 \cdots a_n$ and $v = b_1 b_2 \cdots b_n$, there exists an index $i, 1 \leq i \leq n$ such that $a_i \neq b_i$ and $a_j = b_j$ for all $j \neq i$. In other words, $u$ and $v$ differ in exactly one symbol.

It’s called a cube (or hypercube) because one of the ways to draw it is to arrange the vertices and edges so that they form the $n$th-dimensional cube.

Speaking of arranging vertices, consider the following drawings of graphs.

These two graphs happen to be the “same”. Furthermore, it turns out that these are also basically the same graph as $Q_3$, or at least, we feel that it should be. This means we don’t need to necessarily draw a $3$-cube like a cube (and we certainly wouldn’t expect this for $n \gt 3$).

Although the visual representation of the graph is very convenient, it is sometimes misleading, because we’re limited to 2D drawings. In fact, there is a vast area of research devoted to graph drawing and the mathematics of embedding graphs in two dimensions. The point of this is that two graphs may look very different, but turn out to be the same.

But even more fundamental than that, we intuitively understand that just because the graph isn’t exactly the same (i.e., the vertices are named something differently) doesn’t mean that we don’t want to consider them equivalent. So how do we discuss whether two graphs are basically the same, just with different names or drawings?