6.042/18.062J Mathematics for Computer Science September 28, 2004 Tom Leighton and Eric Lehman Lecture Notes

Graph Theory

1 Introduction

Informally, a graph is a bunch of dots connected by lines. Here is an example of a graph:

Sadly, this definition is not precise enough for mathematical discussion. Formally, a graph is a pair of sets (V, E), where:

• V is a nonempty set whose elements are called vertices.

• E is a collection of two-element subsets of V called edges.

The vertices correspond to the dots in the picture, and the edges correspond to the lines. Thus, the dots-and-lines diagram above is a pictorial representation of the graph (V, E) where:

V = {A, B, C, D, E, F, G, H, I}
E = {{A, B} , {A, C} , {B, D} , {C, D} , {C, E} , {E, F } , {E, G} , {H, I}} .

1.1 Definitions

A nuisance in first learning graph theory is that there are so many definitions. They all correspond to intuitive ideas, but can take a while to absorb. Some ideas have multiple names. For example, graphs are sometimes called networks, vertices are sometimes called nodes, and edges are sometimes called arcs. Even worse, no one can agree on the exact meanings of terms. For example, in our definition, every graph must have at least one vertex. However, other authors permit graphs with no vertices. (The graph with no vertices is the single, stupid counterexample to many would-be theorems— so we’re banning it!) This is typical; everyone agrees more-or-less what each term means, but disagrees about weird special cases. So do not be alarmed if definitions here differ subtly from definitions you see elsewhere. Usually, these differences do not matter.

If you suspect you’ve found an error in these notes or you just find a part hopelessly confusing, please send email to e lehman@mit.edu, and I’ll try to fix the problem.

Hereafter, we use A—B to denote an edge between vertices A and B rather than the set notation {A, B}. Note that A—B and B—A are the same edge, just as {A, B} and {B, A} are the same set.

Two vertices in a graph are said to be adjacent if they are joined by an edge, and an edge is said to be incident to the vertices it joins. The number of edges incident to a vertex is called the degree of the vertex. For example, in the graph above, A is adjacent to B and B is adjacent to D, and the edge A—C is incident to vertices A and C. Vertex H has degree 1, D has degree 2, and E has degree 3.

Deleting some vertices or edges from a graph leaves a subgraph. Formally, a subgraph of G = (V, E) is a graph G′ = (V′, E′) where V′ is a nonempty subset of V and E′ is a subset of E. Since a subgraph is itself a graph, the endpoints of every edge in E′ must be vertices in V′.

1.2 Sex in America

A 1994 University of Chicago study entitled The Social Organization of Sexuality found that on average men have 74% more opposite-gender partners than women.

Let’s recast this observation in graph theoretic terms. Let G = (V, E) be a graph where the set of vertices V consists of everyone in America. Now each vertex either represents either a man or a woman, so we can partition V into two subsets: M, which contains all the male vertices, and W, which contains all the female vertices. Let’s draw all the M vertices on the left and the W vertices on the right:

Now, without getting into a lot of specifics, sometimes an edge appears between an M vertex and a W vertex:

Since we’re only considering opposite-gender relationships, every edge connects an M vertex on the left to a W vertex on the right. So the sum of the degrees of the M vertices must equal the sum of the degrees of the W vertices:

∑_{x∈M} deg(x) = ∑_{y∈W} deg(y)

Now suppose we divide both sides of this equation by the product of the sizes of the two sets, |M| · |W |:

(\frac{∑_{x∈M} deg(x)}{|M|}) · \frac{1}{|W |} = (\frac{∑_{y∈W} deg(y)}{|W |}) · \frac{1}{|M|}

The terms above in parentheses are the average degree of an M vertex and the average degree of a W vertex. So we know:

\frac{Avg. deg in M}{|W |} = \frac{Avg. deg in W}{|M|}
Avg. deg in M = \frac{|W |}{|M|} · Avg. deg in W

Now the Census Bureau reports that there are slightly more women than men in America; in particular |W | / |M| is about 1.035. So— assuming the Census Bureau is correct— we’ve just proved that the University of Chicago study got bad data! On average, men have 3.5% more opposite-gender partners. Furthermore, this is totally unaffected by differences in sexual practices between men and women; rather, it is completely determined by the relative number of men and women!

1.3 Graph Variations

There are many variations on the basic notion of a graph. Three particularly common variations are described below. In a multigraph, there may be more than one edge between a pair of vertices. Here is an example:

The edges in a directed graph are arrows pointing to one endpoint or the other. Here is an example:

Directed graphs are often called digraphs. We denote an edge from vertex A to vertex B in a digraph by A ⟶ B. Formally, the edges in a directed graph are ordered pairs of vertices rather than sets of two vertices. The number of edges directed into a vertex is called the in-degree of the vertex, and the number of edged directed out is called the out-degree.

One can also allow self-loops, edges with both endpoints at one vertex. Here is an example of a graph with self-loops:

Combinations of these variations are also possible; for example, one could work with directed multigraphs with self-loops.

Except where stated otherwise, the word “graph” in this course refers to a graph without multiple edges, directed edges, or self-loops.

