The 4th annual π day anime and mathematics post: Traveling teacher time

Korosensei is fast, but can he do better?

Korosensei is fast, but can he do better?


Korosensei can move at Mach 20 and takes advantage of this fact to make frequent trips around the world. Obviously, in the interest of efficiency, he often takes the opportunity to make multiple stops per trip. But what is the most efficient way for him to do so?

We can think about this using graphs. Suppose all the possible destinations are vertices and edges with costs connect the vertices, representing the cost of traveling from some destination $u$ to another destination $v$. At first glance, it might make sense to use physical distance in our case, but that is not necessarily a measure of the “best” way to get there. For instance, taking a bus or train between two cities may get you to the same place, but the actual cost depends on the path that’s taken and you may choose to include other criteria like the cost of tickets and other stuff like that.

So the problem is this: Korosensei has a list of places he wants to hit up during lunch hour. What is the most cost-effective way of getting to each of those places exactly once and get back to school? This is what’s known as the Traveling Salesman problem (TSP).

As it turns out, this problem, like many graph theory problems, is NP-complete, meaning it’s quite computationally hard and taxing for computers to solve. Formally, if we’re given a graph $G = (V,E)$ and a cost function $d: V \times V \to \mathbb R$, the problem is to find a cycle that visits every vertex exactly once with smallest possible cost. Usually, if we have $n$ vertices, then $G$ is the complete graph on $n$ vertices, that is, a graph where every vertex has an edge to every other vertex. Otherwise, it may not be possible to find such a cycle (and the problem of finding such a cycle is also an NP-complete problem, Hamiltonian cycle).

It’s called the Traveling Salesman problem because the idea is that if you’re a traveling salesman, you’d want to find that least-cost cycle because it’d be the most cost-effective way to hit up all the cities you need to go to in order to sell whatever it is that you’re selling. Of course, the hardness of the problem means that our poor salesman or Korosensei are stuck having to check the cost of every cycle. How many are there? Well, since we’re dealing with a complete graph, this means we can get to any vertex from any vertex so we can take any permutation of our vertices and that’s a cycle, and there are $n!$ permutations. This means that as $n$ gets larger, the difficulty of solving this problem grows exponentially.

One way we can attempt to make NP-complete problems feasible to solve is to loosen our demands a bit. Right now, we want the absolute least-cost cycle, but what if it’s not necessary for us to get the least cost cycle? What if we’re okay with getting something that’s within a factor of 2 or 3 or $f(n)$ for some function $f$ that depends on the size of the input? These are called approximation algorithms, in that they approximate the optimal solution by some factor. Unfortunately this doesn’t work for TSP.

Why? Because if I have a feasible algorithm for approximating TSP, then I’ve got an efficient algorithm for solving Hamiltonian cycle, which I mentioned was also NP-complete. Suppose I take any old graph $H$ with $n$ vertices and turn it into a complete graph with all my original edges having cost 1 and any new edges I add having cost $\rho \cdot n + 1$. If I do have some approximation algorithm that gives me a solution within a factor of $\rho$, I’ll run it and get a cycle for Korosensei to use. But, based on the cost of the cycle I get, I can tell if my original graph had a Hamiltonian cycle: if it has cost $\leq n$, then that means it found a Hamiltonian cycle using all of the edges in my original graph. Otherwise, we get a cycle with cost at least
$$(\rho \cdot n + 1) + (n-1) = \rho \cdot n + n > \rho \cdot n$$
meaning it must’ve used one of the new expensive edges I added and so we know the original graph didn’t have a Hamiltonian cycle.

Now this is a bit discouraging, but Korosensei would encourage us to keep on thinking about how to assassinate the hell out of this problem. In the most general case, the cost function $d$ has no constraints and the way that I’ve initially motivated Korosensei’s problem, $d$ can be arbitrary, with costs adjusted to his needs. However, some of the attempts to make TSP more computationally feasible have to do with making some reasonable restrictions on our cost function. This is another fairly standard approach to making computationally hard problems easier to deal with: figure out some cases of the problem that are still useful but might help to simplify or restrict the problem a bit.

For example, in most cases, it’s a reasonable expectation that if you’re going from $u$ to $v$, it’s best to go there directly rather than stopping at $w$ on your way there. This is what we call the triangle inequality:
$$d(u,v) \leq d(u,w) + d(w,v).$$
It’s called the triangle inequality because of what I just described: draw a triangle out of $u$, $v$, and $w$ and the distance between any two should be shorter than going through the third point.

