Communicating Math – Euler Characteristic

One of my favorite areas of math is graph theory.  The Euler characteristic can be used to describe polyhedra surfaces, but I am just going to look at how it is applied to planar graphs.

Before beginning it is important to note that every cycle that a graph has creates a face.  Also, the infinite plane that the graph is sitting in is also a face.

If a finite, connected, planar graph has v vertices, e edges, and f faces without any intersecting edges then

v – e + f = 2.

Before beginning it is important to note that every cycle that a graph has creates a face.  Also, the infinite plane that the graph is sitting in is also a face.

A graph can either have one or more cycles or have zero cycles.  A graph without any cycles, acyclic, can pretty easily be shown that the Euler characteristic holds. Look at the acyclic graph below.

Image

There are 6 vertices (v=6), 5 edges (e=5), and only 1 face (f=1).  Therefore,

v – e + f = 6 – 5 + 1 = 2,

which is what we wanted.

More generally, a graph that is acyclic and connected will always have one less edge than it has vertices (e = v – 1).  Otherwise, a cycle would be created.  Also, a graph that is acyclic will always have exactly one face (f = 1) because any additional faces have to be created by the presence of a cycle.  Therefore,

v – e + f = v – (v – 1) + 1 = 1 + 1 =2

Now, let’s look at the case where the graph does contain one or more cycles.  The graph below has 6 vertices (v = 6), 7 edges (e = 7) and 3 faces (f=3).

Image

So,

v – e + f = 6 – 7 +3 = 2.

The Euler characteristic for this graph with 2 cycles is still 2.

In order to show this for a general case, let’s start to remove the edges that create a cycle.  First, we will remove edge 7.

Image

There are still 6 vertices (v = 6) , but there are now only 6 edges (e = 6) and 2 faces (f=2).  Now,

v – e + f = 6 – 6 + 2 = 2.

Even though we have deleted an edge, the Euler characteristic has remained the same.

If we remove edge 6, the number of vertices will remain the same.  However, the number of edges and faces will both decrease by 1 again.

Image

 

We see that the number of vertices is still 6 (v = 6), the number of edges is now 5 (v = 5), and the number of faces is now 1 (f = 1).  We have the same values for v, e, and f as we did in the case were the graph did not contain any cycles. Therefore,

v – e + f = 6 – 5 +1 = 2.

As we saw, after deleting an edge that is in a cycle, the cycle no longer exists.  Also,

v ‘ = v

e ‘ = e – 1

f ‘ = f-1

where v ‘ , e ‘ , and f ‘ are the number of vertices, edges, and faces in the graph once the specified edge has been removed, respectively.  By using the above values for v ‘ , e ‘ , and f  ‘ we get that

v ‘ – e ‘ + f ‘ = v – (e-1) + (f – 1) = v – e + f.

This will remain true no matter how many edges are removed in order to create a graph that does not contain any cycles. Since we have already shown that v – e + f is equal to 2 when a graph does not contain any cycles, we can now conclude that v – e + f  is equal to 2 for any finite, connected, planar graph.

So, every planar, connected graph has an Euler Characteristic of 2.  This can be useful in determining a missing piece of information.  If you desire to create a connected planar graph and you know that you need to have 10 vertices and 14 edges, then you know that you will have to have 6 faces.  This is because in order for

10-14+f=2

f must equal 6.  From there, you know that your graph will have to have 5 cycles in it, since each cycle creates a face and then there is the infinite face created from the plane that the graph is on.  Also, if you are given the number of vertices, edges, and faces a graph has, you can determine if it is planar given that it is a connected graph.  If the Euler Characteristic isn’t two, then you know it isn’t possible to create a planar connected graph using the given information.

By utilizing the Euler Characteristic of a graph, you can save a lot of time in trying to draw a planar representation of a graph that may not be even be planar.

Advertisements

One thought on “Communicating Math – Euler Characteristic

  1. So if you have a cycle you have to include a face for it? Why does the plane the points lie in count as a face?
    A lot of fun math in this, explained well.
    For an exemplar, consider adding a summary. For this post, it should probably be about the key ideas &/or importance of this work.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s