1.4 Applications of Graphs

Graphs are the most useful mathematical objects in computer science. You can model an enormous number of real-world systems and phenomena using graphs. Once you’ve created such a model, you can tap the vast store of theorems about graphs to gain insight into the system you’re modeling. Here are some practical situations where graphs arise:

Data Structures Each vertex represents a data object. There is a directed edge from one object to another if the first contains a pointer or reference to the second.

Attraction Each vertex represents a person, and each edge represents a romantic attraction. The graph could be directed to model the unfortunate asymmetries.

Airline Connections Each vertex represents an airport. If there is a direct flight between two airports, then there is an edge between the corresponding vertices. These graphs often appear in airline magazines.

The Web Each vertex represents a web page. Directed edges between vertices represent hyperlinks.

People often put numbers on the edges of a graph, put colors on the vertices, or add other ornaments that capture additional aspects of the phenomenon being modeled. For example, a graph of airline connections might have numbers on the edges to indicate the duration of the corresponding flight. The vertices in the attraction graph might be colored to indicate the person’s gender.

1.5 Some Common Graphs

Some graphs come up so frequently that they have names. The complete graph on n vertices, also called K_{n}, has an edge between every pair of vertices. Here is K_{5}:

The empty graph has no edges at all. Here is the empty graph on 5 vertices:

Here is a path with 5 vertices:

And here is a cycle with 5 vertices, which is typically denoted C_{5}:

Paths and cycles are going to be particularly important, so let’s define them precisely. A path is a graph P = (V, E) of the form

V = {v_{1}, v_{2}, …, v_{n}} E = {v_{1}—v_{2}, v_{2}—v_{3}, …, v_{n−1}—v_{n}}

where n ≥ 1 and vertices v_{1}, …, v_{n} are all distinct. Vertices v_{1} and v_{n} are the endpoints of the path. Note that a path may consist of a single vertex, in which case both endpoints are the same. We’ll often say that there is a path from u to v in a graph G; this is a shorthand for saying that a path with endpoints u and v is a subgraph of G.

Similarly, a cycle is a graph C = (V, E) of the form

V = {v_{1}, v_{2}, …, v_{n}} E = {v_{1}—v_{2}, v_{2}—v_{3}, …, v_{n−1}—v_{n}, v_{n}—v_{1}}

where n ≥ 3 and v_{1}, …, v_{n} are all distinct. The length of a path or cycle is the number of edges it contains. For example, a path with 5 vertices has length 4, but a cycle with 5 vertices has length 5.

1.6 Isomorphism

Two graphs that look the same might actually be different in a formal sense. For example, the two graphs below are both cycles with 4 vertices:

But one graph has vertex set {A, B, C, D} while the other has vertex set {1, 2, 3, 4}. If so, then the graphs are different mathematical objects, strictly speaking. But this is a frustrating distinction; the graphs look the same!

Fortunately, we can neatly capture the idea of “looks the same” and use that as our main notion of equivalence between graphs. Graphs G_{1} and G_{2} are isomorphic if there exists a one-to-one correspondence between vertices in G_{1} and vertices in G_{2} such that there is an edge between two vertices in G_{1} if and only if there is an edge between the two corresponding vertices in G_{2}. For example, take the following correspondence between vertices in the two graphs above:

A corresponds to 1  B corresponds to 2
D corresponds to 4  C corresponds to 3.

Now there is an edge between two vertices in the graph on the left if and only if there is an edge between the two corresponding vertices in the graph on the right. Therefore, the two graphs are isomorphic. The correspondence itself is called an isomorphism.

Two isomorphic graphs may be drawn to look quite different. For example, here are two different ways of drawing C_{5}:

Isomorphic graphs share a great many properties, such as the number of vertices, number of edges, and the pattern of vertex degrees. Thus, two graphs can be proved nonisomorphic by identifying some property that one possesses that the other does not. For example, if one graph has two vertices of degree 5 and another has three vertices of degree 5, then the graphs can not be isomorphic.

2 Connectivity

In the diagram below, the graph on the left has two pieces, while the graph on the right has just one.

Let’s put this observation in rigorous terms. A graph is connected if for every pair of vertices u and v, the graph contains a path with endpoints u and v as a subgraph. The graph on the left is not connected because there is no path from any of the top three vertices to either of the bottom two vertices. However, the graph on the right is connected, because there is a path between every pair of vertices.

A maximal, connected subgraph is called a connected component. (By “maximal”, we mean that including any additional vertices would make the subgraph disconnected.) The graph on the left has two connected components, the triangle and the single edge. The graph on the right is entirely connected and thus has a single connected component.

2.1 A Simple Connectivity Theorem

The following theorem says that a graph with few edges must have many connected components.

Theorem 1. Every graph G = (V, E) has at least |V | − |E| connected components.

Proof. We use induction on the number of edges. Let P (n) be the proposition that every graph G = (V, E) with |E| = n has at least |V | − n connected components.

Base case: In a graph with 0 edges, each vertex is itself a connected component, and so there are exactly |V | − 0 = |V | connected components.