I say should because for an arbitrary cost function, this isn’t always the case. One example is flight pricing. Sometimes, it’s more expensive to fly from $u$ to $w$ than it is to fly from $u$ to $v$, even if the flight stops over at $w$. Anyhow, Korosensei doesn’t have to deal with silly things like flight pricing and so we impose this reasonable triangle inequality condition on his cost function. Does it help? It turns out it does and we can get an approximation that’ll be at most twice the cost of the optimal solution.

How? Well, first we find a minimum spanning tree. A spanning tree of a graph is a tree (a graph that contains no cycles) that connects all of the vertices of a graph together. The minimum spanning tree is the spanning tree with the least weight out of all the spanning trees. The nice thing about MSTs is that we know how to do this efficiently.

Once we have our MST $T$ of our graph $G$, we double up every edge in $T$ to get a cycle $T’$. This cycle what we want yet, since it travels along all the same edges and goes to each vertex twice. But, we can get the cycle we really want by removing all of the second times we visit a vertex and we can do this because the triangle inequality tells us that by taking a more direct route, the cost of the cycle won’t increase. So now if we have our cycle $C$, then we have
$$cost(C) \leq cost(T’) \leq 2 \cdot cost(T).$$

Now, to compare to the cost of our actual optimal solution $C^*$, we notice that taking out some edge of $C^*$ makes it a spanning tree. It’s not necessarily minimal, so we’ve got
$$cost(T) \leq cost(C^* \setminus \{ e \}) \leq cost(C^*).$$
Putting that all together, we’ve got
$$cost(C) \leq cost(T’) \leq 2 \cdot cost(T) \leq 2 \cdot cost(C^*)$$
and there’s our 2-approximation.

Given how fast Korosensei is, this is probably good enough for him and is a decent tradeoff between the time it takes to solve the problem and his actual travel time.

The fourth annual π/ホワイト day animaths appreciation post

Qualia 8

Let us celebrate this day with Nadeko.

Okay, now let’s figure out what the hell Alice is trying to claim. Alice can solve equations by turning them into pictures and solve them instinctively like that. What implications does this have?

First, we probably want to talk about what the P/NP problem is. In computational complexity, we talk about the complexity of problems and we measure this as the amount of resources we need to solve a problem. The two most common measures are for time and space. That is, roughly the amount of time it takes to solve a problem or the amount of space (so, like memory) that’s required to solve a problem. This is expressed as a function of the size of the input.

Formally, all of this stuff is defined in terms of Turing machines, but we don’t need that level of specificity. Intuitively, we can think of P as the class of problems which we can solve in a reasonable amount of time (or “efficiently”) and NP as the class of problems for which we can verify the correctness of a given solution in a reasonable amount of time. By reasonable, we mean that the amount of time it takes scales reasonably depending on the size of the input or problem we want to solve.

The P/NP problem asks whether P is equal to NP. If you think about it for a bit, it seems kind of intuitive that those two classes shouldn’t be equal. It’s a lot easier to figure out whether an answer to a problem is correct than it is to find a correct answer. And most computer scientists also agree that that’s probably the case. The hard part is actually proving it, which no one has been able to do since 1971, when U of T’s Stephen Cook first formulated the problem.

The classical NP-complete problem is the satisfiability problem. If I have a boolean formula, is there an assignment of true/false values that makes the formula evaluate to true? Testing this is easy: if you give me an assignment that you claim works, I can check it in the amount of time it takes to look at each variable. Trying to come up with an assignment is a lot trickier. The easiest thing to do is try trial and error, but that could take an exponential amount of time. Of course, there are a lot of fancy tricks we’ve come up with for this problem, but we still have no way of solving this problem in a way that we can say is theoretically efficient (whether it’s the case for practical uses is a different matter).

What’s baffling about P/NP is that the idea is rather simple to prove or disprove. We have these notions of hardness and completeness which allow us to reduce problems to other problems. In particular, the class of NP-complete problems are those problems which are called NP-hard and contained in the class NP. These problems have the property of being able to reduce to any other NP-complete problem.

A reduction basically says that two problems are about as computationally hard as each other. The idea is that if I have some problem I want to solve but I don’t know how to do it, I can transform it (with a reasonable amount of time) into some other problem that I hypothetically do know how to solve. The reasoning is that if I can do that, then I know that the problem I wanted to solve takes about as much resources to solve as the problem I already know how to solve. And it’s pretty remarkable, then, that every NP-complete problem has this property of being able to reduce to any other one.

