Compsci 225 2021 Notes, weeks 1-6
Above: schematics for the Voyager I space probe, which was launched on September 5th, 1977. It has sent signals back to NASA for over 43 years by using error-correcting codes, and is the most distant man-made object from Earth.
Compsci 225 Lecturer:
Chapter 0: About These Notes
Welcome to Compsci 225! This is a set of typeset notes I’ve been writing that are meant to serve as a companion to the first six weeks of lectures this term that I’m teaching.
Think of these notes as a slightly “remixed” version of the course- book; here, I’ve tried to adapt the material in the coursebook to the interests of Compsci 225 students (more examples, more de- tails in the proofs, less repetition of material from Compsci 120, more applications to the field of Computer Science). The main concepts covered should be broadly similar to that of the course- book, but we’ll depart from the coursebook in places where either the material it’s treating has already been done in Compsci 120, or where there’s an application or proof that’s just too cool to not mention 😀
If you have any questions, please email me at
In particular, let me know if you spot any typos! I’ll do my best to avoid them, but because I’m writing these notes in my spare time, they’re likely inevitable. (As a tiny incentive, I’ll give the first person to spot any mathematical typo a chocolate fish! Stop by office hours to claim your reward whenever you spot such a typo.)
Compsci 225 Lecturer:
Chapter 1: Graph Theory
1.1 How it started: the Bridges of Ko ̈nigsberg
Puzzle. The city of K ̈onigsberg was divided by the river Pregel into four parts: a northern region, a southern region, and two islands. These were connected by seven bridges, drawn in red at right.
Can you come up with a path through the city that starts and ends at the same place, and walks over each bridge exactly once?
1.2 How it’s going: circuits
Problem. You’re an electrical engineer. You’ve used a bread- board to design a prototype for a circuit. The breadboard cir- cuit is shown below; to help you visualize what’s going on if you haven’t worked with circuits before, a graph is drawn below that represents the same objects (4 LEDs, 4 buttons, 1 power source, 1 ground source) connected in the same way.
You’ve sent your prototype off to be turned into a printed circuit board (PCB) for production. A printed circuit board is essentially a board with wires “printed” onto it, which we call traces. Note that because of this process, we cannot have any wires “cross”; where our breadboard could have wires cross over each other be- cause we could physically put one wire above the other, with a PCB such a crossing would create a short-circuit. As a result, when you convert a breadboard circuit to a PCB, elements some- times need to be reordered.
You’ve been sent the following board, which we’ve translated into a graph (both drawn at right.) Can you plug in your objects into the slots on the PCB to get the same circuit as your prototype? Or is this impossible?
Problem. In the above, we had a circuit prototype with “cross- ing” wires. As noted above, if these wires are insulated and phys- ically separate, this isn’t a problem: however, if we’re making a PCB, this definitely is a problem, as crossings will cause short- circuits. When can we redraw a circuit to avoid crossings, and when are crossings inevitable?
More generally: if crossings are inevitable, we can get around this by “stacking” multiple circuit boards on top of each other. If we do so, we can draw different traces on different PCBs, and create a “book” of PCBs that embeds our circuit without crossings.
Given a circuit, how many PCBs do we need to stack to embed our circuit without any crossings?
A map of Ko ̈nigsberg, c. 1730.
slot1 slot2
slot3 slot5
slot4 slot6
ground power gate1 gate2 gate3
K5, drawn on 3 pages, with no crossings. Can you do this with fewer pages?
1.3 Overview
Historically, the K ̈onigsberg bridge problem above is the “first” problem in graph theory; to resolve it, (arguably the most prolific mathematician in history) invented the funda- mental ideas that allowed him and others to analyse objects and the connections between them. Originally, graph theory was seen as being a recreational branch of mathematics (think: 17/18th- century Sudoku) with few applications beyond coloring maps. In recent years, however, this perception has completely changed: our modern computer-based world is built on networks and con- nections, and graph theory is the perfect tool to attack critical problems in computer science and engineering.
In these notes, we’re going to build on the fundamentals you’ve developed in Compsci 120: graph theory language, the degree-sum formula, walks and connectivity, and some practice with writing graph theory proofs. With these skills at hand, we’re going to examine several uses of graphs in industry and computer science, and develop the mathematical tools and theorems you’ll want to approach problems like these later in your career!
These notes are just the tip of the iceberg; if you’re interested in further resources, books like ’s Graph Theory have an immense wealth of problems, theorems and applications. (Also feel free to talk to me; I love this stuff!)
1.4 Graph Isomorphism: Definition/Applications
Recall from Compsci 120 that a graph, by definition, is just a
collection of objects (vertices) along with a collection of unordered
distinct pairs of those objects (edges). In particular, the way in
which we draw a graph (i.e. where the vertices are drawn on a
page, or whether we draw our edges with straight lines or curves)
doesn’t matter: the only thing that matters is we have the same
objects on our page, and that each edge we’ve drawn has the same
starting and ending vertices. aa
So, for instance, the three length-5 cycle graphs drawn at right are all equal, even through they’re drawn differently: they both consist of the same objects, linked in the same order.
With that said, I claim that in your previous studies you’ve used a looser notion of “equality” when thinking about graphs. Consider the following three graphs:
On one hand, these graphs are all different: the first graph’s ver- tices are labeled with numbers, the second is labeled with letters, and the third is labeled with Pok ́emon! As such, these are differ- ent graphs. On the other, though, if we’d given you any of those graphs and asked you “what is the name of that graph,” you would
have said K5, the complete graph on 5 vertices1 for each of them. That is: even though these are nominally different graphs, we were giving them the same name in Compsci 120, and thinking of them as being fundamentally equivalent to each other in some sense (if not literally as the same objects.)
We make this notion rigorous with the following definition:
Definition. Two graphs G and H are isomorphic if they are identical “up to the names of their vertices:” that is, if we can transform G into H simply by changing the labels of the vertices.
The three graphs above are all isomorphic: by simply changing the labels of the vertices, we can transform any one of these graphs into any of the other two. As such, we are justified in thinking of them all as “K5” graphs, provided that by the complete graph on 5 vertices we’re thinking of any graph on 5 vertices in which all possible edges are drawn.
More generally in mathematics, “isomorphism” or “equivalence” is a concept we’ll use to group together objects that are the “same” up to some property (i.e. same up to labels, same up to colouring, same up to remainder mod 5, etc.) You’ll examine these properties more rigorously later on in this course! For now, let’s focus on why this is a practical and natural thing to care about.
When modelling real-life situations with graphs, we often don’t care about the precise names of the objects being connected; we simply care about the ways in which those connections take place. You’ve seen this already in these notes with our circuit prob- lem: there, we had two versions of a graph (one corresponding to our breadboard diagram, one corresponding to the PCB) and we wanted to determine if these graphs represented the same cir- cuit — i.e. if they were isomorphic! To illustrate that this is a fairly common phenomenon, here’s a selection of other practical instances of graph isomorphism:
You can think of a molecule as a graph, if you treat its atoms as vertices and consider the bonds between atoms to be edges. If you do so, then two molecules will have isomorphic molecular graphs if and only if the molecules are stereoisomers of each other (i.e. same atoms with same connections.)
A scan of a fingerprint can be represented by a graph, if we consider ridges to be vertices and connect two vertices if their corresponding ridges are adjacent or intersect. Given this, determining if two fingerprint scans represent the same finger is the same thing as determining if their corresponding graphs are isomorphic.
If you take a picture of a object, you can frequently use image analysis tools to decompose that object into various features (i.e. corners, parts with a given hue, etc) and from there turn that object into a graph (connect two features if they’re adjacent in the image.) If you do this, then deter- mining if two images represent the same object is the same as determining whether these image-graphs are isomorphic!
Given that graph isomorphism is both a practical and a natural concept, you might hope that this is something we can easily and
1If you’ve forgotten: the complete graph on n vertices consists of n vertices
and n edges, one connecting each distinct unordered pair of vertices. 2
Molecule graphs.
Two different pictures of the same tetrahedron. If you turn each image into a graph by thinking of corners as vertices, the resulting graphs are isomorphic!
quickly compute! Conversely, pessimists amongst you / people with some experience with graph and algorithms might expect that anything this useful is an NP-hard2 problem, and thus is very difficult as a rule.
Surprisingly, the answer is somewhere in between:
Remark. The graph isomorphism problem is the following task: given two graphs G,H on n vertices, is there an isomorphism between G and H?
Thus far in human history, there is no known polynomial-time algorithm to solve the graph isomorphism problem. People have gotten quite close to polynomial-time algorithms: the professor that taught me this material, L ́aszl ́o Babai, recently released work that has “quasipolynomial” runtime3 and solves the graph isomor- phism problem. However, no polynomial time algorithm is known in general that can tell you whether two graphs are isomorphic.
At the same time, however, this problem isn’t known to be a NP-complete! Very closely related tasks are known to be NP- complete: the subgraph isomorphism problem, which gives you two graphs G, H and asks you if any subgraph4 of G is isomorphic to H, is NP-complete. However, just asking straight-up if two specific graphs are isomorphic is not known to be NP-complete.
1.5 Graph Isomorphism: Examples and Nonex- amples
As you might expect from the above, in general, the fact that the same graph can be drawn in radically different ways can make it quite difficult to intuitively “tell” if two graphs are isomorphic or not. Consider the following two graphs:
Visually, these graphs look nothing alike: however, they actually turn out to be isomorphic! The animation linked here is a great
2A quick refresher, if you haven’t seen computational complexity before: roughly speaking, a problem is said to be in the complexity class P if there is an algorithm that solves instances of that problem of size n with a runtime that can be measured as a polynomial of n. So, for instance, the task “find the largest degree of a vertex in a graph” is in P: we just need to go through all vertices in G and record the largest one. Conversely, a problem is said to be in NP if there is an algorithm that can verify whether a claimed solution to a problem is true with polynomial runtime: for example, checking if a filled-in n × n Sudoku grid is a valid solution can be done in polynomial time (check all rows/cols/subsquares.) A problem is said to be NP-hard if any algorithm to solve that problem can be adapted to solve literally every problem that’s in NP. With few exceptions, most true-false problems we’ve found have been either in P or have been NP-hard. A massive open problem, arguably the biggest in science, is determining whether P = NP; that is, whether any problem whose solution can be verified quickly can be solved quickly!
3Specifically, a runtime of 2O((log n)c).
4Recall that we say that A is a subgraph of G if we can create A by taking G and removing extra vertices/edges/etc in some manner.
way to visualize this: it shows you how to bend the first graph around in space so that it becomes the second graph.
In general, animations (or step-by-step diagrams) are a good way to show that two graphs are isomorphic: if two graphs are iso- morphic, then (ignoring the vertex names) there should be some way to stretch/move any drawing of the first to transform it into a drawing of the second. To give a example that we draw ourselves, let’s look at the following two graphs:
I claim that these are isomorphic! To see why, let’s just move the vertices of the leftmost graph around until it has the same configuration as the rightmost graph:
While I generated this image via Inkscape, you can do much the same with screenshots of apps like this one.
Determining when two graphs are not isomorphic can be much trickier. Where showing that two graphs are isomorphic is very much a constructive sort of proof — you create a specific way to relabel vertices — claiming that no such isomorphism exists involves showing that something is impossible, and thus requires different proof techniques.
1.6 Showing graphs are not isomorphic
Sometimes, it can be easy to show that two given graphs are nonisomorphic:
Observation. If G and H have different numbers of vertices, then they are not isomorphic.
Observation. If G and H have different numbers of edges, then they are not isomorphic.
Observation. If there is a value k such that G and H have dif- ferent numbers of vertices with degree k, then they are not iso- morphic.
For example, we can immediately see that none of the graphs at right are isomorphic to each other. The first graph is on 5 vertices, while the other two are each graphs on 6 vertices; the
Three nonisomorphic graphs.
second graph contains 8 edges, while the others contain 7; the third graph contains a vertex of degree 4, while the others do not.
However, these properties are not enough to determine if two graphs are isomorphic! Consider the graphs from our circuit ex- ample to start the chapter:
slot1 slot2
These graphs both contain 9 edges, 6 vertices, and all of the ver- tices in these graphs are degree 3. Despite this, they are not isomorphic! To see why, we need to consider more complex prop- erties. We close this chapter by introducing two such properties, both of which are quite interesting and applicable in their own right. The first of these relates back to our circuit problem and desire to draw a graph “without crossings:”
1.7 Planarity
Definition. We say a graph G is planar if we can draw it in the plane so that none of its edges intersect.
Note that a graph can be planar even if a given drawing of that graph has edges that cross. For example, the graph drawn in the margins at right is just K4, which in the past we’ve drawn with
crossing edges as . For a graph to be planar all we need is that there is some way to draw that graph without crossing edges.
A useful concept to keep in mind when working with planar graphs is the idea of a face:
Definition. For any drawing of a connected planar graph G, we f1 define a face of G to be a connected region of the plane whose
boundary is given by the edges of G. f2
For example, the graph we’ve drawn in the margins has four faces, labeled f1, f2, f3, f4. Notice that we always have the “outside” face in these drawings, which can be easy to forget about when drawing our graphs on the plane.
It bears noting that not all graphs are planar. For example, in the Compsci 120 coursebook’s chapter on graph theory, we proved that K3,3 is nonplanar!
Relatedly, this fact can answer our circuit isomorphism question from earlier: the breadboard graph we drew is a K3,3, i.e. com- plete bipartite graph5 on 3,3 vertices, if you consider the three gates to be one set of 3 vertices and the ground/power/led trio to be the other set of three vertices. Because K3,3 is nonplanar, we cannot embed this circuit on a single PCB withour crossings, and thus the given PCB graph must be different than our original graph.
As a refresher, let’s use a similar approach to prove that a different graph is nonplanar:
5The complete bipartite graph Kn,m is formed by putting n vertices in one group, m vertices in a second group, and for each vertex in the n group, drawing an edge connecting it to each vertex in the m group.
ground power gate1 gate2 gate3
slot3 slot4 slot5 slot6
Claim. The graph K5 is nonplanar.
Proof. We proceed by contradiction; that is, we assume that there is some planar way to draw K5, and make a sequence of logical deductions from there that lead us to something we know must false (i.e. 1=0 or something like that.) Because true things cannot imply false things, this must mean that our original assumption is flawed: i.e. that K5 cannot be planar.
To get such a contradiction, we first notice that K5 contains a “pentagon,” i.e. a C5, given by its outside edges. Therefore, in any drawing of K5, we will have to draw this cycle C5.
Because this cycle is a closed loop, it separates space into an “inside” and an “outside.” Therefore, if we are creating a planar drawing after drawing this C5, any remaining edge will have to either be drawn entirely “inside” the C5 or “outside” the C5. That is, we can’t have an edge cross from inside to outside or vice-versa, because that would involve us crossing over pre-existing edges.
Therefore, if we have a planar drawing of K5, after we draw the C5 part of this graph, when we go to draw the {a, c} edge we have two options: either draw this edge entirely on the inside of our C5, or entirely on the outside.
If we draw this edge on the inside, then on the inside the vertices b and d are separated by this edge; therefore, to draw the edge {b, d} we must go around the outside. Similarly, if we draw this edge on the outside, then b,d are separated from each other on any outside path, and the edge {b, d} must be drawn inside of the pentagon.
Similarly, the edge {b,e} is forced to be drawn on only one side by our previous choices:
Similarly, the edge {a,d} is forced to be drawn on only one side by our previous choices:
In either of these cases, notice that there is no path that can be drawn from b to e on either the inside or the outside! Therefore we cannot draw our last edge {c, e} without breaking our planar condition, and thus have a contradiction to our claim that such a planar drawing of K5 was possible.
If you are skeptical of the above proof, get a pen and paper and draw out the steps we’ve gone through! In general, it’s a lot easier to understand most graph theory arguments if you’re drawing examples alongside the proofs at the same time.
Planar graphs have many beautiful properties. One particularly elegant invariant is the Euler characteristic:
Theorem. (Euler characteristic.) Take any planar drawing of a connected graph G. Then, if V is th