this spring i came across introduction to graph theory by richard j. trudeau, a wonderful little book on the basics of graph theory. honestly, if i were to suggest a few books to younger me, this would definitely be on that list. the prerequisites are none, yet trudeau is able to build up quite a bit of the beautiful structure of graphs, touching on planarity, euler’s formula, colorings and more. admittedly, this wouldn’t serve as a sole reference on the subject, but it does serve its intended purpose as an introduction.
one striking feature of the theory of graphs of which i was unaware is kuratowski’s theorem:
kuratowski’s theorem: every nonplanar graph is a supergraph of an expansion of UG or K5.
backing up a bit, a planar graph is one that can be drawn in the plane with no edge crossings. the utility graph, which trudeau denotes as UG is one such example and comes from that problem asking if you can route three utilities to three houses without crossing any lines1. on the other hand K5 is the complete graph of five vertices; it’s complete in the sense that each vertex is adjacent to the other four2.
what kuratowski’s theorem shows, then, is that any nonplanar graph—any graph you can think of that has one or more edge crossings 3—has UG or K5 as its ancestor. in some sense, these two nonplanar graphs are the most fundamental of the nonplanar graphs and function as the building blocks for all nonplanar graphs, no matter how complex or contrived. truly remarkable!
one of my takeaways from this theorem along with trudeau’s proof of euler’s formula is that it’s often useful to augment graphs to build up new ones, very akin to induction. if you take care to augment a graph in a way that maintains some invariant, you can prove some key results or at least find a new way to think about a problem.
in any case / in that spirit, i try to learn some html / css / javascript here and there4 and so i tried to build a little interactive that let’s you build your own graph, which you can find here. i threw it together by adapting this visualization by mike bostock5.
-
this is also called K3,3 the complete bipartite graph. ↩︎
-
a graph H is a supergraph of a graph G if G is a subgraph of H. since that’s a little lacking: a graph G is a subgraph of a graph H if G’s vertex set is a subset of H’s vertex set and G’s edge set is a subset of H’s edge set. neither subset must be proper; indeed every graph is a subgraph of itself.
a graph H is an expansion of a graph G if you can construct H by adding zero or more vertices of degree 2 to some of the edges of G. when we expand a graph we are splicing vertices into existing edges, although it’s perfectly fine if we do nothing to the graph. like with subgraphs, every graph is an expansion of itself. ↩︎
-
technically, this isn’t entirely sufficient, for you can draw a planar graph with edge crossings, although it won’t inherit from UG or K5. however, it can be “untangled”, so to speak, and redrawn with the same number of vertices and with the same adjacencies but with no edge crossings. in formal mathematics, we typically talk about these types of relationships as isomorphisms. a planar graph with edge crossings is always isomorphic to a planar graph with no edge crossings, which is really what we’re talking about here and is also what makes it so difficult to prove if a graph is truly nonplanar (think: how can you verify that a graph that has edge crossings cannot be redrawn without any?). one of the applications of kuratowski’s theorem, then, is that it provides us an “easy” way to determine if a graph is nonplanar: given a graph G it suffices to show that G has a subgraph that is isomorphic to an expansion of UG or K5. ↩︎
-
read: i’m bad at all three. ↩︎