So the way to prove that P=NP is to figure out a way to solve any NP-complete problem in polynomial time. Since every NP-complete problem reduces to every other one, you just have to choose your favourite (read: easiest) NP-complete problem out of the several thousand that we know of and figure out an efficient algorithm for it. Because of the reducibility property, if you solve one efficiently, you’ve basically solved them all efficiently. This means that all problems in NP can be solved efficiently and it turns out P=NP. And yet, no one has been able to come up with an efficient algorithm for any NP-complete problems.

On the other hand, while at this point it’s pretty obvious that P≠NP, we have no idea how to prove it. The field of computational complexity and all the tools that we’ve developed over the last few decades are all interesting and useful, but they were all in an attempt to show that P≠NP and so far, nothing we’ve thrown at it has stuck. In fact, we’ve ended up creating a lot more questions that seem to have interesting structures and intuitive answers but we still have no way of proving a lot of these conjectures.

Of course, in the last decade or two, there’s been a lot of focus on quantum computing and with the rise of quantum computing, quantum complexity theory. It’s commonly believed that quantum computing gives us exponential speedup and allows us to solve NP-complete problems in polynomial time.

Well, it doesn’t.

The idea is that since you have a bunch of states in superposition, you also have all possible outcomes stored in those states. Unfortunately, it doesn’t work like that and there are a bunch of complications that arise in trying to extract outcomes of computations stored in qubits that render this whole point moot.

There’s nothing inherent in quantum computing that brings us closer to actually resolving questions that we have about the complexity hierarchy we’ve defined. In fact, quantum computations can be simulated on classical computers in exponential time, so it’s not like there’s nothing we don’t already know about computation, we can just certain kinds of computations faster.

And just like the other tools we’ve developed in computational complexity to try and resolve this question, quantum computing throws another wrench into the problem by introducing quantum analogues of classical complexity classes. Some of these, like QIP, the class of problems solvable by quantum interactive protocols, turn out to have no additional power (it was proved in 2010 by Jain, Ji, Upadhyay, and Watrous that QIP = IP). And some, like BQP, the class of problems solvable in bounded-error polynomial time, have the same problem where we’re not entirely sure how it relates to the other classes.

So knowing all of this, what does Alice’s claim mean exactly? Unsurprisingly, it doesn’t mean anything. If Alice can solve equations intuitively by drawing pictures, then she can probably already solve PSPACE-complete problems (since there are equation problems which are known to be in PSPACE), which means that it doesn’t even matter whether or not she has access to a quantum computer, since she can already solve problems harder than the ones in the quantum analogues of P and NP.

The lesson here is that little girls would not necessarily make very good mathematicians even if they can compute computationally intractable problems (this is basically what Gödel’s incompleteness theorems say too).

World End Economica episode 1: Quantitative Analysis 101

A long time ago, I was searching for news about the newest Kishida Kyodan and the Akeboshi Rockets album, POPSENSE. POPSENSE came with a bunch of these funny little blue-haired faces, one of which was the album cover. One of these faces was noticeably different, having black hair and red eyes. It turns out that was supposed to be Hagana, one of the main characters from World End Economica and it turned out that the OP track was on this album.

That’s how I found out about World End Economica, which was a weird-sounding title and surely couldn’t have had anything to do with economics. But I was wrong, because it so happened that it was written by a certain Isuna Hasekura, who was responsible for everyone’s favourite wolf goddess medieval mercantile adventure. This was exciting to learn about until I realized that it was never going to be translated because it was a doujin visual novel. I shouted into the wind on twitter and magically received a response:

So now it’s been almost a year later and finally available for purchase with my hard earned yencoins so I can actually read it. Is there anything to it beyond economics on the moon? Why, yes, in fact, there is.

World End Economica is about quantitative analysis.

Our story begins in the grand moon city with a young vagrant, Yoshiharu, who’s pretty good at trading and has an intuition for it. At this point I’m wondering how the hell human civilization managed to build a financial centre on the moon but it’s still possible for someone to succeed at trading manually. And the story answered with Hagana, an incredibly socially awkward girl whose only skill is being amazing at math and is distraught because math is actually totally useless in the real world.

You might be able to see where this is going. Quantitative analysis is what we call the application of mathematics to finance. The idea is to take into account all of the data on the market and somehow model it so that you can predict and optimize when you buy and sell various stocks, how much of each stock, and at what rate. And of course, when you’re dealing with this much data and this many calculations, you’ll need to get a computer to do all of this for you and you can get computers to automate trading for you. This automation is what’s called algorithmic trading, where you essentially rely on computers and algorithms to figure out and do stuff automatically.

