EECS 70 Discrete Mathematics and Probability Theory Fall 2021
1 Graph Theory: An Introduction
One of the fundamental ideas in computer science is the notion of abstraction: capturing the essence or the core of some complex situation by a simple model. Some of the largest and most complex entities we might deal with include the internet, the brain, maps, and social networks. In each case, there is an underlying “network” or graph that captures the important features that help us understand these entities more deeply. In the case of the internet, this network or graph specifies how web pages link to one another. In the case of the brain, it is the interconnection network between neurons. We can describe these ideas in the beautiful framework of graph theory, which is the subject of this lecture.
Remarkably, graph theory has its origins in a simple evening pastime of the residents of Königsberg, Prussia (nowadays Kaliningrad, Russia) a few centuries ago. Through their city ran the Pregel river, depicted on the left in Figure 1 below, separating Königsberg into two banks A and D and islands B and C. Connecting the islands to the mainland were seven bridges. As the residents of the city took their evening walks, many would try to solve the challenge of picking a route that would cross each of the seven bridges precisely once and return to the starting point.
Figure 1: (Left) The city of Königsberg. (Right) The (multi-)graph modeling the bridge connections in Königsberg.
In 1736, the brilliant mathematician proved this task to be impossible. How did he do it? The key is to realize that for the purpose of choosing such a route, Figure 1a can be replaced with Figure 1b, where each land mass A, B, C, and D is replaced by a small circle, and each bridge by a line segment. With this abstraction in place, the task of choosing a route can be restated as follows: trace through all the line segments and return to the starting point without lifting the pen, and without traversing any line segment more than once. The proof of impossibility is simple. Under these tracing rules, the pen must enter each small circle as many times as it exits it, and therefore the number of line segments incident to that circle must be even. But in Figure 1b, each circle has an odd number of line segments incident to it, so it is impossible to carry out such a tracing. Actually Euler did more. He gave a precise condition under which the tracing can be carried out. For this reason, Euler is generally hailed as the inventor of graph theory.
EECS 70, Fall 2021, Note 5 1
1.1 Formal definitions
Formally, a (undirected) graph is defined by a set of vertices V and a set of edges E . The vertices correspond to the little circles in Figure 1 above, and the edges correspond to the line segments between the vertices. In Figure 1, V = {A,B,C,D} and E = {{A,B},{A,B},{A,C},{B,C},{B,D},{B,D},{C,D}}. However, note that here E is a multiset (a set where an element can appear multiple times). This is because in the Königsberg example there are multiple bridges between a pair of banks. We will generally not consider such a situation of multiple edges between a single pair of vertices, so in our definition, we require E to be a set, not a multi-set. What this means is that between any pair of vertices there is either 0 or 1 edge. If there are multiple edges between a pair of vertices, then we collapse them into a single edge.
More generally, we can also define a directed graph. If an edge in an undirected graph represents a street, then an edge in a directed graph represents a one-way street. To make this formal, let V be a set denoting the vertices of a graph G. For example, we can have V = {1, 2, 3, 4}. Then, the set of (directed) edges E is a subset of V ×V, i.e. E ⊆ V ×V. (Recall here that U ×V denotes the Cartesian product of sets U and V, defined as U × V = {(u, v) : u ∈ U and v ∈ V }.) Continuing with our example, let E = {(1, 2), (1, 3), (1, 4)}. Then, the corresponding graph is given by G1 below.
Figure 2: Examples of directed and undirected graphs, respectively.
Note that each edge in G1 has a direction specified by an arrow; thus, for example, (1, 2) ∈ E but (2, 1) ̸∈ E . Such graphs are useful in modeling one-way relationships, such as one-way streets between two locations, and are called directed. On the other hand, if each edge goes in both directions, i.e., (u, v) ∈ E iff (v, u) ∈ E , then we call the graph undirected. For undirected graphs we drop the ordered pair notation for edges, and simply denote the edge between u and v by the set {u,v}. Undirected graphs model relationships such as two-way streets between locations naturally, and an example is given by G2 above. For simplicity, we omit the arrowheads when drawing edges in undirected graphs. We conclude that a graph is thus formally specified as an ordered pair G = (V, E ), where V is the vertex set and E is the edge set.
Sanity check! What are the vertex and edge sets V and E for graph G2?
Let us continue our discussion with a working example from social networks, an area in which graph theory plays a fundamental role. Suppose you wish to model a social network in which vertices correspond to people, and edges correspond to the following relationship between people: We say Alex recognizes Bridget if Alex knows who Bridget is, but Bridget does not know who Alex is. If, on the other hand, Alex knows Bridget and Bridget knows Alex, then we say they know each other.
Sanity check! Suppose first that an edge between two people (say) Alex and Bridget means that Alex recognizes Bridget; would you use a directed or undirected graph for this? How about if an edge instead
EECS 70, Fall 2021, Note 5 2
means Alex and Bridget know each other? (Answer: directed and undirected, respectively.)
Moving on with our example, we say that edge e = {u, v} (or e = (u, v)) is incident on vertices u and v, and that u and v are neighbors or adjacent. If G is undirected, then the degree of vertex u ∈ V is the number of edges incident to u, i.e., degree(u) = |{v ∈ V : {u,v} ∈ E}|. A vertex u whose degree is 0 is called an isolated vertex, since there is no edge which connects u to the rest of the graph.
Sanity check! What does the degree of a vertex represent in our undirected social network in which an edge {u, v} means u and v know each other? How should we interpret an isolated vertex?
A directed graph, on the other hand, has two different notions of degree due to the directions on the edges. Specifically, the in-degree of a vertex u is the number of edges from other vertices to u, and the out-degree of u is the number of edges from u to other vertices.
Sanity check! What do the in-degree and out-degree of a vertex represent in our directed social network in which an edge (u, v) means u recognizes v?
Finally, our definition of a graph thus far allows edges of the form {u,u} (or (u,u)), i.e., a self-loop. In our social network, however, this gives us no interesting information (it means that person A recognizes him/herself!). Thus, here and in general in these notes, we shall assume that our graphs have no self-loops, unless stated otherwise. We shall also not allow multiple edges between a pair of vertices (unlike the case of the Seven Bridges of Königsberg).
Paths, walks, and cycles. Let G = (V,E) be an undirected graph. A path in G is a sequence of edges {v1,v2},{v2,v3},…,{vn−2,vn−1},{vn−1,vn}. In this case we say that there is a path between v1 and vn. For example, suppose the graph G3 below models a residential neighborhood in which each vertex corresponds to a house, and two houses u and v are neighbors if there exists a direct road from u to v.
Sanity check! What is the shortest path from house 1 to house 3 in G3? How about the longest path, assuming no house is visited twice?
Usually, we assume a path is simple, meaning v1,…,vn are distinct. This makes complete sense in our housing example G3; if you wanted drive from house 1 to 3 via house 2, why would you visit house 2 more
EECS 70, Fall 2021, Note 5 3
than once? A cycle (or circuit) is a sequence of edges {v1,v2},{v2,v3},…,{vn−2,vn−1},{vn−1,vn},{vn,v1}, where v1,…,vn are distinct.
Sanity check! Give a cycle starting at house 1 in G3.
Suppose now that your aim is not to go from 1 to 3 as quickly as possible, but to take a leisurely stroll from 1 to 3 via the sequence {1, 2}, {2, 1}, {1, 4}, {4, 3}. A sequence of edges with repeated vertices, such as this one, is called a walk from 1 to 3. Analogous to the relationship between paths and cycles, a tour is a walk which starts and ends at the same vertex. For example, {1,2},{2,3},{3,1} is a tour.
Connectivity. Much of what we discuss in this note revolves around the notion of connectivity. A graph is said to be connected if there is a path between any two distinct vertices. For example, our residential network G3 above is connected, since one can drive from any house to any other house via some sequence of direct roads. On the other hand, the network below is disconnected.
Sanity check! What would a disconnected vertex represent in our residential network? Why would you not want to design a neighborhood this way?
Note that any graph (even a disconnected one) always consists of a collection of connected components, i.e., sets V1,…,Vk of vertices, such that all vertices in a set Vi are connected. For example, the graph above is not connected, but nevertheless consists of three connected components: V1 = {1, 2, 3}, V2 = {4}, and V3 ={5,6,7}.
2 Revisiting the Seven Bridges of Koenigsberg: Eulerian Tours
With a formal underpinning in graph theory under our belts, we are ready to revisit the Seven Bridges of Königsberg. What exactly is this problem asking? It says: Given a graph G (in this case, G is an abstraction of Königsberg), is there a walk in G that uses each edge exactly once? We call any such walk in a graph an Eulerian walk. (In contrast, by definition a walk can normally visit each edge or vertex as many times as desired.) Moreover, if an Eulerian walk is closed, i.e., it ends at its starting point, then it is called an Eulerian tour. Thus, the Seven Bridges of Königsberg asks: Given a graph G, does it have an Eulerian tour? We now give a precise characterization of this in terms of simpler properties of the graph G. For this, define an even degree graph as a graph in which all vertices have even degree.
EECS 70, Fall 2021, Note 5 4
Theorem 5.1 (Euler’s Theorem (1736)). An undirected graph G = (V,E) has an Eulerian tour iff G is even degree, and connected (except possibly for isolated vertices).
Proof. To prove this, we must establish two directions: if, and only if.
Only if. We give a direct proof for the forward direction, i.e., if G has an Eulerian tour, then it is connected and has even degree. Assume that G has an Eulerian tour. This means every vertex that has an edge adjacent to it (i.e., every non-isolated vertex) must lie on the tour, and is therefore connected with all other vertices on the tour. This proves that the graph is connected (except for isolated vertices).
Next, we prove that each vertex has even degree by showing that all edges incident to a vertex can be paired up. Notice that every time the tour enters a vertex along an edge it exits along a different edge. We can pair these two edges up (they are never again traversed in the tour). The only exception is the start vertex, where the first edge leaving it cannot be paired in this way. But notice that by definition, the tour necessarily ends at the start vertex. Therefore, we can pair the first edge with the last edge entering the start vertex. So all edges adjacent to any vertex of the tour can be paired up, and therefore each vertex has even degree.
If. We give a recursive algorithm for finding an Eulerian tour, and prove by induction that it correctly outputs an Eulerian tour.
We start with a useful subroutine, FINDTOUR(G,s), which finds a tour (not necessarily Eulerian) in G. FINDTOUR is very simple: it just starts walking from a vertex s ∈ V , at each step choosing any untraversed edge incident to the current vertex, until it gets stuck because there is no more adjacent untraversed edge. We now prove that FINDTOUR must in fact get stuck at the original vertex s.
Claim: FINDTOUR(G,s) must get stuck at s.
Proof of claim: An easy proof by induction on the length of the walk shows that when FINDTOUR enters any vertex v ̸= s, it will have traversed an odd number of edges incident to v, while when it enters s it will have traversed an even number of edges incident to s. Since every vertex in G has even degree, this means every time it enters v ̸= s, there is at least one untraversed edge incident to v, and therefore the walk cannot get stuck. So the only vertex it can get stuck at is s. The formal proof is left as an exercise.
The algorithm FINDTOUR(G,s) returns the tour it has traveled when it gets stuck at s. Note that while FINDTOUR(G,s) always succeeds in finding a tour, it does not always return an Eulerian tour.
We now give a recursive algorithm EULER(G,s) that outputs an Eulerian tour starting and ending at s. EULER(G,s) invokes another subroutine SPLICE(T,T1,…,Tk) which takes as input a number of edge dis- joint tours T,T1,…,Tk (k ≥ 1), with the condition that the tour T intersects each of the tours T1,…,Tk (i.e., T shares a vertex with each of the Ti’s). The procedure SPLICE(T,T1,…,Tk) outputs a single tour T′ that traverses all the edges in T,T1,…,Tk, i.e., it splices together all the tours. The combined tour T′ is obtained by traversing the edges of T, and whenever it reaches a vertex si that intersects another tour Ti, it takes a detour to traverse Ti from si back to si again, and only then it continues traversing T .
The algorithm EULER(G,s) is given as follows:
Function EULER(G,s)
T = FINDTOUR(G,s)
Let G1,…,Gk be the connected components when the edges in T are removed from G, and let si be the
first vertex in T that intersects Gi
EECS 70, Fall 2021, Note 5 5
Output SPLICE(T,EULER(G1,s1),…,EULER(Gk,sk)) end EULER
We prove by induction on the size of G that EULER(G,s) outputs an Eulerian Tour in G. The same proof works regardless of whether we think of size as number of vertices or number of edges. For concreteness, here we use number of edges m of G.
Base case: m = 0, which means G is empty (it has no edges), so there is no tour to find.
Induction hypothesis: EULER(G,s) outputs an Eulerian Tour in G for any even degree, connected graph
with at most m ≥ 0 edges.
Induction step: Suppose G has m + 1 edges. Recall that T = FINDTOUR(G,s) is a tour, and therefore has even degree at every vertex. When we remove the edges of T from G, we are therefore left with an even degree graph with less than m edges, but it might be disconnected. Let G1,…,Gk be the connected components. Each such connected component has even degree and is connected (up to isolated vertices). Moreover, T intersects each of the Gi, and as we traverse T there is a first vertex where it intersects Gi. Call it si. By the induction hypothesis EULER(Gi,s) outputs an Eulerian tour of Gi. Now by the definition of SPLICE, it splices the individual tours together into one large tour whose union is all the edges of G, hence an Eulerian tour.
Sanity check! Why does Theorem 5.1 imply the answer to the Seven Bridges of Königsberg is no?
3 Planarity, Euler’s Formula, Coloring. Trees
We need to discuss trees briefly here, though we will discuss them more later. A graph is a tree if it is connected and acyclic (contains no cycles). There are many other equivalent definitions. For example, a tree is a connected graph where the number of vertices is one more than the number of edges. Or, a tree is a connected graph such that if you delete any edge it becomes disconnected.
internal nodes 4567
8 91011121314 15
Planar Graphs
A graph is planar if it can be drawn on the plane without crossings. For example, the first four graphs shown below are planar. Notice that the first and second graphs are the same, but drawn differently. Even though
EECS 70, Fall 2021, Note 5 6
the second drawing has crossings, the graph is still considered planar since it is possible to draw it without crossings.
The other three graphs are not planar. The first one of them is the infamous “three houses-three wells graph,” also called K3,3, (This notation says there are two sets of vertices, each of size three and all edges between the two sets of vertices are present.) The second is the “complete” graph (every edge is present) with five nodes, or K5. The third is the four-dimensional cube. We shall soon see how to prove that all three graphs are non-planar.
A useful concept is the notion of a bipartite graph, G = (V,E) which is a graph where the vertices are split into two groups and edges only go between groups. More formally, we have V = L ∪ R and E ⊆ L × R. Clearly, K3,3 is bipartite. Moreover, the four dimensional cube is bipartite: this follows from the fact that every cycle in the cube has even length. We will show the equivalence a bit later.
When a planar graph is drawn on the plane, one can distinguish, besides its vertices (their number will be denoted v here) and edges (their number is e), the faces of the graph (more precisely, of the drawing). The faces are the regions into which the graph subdivides the plane. One of them is infinite, and the others are finite. The number of faces is denoted f . For example, for the first graph shown f = 4, and for the fourth (the cube) f = 6.
One basic and important fact about planar graphs is Euler’s formula, v + f = e + 2 (check it for the graphs above). It has an interesting story. The ancient Greeks knew that this formula held for all polyhedra (check it for the cube, the tetrahedron, and the octahedron, for example), but could not prove it. How do you do induction on polyhedra? How do you apply the induction hypothesis? What is a polyhedron minus a vertex, or an edge? In the 18th century Euler realized that this is an instance of the inability to prove a theorem by induction because it is too weak, something that we saw time and again when we were studying induction. To prove the theorem, one has to generalize polyhedra. And the right generalization is planar graphs.
Can you see why planar graphs generalize polyhedra? Why are all polyhedra (without “holes”) planar graphs?
Theorem 5.2. (Euler’s formula) For every connected planar graph, v + f = e + 2
EECS 70, Fall 2021, Note 5 7
Proof. By induction on e. It certainly holds when e = 0, and v = f = 1. Now take any connected planar graph. Two cases:
• If it is a tree, then f = 1 (drawing a tree on the plane does not subdivide the plane), and e = v−1 (check homework).
• If it is not a tree, find a cycle and delete any edge of the cycle. This amounts to reducing both e and f by one. By induction the formula is true in the smaller graph, and so it must be true in the original
What happens when the graph is not connected? How does the number of connected components enter the formula?
Take a planar graph with f faces, and consider one face. It has a number of sides, that is, edges that bound it clockwise. Note that an edge may be counted twice, if it has the same face on both sides, as it happens for example in a tree (such edges are called bridges). Denote by si the number of sides of face i. Now, if we add the si’s we are going to get 2e, because each edge is counted twice, once for the face on its right and once for the face on its left (they may coincide if the edge is a bridge). We conclude that, in any planar graph,
∑si =2e. (1) i=1
Now notice that, since we don’t allow parallel edges between the same two nodes, and if we assume that there are at least two edges (so there are at least three vertices), every face has at least three sides, or si ≥ 3 for al