Author:
Amanda Hager
Subject:
Mathematics
Material Type:
Lesson
Level:
Provider:
University of Texas at Austin
Tags:
• D2S2
• Mindset
Language:
English
Media Formats:
Text/HTML, Video

# 5.2 Euler characteristic ## Overview

 TCCNS Course MATH 1332: Contemporary Mathematics UT Austin Course M 302: Introduction to Mathematics

# Suggested Resources and Preparation

## Materials and Technology

• For the instructor: spheres and toruses (plastic balls and stacking rings) are helpful for drawing graphs on.

## Prerequisite Assumptions

References to regular solids are made.

# Overview and Student Objectives

50 minutes

## Lesson Objectives

Students will understand that:

• The Euler characteristic of any connected planar graph drawn on the plane or on the sphere is 2.
• Euler characteristic can be generalized beyond graphs on spheres to graphs drawn on other objects, or to 3D or 4D objects.

Students will be able to:

• Compute the numbers of vertices, edges, and faces in assorted connected planar graphs.
• When possible, alter non-planar graphs to an equivalent graph which is planar.

# Euler characteristic

The concept of and formula for Euler characteristic applies in the world of graph theory as well as topology. The reason is because the basic objects we're working with are similar, just dots and lines and regions. Here, basically, you'll learn some terms and skills, learn about a theorem in graph theory, and learn one interesting connection/application of it to topology.

# Terms

• The Euler characteristic of any graph is equal to V - E + F. Remember to count the infinitely large "outside face" along with all the other faces, even if it is strangely shaped.
• A graph is connected if it can be drawn completely without picking up your pencil.
• A graph is planar if it can be drawn without any of the edges intersecting. It doesn't have to appear that way initially; if you know you can redraw it without edges intersecting, the original graph also counts as planar.

# Examples  This graph is not connected. There is a vertex on the upper right that you can't get to from the rest of the graph without picking up your pencil. I would say this graph has "two connected components," which is a way of saying it's a graph with two pieces or two clumps of vertices and edges. Fixed it! This graph is connected. You can draw this entire graph without picking up your pencil. In other words, you can walk from any vertex to any other vertex via the edges.

This graph is planar: It has two edges crossing in the middle, though, so at first it doesn't look like it. But because we can pick one edge up and move it out of the way, the original graph actually counts as planar (this reminds me of the definition of a rational number. 0.25 counts as rational because you could write it as 1/4 if you were in the mood).  # Euler characteristic theorem

Try an experiment:

1. Draw a big swirly doodle with your pen. Do not pick up the pen as you doodle.
2. Every time you see an intersection, add a vertex. Add vertices at the two ends, too.
3. Compute V - E + F. You always get 2!   In this example, we get V = 8, E = 13, and F = 7, and 8 - 13 + 7 = 2.

# Euler characteristic theorem

All connected planar graphs have an Euler characteristic of 2.

# Examples   There are no bounded faces here, so all of the outside area is one face. This means we have V=2, E=1, and F=1, and 2 - 1 + 1 = 2. We have one bounded face plus the outside face. This means that V=3, E=3, and F=2, and 3 - 3 + 2 = 2. We have three bounded faces and all the rest of the outside area is a fourth face. Also note the looped edge counts as one edge. This means we have V - E + F = 6 - 8 + 4 = 2.

# Proof of Euler characteristic theorem

Given how many different graphs there are, how do you prove such a theorem?

It starts by understanding that we can build up a connected planar graph gradually starting from a single vertex. And notice that the Euler characteristic of a graph that has only a single vertex is 1 - 0 + 1 = 2. You can always build up a graph using these moves:

1. Draw a new vertex and a new edge connected the new vertex to the rest of the graph. In this case V goes up one, and E goes up one, and the formula stays the same.
2. Draw a new edge connecting two existing vertices or a loop with both ends connecting to the same vertex. In this case E goes up 1, F goes up 1, so the formula stays the same.

Since these moves don't change the Euler characteristic and we can always build our graph using those moves, we know the characteristic will always be 2.

# Multi-piece graphs

What happens if the graph is not connected but is still planar? We can still compute the Euler characteristic, but we will get a different number. For example:

This graph has two pieces. I count four vertices, three edges, and two faces. We get 4 - 3 + 2 = 3. It turns out that you always get an Euler characteristic of 3 for a two piece graph. More about this in the homework.

# Application to topology

When we studied the regular solids, we found out that the graphs on the outside of those solids (the networks of vertices, edges, and faces) had an Euler characteristic of 2. That's because all of them can be flattened out and viewed as connected planar graphs. But what else is possible?

# Question 1

6, 7, 3, 6-7+3=2.

cube

octahedron

2

3

3

# Question 1

This graph has ____ vertices, ____ edges, and ____ faces.  The Euler characteristic is ____ . # Question 2 # Question 3

Which regular solid does this graph correspond to? # Question 4

What does it mean for a graph to be planar?

1. It means you can draw the graph in the plane without any of the edges crossing over one another.
2. It means you can draw the graph in the plane using only straight edges.
3. It means you can draw the graph in the plane without picking up your pencil.
4. It means you can draw the graph in the plane.

# Question 5

We learned that the Euler characteristic V−E+F is equal to 2 under certain conditions.  What are those conditions?

1. The Euler characteristic is 2 as long as there are six or fewer vertices in the graph.
2. The Euler characteristic is always 2, no matter what.
3. The Euler characteristic is 2 if it is connected and if it is also planar.
4. The Euler characteristic is 2 when the graph is connected.

# Question 6

Is this a planar graph? 1. Yes because it is drawn in the plane.
2. No because two edges overlap.
3. Yes because it could be redrawn as a graph with no overlapping edges.
4. No because it has too many edges.

8-12+6=2

6-12+8=2

# Question 5.2.3

4, 5, 3

1. E  and F go up one.
2. E and F go down one.
3. No. V-E+F=2. If we add an edge, then either V or F must go up to compensate. Also it doesn't make sense to add lines and somehow combine regions.

5-4+2=3

8-7+3=4

# Question 5.2.6

The E characteristic of an n piece graph should be n+1

# Question 5.2.1

Compute the Euler Characteristic V−E+F for this graph. # Question 5.2.2

Compute the Euler Characteristic V−E+F for this graph. # Question 5.2.3

Compute V, E, and F for this graph. 1. What happens to those three numbers if we add an edge from E to H?
2. What happens to those three numbers if we delete the loop from H to H?
3. Is it possible to add an edge and decrease the number of faces? Why or why not?

# Question 5.2.4

This is a two-piece graph. We consider it to be a single graph, but it just has two clusters of vertices and edges. Compute V−E+Ffor this graph. # Question 5.2.5

This is a three-piece graph. We consider it to be a single graph, but it just has three clusters of vertices and edges. Compute V−E+Ffor this graph. # Question 5.2.6

Make a conjecture about the Euler characteristic of an n-piece graph. Support your guess by drawing a four-piece graph and computing its Euler characteristic.