Because of how well it’s able to optimize profits and how quickly it gets data and processes it, it’s how a significant amount of trading goes on today. As a result, the market becomes a giant feedback loop of inputs going into these algorithms. The algorithms process this stuff and make decisions and take actions and generates a whole new set of data to be fed back into the algorithms again.

Now, this is great for all the mathematicians and computer scientists out there because all of a sudden, there’s another career track that’s opened up that’s willing lure us away from academia with large bags of money. But then the question is that once algorithms are doing all the trading, what do the traders do? This is something that I don’t have an answer to because I don’t really know that much about finance.

This also turns out to be a question that our MC asks himself too. He’s managed to help this girl discover that her talents aren’t a waste and that she can use them to help people. But in the course of using and developing her skills, she’s basically making bank and obsoleted him out of nowhere. So, is there a role for people in trading and finance if computers can do it all?

And that could be a pretty frightening question if you think about it. We’re used to robots replacing people for menial labour because they’re stronger or more efficient and better at doing rote tasks. But now, we’re able to replace traders with computers. And if you think about that for a bit, you realize that these algorithms fighting it out on the market are responsible for a huge chunk of wealth in the world right now.

And that brings us to the other question, which is can we trust the computer? Obviously, someone has to know how to transform the processes and data so that it can be shoved into a computer, but once we have something complex enough, it kind of morphs into a magical box. There’s no way to verify that this thing you’re feeding a ton of data is doing the right thing. So when your gut and the box are in conflict, which do you trust when you have tons of peoples’ money on the line?

Unfortunately, this is only episode 1 so I have to wait an unspecified amount of time before Spicy Tails decides to translate and release the next installment to find out where this is going. So far, it’s been intriguing enough for me to stick around, even though the art and music are fairly sparse and the editing could use some work. I guess the answer to getting my attention is to write a story about math.

The 3rd annual π day anime and mathematics post: A symmetric group of friends of degree 5


It’s that day of the year again.

Kokoro Connect’s premise made a lot of people raise their eyebrows, because really, what good can come from body-switching shenanigans? Well, let’s think about this for a second. We have a group of five kids and every once in a while, at random, they switch into the others’ bodies at random. What does that sound like? That’s right, a permutation!

Interestingly enough, the idea of connecting body-switching with permutations isn’t new. The Futurama writers did it and apparently got a new theorem out of it. What differs in the case of Kokoro Connect and Futurama is that in Futurama, the body-switching could only happen in twos. These are called transpositions. Obviously, this isn’t the case for Kokoro Connect. This doesn’t make too much of a difference since it turns out we can write out any permutation we want as a series of transpositions, but that wouldn’t be very fun for Heartseed.

We write permutations in the following way. If we let Taichi = 1, Iori = 2, Inaban = 3, Aoki = 4, and Yui = 5, we’ll have $(1 2 3 4 5)$ representing the identity permutation, when everyone’s in their own body. If Heartseed wanted to make Aoki and Yui switch places, he’d apply the following permutation
$$ \left( \begin{array}{ccccc} 1&2&3&4&5 \\ 1&2&3&5&4 \end{array} \right) $$
While it’s helpful for seeing exactly what goes where, especially when we start dealing with multiple permutations, this notation is a bit cumbersome, so we’ll only write the second line ($(12354)$) to specify a permutation.

For the purposes of this little exercise, we’ll consider applying a permutation as taking whoever’s currently in a given body. That is, say we permute Aoki and Taichi to get $(4 2 3 1 5)$. In order to get everyone back into their own bodies, we have to apply $(4 2 3 1 5)$ again, which takes Aoki, who’s in Taichi’s body, back into Aoki’s body.

So let’s begin with something simple. How many different ways are there for the characters to body switch? Both who is switched and who they switch with is entirely random. Again, since the switches aren’t necessarily transpositions, this means that we can end up with cycles like in episode 2, when Yui, Inaban, and Aoki all get switched at the same time. This can be written as $(1 2 4 5 3)$.

But this is just the number of permutations that can happen on a set of five elements, which is just 5! = 120. Of course, that includes the identity permutation, which just takes all elements to themselves, so the actual number of different ways the characters can be swapped is actually 119.

