## 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.

Read the rest of this entry »