MEC Lesson 3 – Graph theory and Euler characteristic

Our next step in attempting to understand mathematical proof is to look at how mathematicians actually come up with theorems in the first place, and how this process can help them come up with ways to create a proof.

With that in mind, work through the following exercises in which you will come up with your own idea for a theorem, and then see how one might prove it!

Worksheet on Euler Characteristic

Hopefully as you went through this worksheet you came up with the following guess for a theorem:

The value of V-E+F is always 1, no matter the graph.

More then that, what followed was the outline for a way to prove this via a direct proof. Remember, with a direct proof we need to give an argument that works for any graph obeying those rules (there’s actually a name for such graphs, we call them planar graphs, because they can be drawn in the plane!). So our proof should start with something like:

Let G be any planar graph. For this graph G suppose the value of

V-E+F = x

We want to show that x=1. Well we saw in the worksheet that we can always cut up all the faces of G into triangles without changing the value of x.

Screen Shot 2015-11-10 at 10.06.22 p.m.

Next we saw that we can remove triangles from the outside in, each time not changing the value of x.

Screen Shot 2015-11-10 at 10.06.34 p.m.

We repeat in this way until we are left with only 1 more triangle, and because we haven’t changed the value of x along the way we know that V-E+F for the triangle is equal to V-E+F of the original graph G! We complete the proof by verifying that any triangle has V-E+F = 1.

Summary. We see here that although we cannot prove something just by doing examples, it is still a very important part of the process. We not only saw that V-E+F=1 in each of our examples, but by playing around with triangles we were able to gain intuition on how the proof might go.

A word on Platonic Solids

We followed up this proof with a proof of one of my favorite theorems! We showed that there are only 5 so called Platonic solids. As it happens I already have a blog post explaining how that proof follows from this one.

Proof that there are only five Platonic solids

I also promised that I’d put a link the visualization we demoed. You can get that here.

Advertisements

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s