「涼宮ハルヒの消失」/「茨乃」
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:
$$x-y=(D-1)-z$$
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.
