Nonplanar graphs & the Euler characteristic

Introduction and K4, the complete graph on 4 vertices

I want to show you something clever, but I’m going to omit the details of how we justify part of it. And I’m going to raise a question about another part of it. But I think this application of the Euler characteristic is interesting, even if I won’t or can’t cross all the t’s.

We can define the Euler characteristic of a graph as . We can show, for example, that every tree (a graph with no closed paths) has . If a graph is not a tree, then the closed path might create a face, but we don’t count the faces.

One question that arises when we have a graph is: is the graph planar? That is, can it be drawn in the plane so that edges do not have extraneous intersections?

Better to show you. Draw a square (or rectangle), and draw the two diagonals. This is called K4, the complete graph on 4 vertices, because every vertex is connected to every other vertex.

But the diagonals cross each other.

Books Added 1 Aug 2008: Graph Theory

I have had a long-standing question: why is the usual triangulation of a torus so large? It is a square with 18 triangles. Why so many?

While looking through algebraic topology books for more information about simplicial complexes – which is supplementary material for Bloch (“A First Course in Geometric Topology….” – I found the answer. Well, I found a clue. I found an inequality, which implied that the minimum number of triangles was 14 in any possible triangulation of the torus.

What I didn’t find was a proof of that inequality, and I couldn’t work it out for myself.

Eventually, in another algebraic topology book, I found another clue, and it was enough to let me work out the first inequality.

Along the way I found some pretty interesting things, and I want to chatter about them. The result will not really be math, but more in the nature of a travel guide.

Well, no, not even that detailed. More in the nature of some really cool pictures from a foreign country.

The search took me into both algebraic topology and graph theory. Before I put out the posts (there will be at least two), I need to put out some bibliography.