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

    Education Standards

    5.2 Euler characteristic

    5.2 Euler characteristic

    Overview

    TCCNS CourseMATH 1332: Contemporary Mathematics
    UT Austin CourseM 302: Introduction to Mathematics

    Introduction

    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

    Lesson Length

    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

    Four vertex graph with three edges.Four vertex graph with four edges. The isolated vertex has been connected to the other three.
    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:

    Complete graph on four vertices. Two edges cross in center.

     

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

    same four vertex graph, edge from upper left to lower right vertices is highlightedsame four vertex graph, edge from upper left to lower right vertices has been moved to the exterior of the graph

     

    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!

    plain doodle intersecting itselfdoodle has had vertices addedregions of doodle have been numbered 1 through 7

     

    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

    two vertex graph, one edge between themcomplete graph on three verticessix vertex graph. two complete three vertex graphs are joined by a single vertex. An additional vertex is connected to one of the triangles, and that vertex also includes a loop.
    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?

    Quiz Questions

    Question 1

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

    Question 2

    cube

    Question 3

    octahedron

    Question 4

    2

    Question 5

    3

    Question 6

    3

    Question 1

    This graph has ____ vertices, ____ edges, and ____ faces.  The Euler characteristic is ____ .

    six vertex planar graph. Vertices A, B, C, D, E, F. Edges are A to B, B to C, C connected to D twice, C to E, D to E, E to F.

    Question 2

    eight vertex graph. Two nested squares, with four more edges connecting inner vertices to corresponding outer vertices.

    Question 3

    Which regular solid does this graph correspond to?

    6 vertex planar graph with 12 edges. Each vertex has degree 4.

    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?

    complete graph on four vertices

    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.

    Homework Questions

    Question 5.2.1

    8-12+6=2

    Question 5.2.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.

    Question 5.2.4

    5-4+2=3

    Question 5.2.5

    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.

    eight vertex graph. Two nested squares, with four more edges connecting inner vertices to corresponding outer vertices.

    Question 5.2.2

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

    6 vertex planar graph with 12 edges. Each vertex has degree 4.

    Question 5.2.3

    Compute V, E, and F for this graph.

    four vertex graph, vertices E, F, G, H. Two edges from E to F, Edges from E to G, from G to H, and a loop at H.

     

    Then answer the following:

    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. 

    Two piece graph, left piece is a triangle. Right piece is a line segment.

    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.

    Three piece graph, left piece is an isolated vertex. Center piece is five vertices, a square graph with a fifth vertex connected to one of the other four. Third piece is a pair of vertices joined by two edges.

     

    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.