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.1 Graphs and circuits

    5.1 Graphs and circuits

    Overview

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

    Introduction

    Suggested Resources and Preparation

    Materials and Technology

    • For the instructor: Colorful markers or pencils will help in documenting paths (simply tracing over the edges can be confusing).

    Prerequisite Assumptions

    None

    Overview and Student Objectives

    Lesson Length

    50 minutes

    Lesson Objectives

    Students will understand that:

    • Graphs have Euler circuits if and only if the degrees of every vertex are even.

    Students will be able to:

    • Compute the degrees of vertices in graphs. 
    • Identify whether a path is a circuit and/or Euler circuit.
    • Construct an Euler circuit given an appropriate graph.

    Graphs and circuits

    What is a graph?

    Terms

    graph is a collection of vertices and edges.

    Facts and advice about graphs:

    • Vertices do not all have to be connected by edges.
    • Two vertices can have more than one edge between them.
    • Sometimes we draw two edges intersecting without a vertex being where they intersect.

    Example

    The three diagrams below represent valid graphs, even though in the first graph there is a vertex that is separate from the others, in the second there is a loop, and in the third there are edges that cross.

    Three four-vertex graphs. Left has three vertices connected in a triangle. Middle graph has one multi-edge and one loop. Right graph is a complete graph on four vertices. the middle edges intersect

     

    Terms

    • path is any list of edges that you can trace with your pencil without picking it up.
    • circuit is a path that ends where it starts.
    • An Euler circuit ("Oiler") is a circuit that covers every edge exactly once.

    The easiest way to describe paths is to give names to all the vertices, and then use lists of letter to give directions.

    Example

    In this graph, ABCD is a path but not a circuit. ABCDA is a path and a circuit but is not an Euler circuit. ACA and ACACA are also valid circuits. ABCACDA is an Euler circuit.

    Four vertex graph, vertices A, B, C, D. A has two edges to D and one edge to B and one edge to C. B has one edge to D, and C has one edge to D.

    Euler Circuit Theorem

    The Euler circuit theorem tells us exactly when there is going to be an Euler circuit, even if the graph is super complicated.

    Theorem

    Euler Circuit Theorem: If the graph is one connected piece and if every vertex has an even number of edges coming out of it, then the graph has an Euler circuit. If the graph has more than one piece or if even one vertex has an odd number of edges connecting to it, then no Euler circuit exists.

    Example

    In this graph, A and C have four edges coming out of them and B and D have two edges coming out of them. Since the graph is a single-piece graph, we know this graph will have an Euler circuit.

    Four vertex graph, vertices A, B, C, D. A has two edges to D and one edge to B and one edge to C. B has one edge to D, and C has one edge to D.

    In this graph, vertices A and C have an odd number of edges coming out of them. B and D have even numbers of edges coming out of them, but it doesn't matter. This graph can't have an Euler circuit.

    Four vertex graph, vertices A, B, C, D. A has one edge to D and one edge to B and one edge to C. B has one edge to D, and C has one edge to D.

    Representing real-life scenarios as graphs

    In any application problem, you have to choose two things: what vertices represent and what edges represent. Some examples:

    • Vertices are American cities, and two vertices are connected with an edge if Southwest offers a direct flight between them.
    • Vertices are people, and two vertices are connected with an edge if the two people are connected on a social media platform.
    • Vertices are countries, and two vertices are connected with an edge if the two countries have a trade agreement.
    • Vertices are countries, and two vertices are connected with an edge if the two countries share a land border.

    Quiz Questions

    Question 1

    2

    Question 2

    2

    Question 3

    1, 2, 5

    Question 1

    What is a circuit (on a graph)?

    1. It's a graph that is a loop.
    2. It is a list of edges that you can trace without picking up your pencil and that ends where it starts.
    3. It's a list of edges that you can trace with your pencil without using any edge more than once.
    4. It's a graph where you can use up all the edges without picking up your pencil.

    Question 2

    What is an Euler circuit (on a graph?)

    1. It's a graph that goes in a loop.
    2. It is a list of edges that you can trace without picking up your pencil that ends where it starts and uses up all edges exactly once.
    3. It's a graph where you can use up all the edges with no repeats.
    4. It's a list of edges that you can trace without picking up your pencil.

    Question 3

    Here is a graph:

    Four vertex graph, vertices A, B, C, D. Three edges from A to C, two edges from C to D, one edge from A to B and B to D.

    Which of the following paths are circuits? Select all that apply.

    1. ACA
    2. ACABDCA
    3. CDCABD
    4. ABDC
    5. DBACD

    Homework Questions

    Question 5.1.1

    No, it has two vertices with odd degree.

     

    Question 5.1.2

    Yes. For example, ABDEBCEDA.

    Question 5.1.3

    There are six vertices, and all have odd degree. Every time we add an edge, we can add one to the degree of two different vertices. For example, if we add an edge between A and D, then the degrees of A and D both become even. Therefore, if we add three edges, all degrees will be even. Pictures submitted will vary.

    Question 5.1.4

    Here's a graph:

    Four vertex graph, vertices A, B, C, D. A has one edge to D and one edge to B and one edge to C. B has one edge to D, and C has one edge to D.

    1. Responses vary. Ex: AB, ABD
    2. Responses vary. Ex: ABDCA, ABDA, BDCAB. 
    3. Responses vary. Correct responses must begin at A and end at D or vice versa. Ex: ABDCAD.

    Question 5.1.1

    Does this graph have an Euler circuit? If so, list it. If not, explain why.

    five vertex graph, vertices A, B, C, D, E. Edges connecting A to B, B to C, C to D, D to E, E to A, A to D, and A to C.

    Question 5.1.2

    Does this graph have an Euler circuit? If so, list it. If not, explain why.

    five vertex graph, vertices A, B, C, D, E. Edges connecting A to B, B to C, C to E, A to D. Two edges connecting D to E. Edges connecting B to D, and B to E.

    Question 5.1.3

    This graph does not have any Euler circuits. What is the smallest number of edges you need to add so that there will be an Euler circuit? Submit a picture of the graph with the added edges.
    six vertex graph, vertices A, B, C, D, E, F. Edges are A-B, B-D, D-F, F-E, E-A. Also, C is connected to all vertices with one edge.

    Question 5.1.4

    Here's a graph:

    Four vertex graph, vertices A, B, C, D. A has one edge to D and one edge to B and one edge to C. B has one edge to D, and C has one edge to D.

    1. List a path in this graph that is not a circuit.
    2. List a circuit in this graph that is not an Euler circuit.
    3. List a path in this graph that uses up all edges exactly once (it won't be a circuit).