Anyhow, we can gather up all of these different permutations into a set and give it the function composition operation and it becomes a group. A group $(G,\cdot)$ is an algebraic structure that consists of a set $G$ and an operation $\cdot$ which satisfy the group axioms:

  • Closure: for every $a$ and $b$ in $G$, $a\cdot b$ is also in $G$
  • Associativity: for every $a$, $b$, and $c$ in $G$, $(a\cdot b)\cdot c = a\cdot (b\cdot c)$
  • Identity: there exists $e$ in $G$ such that for every $a$ in $G$, $e\cdot a = a \cdot e = a$
  • Inverse: for every $a$ in $G$, there exists $b$ in $G$ such that $a\cdot b = b\cdot a = e$

In this case, we can think of the permutations themselves as elements of a group and we take permutation composition as the group operation. Let’s go through these axioms.

Closure says that if have two different configurations of body swamps, say Taichi and Iori ($(2 1 3 4 5)$) and Iori and Yui ($(1 5 3 4 2)$), then we can apply them one after the other and we’d still have a body swap configuration: $(2 5 3 4 1)$. That is, we won’t end up with something that’s not a body swap. This seems like a weird distinction to make, but it’s possible to define a set that doesn’t qualify as a group. Say I want to take the integers under division as a group ($(\mathbb Z, \div)$). Well, it breaks closure because 1 is an integer and 2 is an integer but $1 \div 2$ is not an integer.

Associativity says that it doesn’t matter what order we choose to apply our operations in. If we have three swaps, say Taichi and Inaban ($(3 2 1 4 5)$), Aoki and Yui ($(1 2 3 5 4)$), and Iori and Yui $(1 5 3 4 2)$ and we want to apply them in that order. Then as long as they still happen in that order, it doesn’t matter which one we apply first. We’d have
$$((32145)(12354))(15342) = (32154)(15342) = (34152)$$
$$(32145)((12354)(15342)) = (32145)(14352) = (34152)$$

The identity means that there’s a configuration that we can apply and nothing will change. That’d be $(12345)$. And inverse means that there’s always a single body swap that we can make to get everyone back in their own bodies.

As it turns out, the group of all permutations on $n$ objects is a pretty fundamental group. These groups are called the symmetric groups and are denoted by $S_n$. So the particular group we’re working with is $S_5$.

So what’s so special about $S_5$? Well, as it turns out it’s the first symmetric group that’s not solvable, a result that’s from Galois theory and has a surprising consequence.

Évariste Galois was a cool dude, proving a bunch of neat stuff up until he was 20, when he got killed in a duel because of some drama which is speculated to be of the relationship kind, maybe not unlike Kokoro Connect (it probably wasn’t anything like Kokoro Connect at all). Among the things that he developed was the field that’s now known as Galois theory, which is named after him. What’s cool about Galois theory is that it connects two previously unrelated concepts in algebra: groups and fields.

One of the most interesting things that came out of Galois theory is related to the idea of solving polynomials. I’m sure we’re all familiar with the quadratic formula. Well, in case you aren’t, here it is:

$$x = \frac{-b \pm \sqrt{b^2 – 4ac}}{2a}$$

This neat little formula gives us an easy way to find the complex roots of any second degree polynomial. It’s not too difficult to derive. And we can do that for cubic polynomials too, which takes a bit more work to derive. And if we want to really get our hands dirty, we could try deriving the general form of roots for polynomials of degree four. And wait until you try to do it for degree five polynomials.

That’s because, eventually, you’ll give up. Why? Well, it’s not just hard, but it’s impossible. There is no general formula using radicals and standard arithmetic operations for the roots for any fifth degree (or higher!) polynomial. The reason behind this is because $S_5$ is the Galois group for the general polynomial of degree 5. Unfortunately, proving that fact is a bit of a challenge to do here since it took about 11 weeks of Galois theory and group theory to get all the machinery in place, so we’ll have to leave it at that.

The 2nd annual π day anime and mathematics post


Happy $\pi$ day. Once again, Nadeko will bring us in:

Snowy Mountain Syndrome is the third story in The Rampage of Haruhi Suzumiya, the fifth volume of the light novel. It’s the first story that has yet to be animated. It’s also a story that contains the dread spectre of mathematics.

So our SOS-dan is stuck in a mysterious cabin in the middle of a snowstorm on a mountain. They find a mysterious contraption that has an equation displayed:


and they are to provide $x$, $y$, and $z$. Koizumi and Kyon are confused, but Haruhi rightly identifies this equation as Euler’s polyhedron formula, which is also very often referred to as just Euler’s formula. If you’re referring to it in context, it doesn’t matter that much, but it’s useful to distinguish between all the other things that Euler discovered, which is a hell of a lot.