Inductive step: Now we assume that the induction hypothesis holds for every n-edge graph in order to prove that it holds for every (n + 1)-edge graph, where n ≥ 0. Consider a graph G = (V, E) with n + 1 edges. Remove an arbitrary edge u—v and call the resulting graph G′. By the induction assumption, G′ has at least |V | − n connected components. Now add back the edge u—v to obtain the original graph G. If u and v were in the same connected component of G′, then G has the same number of connected components as G′, which is at least |V | − n. Otherwise, if u and v were in different connected components of G′, then these two components are merged into one in G, but all other components remain. Therefore, G has at least |V | − n − 1 = |V | − (n + 1) connected components.

The theorem follows by induction.

Corollary 2. Every connected graph with n vertices has at least n − 1 edges.

A couple points about the proof of Theorem 1 are worth noting. First, notice that we used induction on the number of edges in the graph. This is very common in proofs involving graphs, and so is induction on the number of vertices. When you’re presented with a graph problem, these two approachs should be among the first you consider. Don’t try induction on other variables that crop up in the problem unless these two strategies seem hopeless.

The second point is more subtle. Notice that in the inductive step, we took an arbitrary (n + 1)-edge graph, threw out an edge so that we could apply the induction assumption, and then put the edge back. You’ll see this shrink-down, grow-back process very often in the inductive steps of proofs related to graphs. This might seem like needless effort; why not start with an n-edge graph and add one more to get an (n + 1)-edge graph? That would work fine in this case, but opens the door to a very nasty logical error in similar arguments. (You’ll see an example in recitation.) Always use shrink-down, grow-back arguments, and you’ll never fall into this trap.

2.2 Distance and Diameter

The distance between two vertices in a graph is the length of the shortest path between them. For example, the distance between two vertices in a graph of airline connections is the minimum number of flights required to travel between two cities.

In this graph, the distance between C and H is 2, the distance between G and C is 3, and the distance between A and itself is 0. If there is no path between two vertices, then the distance between them is said to be “infinity”.

The diameter of a graph is the distance between the two vertices that are farthest apart. The diameter of the graph above is 5. The most-distant vertices are A and G, which are at distance 5 from one another.

2.2.1 Six Degrees of Separation

There is an old claim that the world has only “six degrees of separation”. In other words, if you pick any two people on the planet— say a hermit in Montana and a random person off the street in Beijing— then the hermit knows someone who knows someone who knows someone who knows the Chinese pedestrian, where the word “knows” appears at most six times.

We can recast this in graph-theoretic terms. Consider a graph where the vertices are all the people on the planet, and there is an edge between two people if and only if they know each other. Then the “six degrees of separation” claim amounts to the assertion that the diameter of this graph is at most 6.

There is little hope of proving or disproving the claim, since people are constantly being born, meeting one another, and dying and no one can keep track of who-knows-who. However, precise data does exist for something similar. The University of Virginia maintains the Oracle of Bacon website. This is based on an “acting graph” where the vertices are actors and actresses, and there is an edge between two performers if they appeared in a movie together. The website reports that everyone is within distance 8 of Kevin Bacon. (This excludes a few actors who are completely disconnected.) This allows us to at least obtain an upper bound on the diameter of the acting graph.

Theorem 3. Let v be an arbitrary vertex in a graph G. If every vertex is within distance d of v, then the diameter of the graph is at most 2d.

Proof. Let x and y be arbitrary vertices in the graph. Then there exists a path of length at most d from x to v, and there exists a path of length at most d from v to y.

Let z be the vertex that lies on both the x-to-v and v-to-y paths and is closest to x. (We know that such a vertex exists, since z could be v, at least.) Joining the x-to-z segment to the z-to-y segment gives a path from x to y of length at most 2d. Therefore, every vertex is within distance 2d of every other.

Data elsewhere on the Oracle of Bacon site shows that the diameter of the acting graph is at least 15, so the upper bound isn’t far off.

3 Traversing a Graph

Can you walk every hallway in the Museum of Fine Arts exactly once? If we represent hallways and intersections with edges and vertices, then this reduces to a question about graphs. For example, could you visit every hallway exactly once in a museum with this floorplan?

3.1 Euler Tours and Hamiltonian Cycles

A walk in a graph G is an alternating sequence of vertices and edges of the form:

v_{0}, v_{0}—v_{1}, v_{1}, v_{1}—v_{2}, v_{2}, …, v_{n−1}, v_{n−1}—v_{n}, v_{n}

If v_{0} = v_{n}, then the walk is closed. Walks are similar to paths. However, a walk can cross itself, traverse the same edge multiple times, etc. There is a walk between two vertices if and only if there is a path between the vertices.

The entire field of graph theory began when Euler asked whether the seven bridges of Königsberg could all be traversed exactly once— essentially the same question we asked by the Museum of Fine Arts. In his honor, an Euler walk is a walk that contains every edge in a graph exactly once. Similarly, an Euler tour is an Euler walk that starts and finishes at the same vertex; that is, v_{0} = v_{n}. Graphs with Euler tours and Euler walks both have simple characterizations.

Theorem 4. A connected graph has an Euler tour if and only if every vertex has even degree.