First, we should probably go over some basic definitions. When we talk about graphs, we’re not talking about bar graphs or pie charts or the like. We’re also not talking about graphs of polynomials on a cartesian plane or other such functions. Graphs are a mathematical structure which, when drawn, looks like a bunch of circles and lines.

Formally, a graph is a pair $G = (V,E)$ where $V$ is a set of vertices and $E$ is a set of edges. Vertices can be any old thing, but each edge is defined as a pair $(u,v)$ where $u$ and $v$ are vertices in $V$. When we draw graphs, we just draw a vertex as a circle and draw an edge as a line that connects the two vertices it’s defined as.

And that’s it! That’s the most general definition of a graph, which means we can end up with a graph that’s completely empty or a graph that’s just a bunch of vertices with no edges in between them. We can even have multiple edges going in between two vertices. Of course, often times, we’d like to add some more constraints, depending on what we want to do with our graphs. Very often, we’d like to restrict the number of edges between two vertices to one and that’s what we’ll do.

Back to the formula, usually it’s given as $\chi=v-e+f$, where $v$ is the number of vertices, $e$ is the number of edges, $f$ is the number of faces, and $\chi$ is called the Euler characteristic. That makes $x=v$, $y=e$, $f=z$ and $D-1=\chi$. Now, the only thing here that we haven’t seen defined yet is a face. Intuitively, we can see that’s just the space that’s bounded by the edges.

What I find strange is the explanation in the novel that $D$ stands for the dimension of the polyhedra. As far as I know, this only works in the three-dimensional case for platonic solids. Once we generalize the structures to other kinds of polyhedra and topological surfaces, that analogy breaks down.

Anyhow, the way the formula is applied in the book is the use that I’m most familiar with, which is as a property of a planar graph. For planar graphs, $\chi=2$. In the novel, they deduce that $\chi=1$ since $D=2$ and that only works because they didn’t count the large face outside of the edges as a face, which we usually do.

But what is a planar graph? Well, if you go back to our definition of a graph, you might notice that all we’ve done is said that it’s a bunch of vertices and edges. We’ve said nothing about how to draw a graph. Usually, we represent vertices as circles and edges as lines in between those circles, but other than that, there’s really nothing telling you what order to draw your circles in or whether your lines have to be completely straight or not or how far apart everything has to be. How you choose to represent your graph is up to you, although if you draw your graph weirdly, you might make the people trying to read it angry.

Informally, a planar graph is a graph that you can draw with none of the edges crossing each other. This seems like a kind of silly thing to be worried about, because it seems like you could just keep on drawing a graph until it works out. Well, for edges with a lot of vertices and edges, it’s not obvious and even for really small graphs. For instance:

At a glance, it doesn’t look like the drawing on the right is planar, but all we have to do is drag one of the vertices into the middle to get the drawing on the left and it turns out they’re both the same graph, $K_4$, the complete graph of order 4.

That’s where Euler’s formula comes in really handy. It gives us a way of figuring out whether or not our graph is planar or not without having to fiddle around with placing edges properly and stuff. You already know how many vertices and edges you’ve got, so all you need to do is make sure you’ve got the right number of faces.

So it’s probably pretty clear at this point that you can’t draw every graph without the edges crossing. We can say something interesting about those graphs too, which just turns out to be another characterization of planar graphs, but oh well. But first, we have to introduce the concept of graph minors.

Suppose we have a graph $G=(V,E)$ and an edge $e=(u,v) \in E(G)$. If we contract the edge $e$, we essentially merge the two vertices into a new vertex, let’s call it $w$, and every edge that had an endpoint at $u$ or $v$ now has $w$ as the corresponding endpoint. Then a graph $H$ is a graph minor of $G$ if we can delete and contract a bunch of edges in $G$ to get $H$ (or a graph that’s isomorphic to $H$).

It turns out that every non-planar graph can be reduced to a minor of one of two graphs. The first is $K_5$, the complete graph of order 5:

The second is $K_{3,3}$, the complete bipartite graph 3,3:

These two graphs are the smallest non-planar graphs, otherwise we’d be able to reduce them further to get another non-planar graph. Like I mentioned before, this is a characterization for planar graphs too, since a planar graph can’t contain a $K_5$ or $K_{3,3}$ minor.

I guess I’ll end by saying that graphs are hella useful, especially in computer science. A lot of people complain about never using math like calc ever. If you’re a developer, you’ll run into graphs everywhere. It’s pretty amazing how many structures and concepts can be represented by a bunch of circles and lines.