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.1 Graphs and circuits ## 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: Colorful markers or pencils will help in documenting paths (simply tracing over the edges can be confusing).

None

# Overview and Student Objectives

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.

# What is a graph?

## Terms

graph is a collection of vertices and edges.

• 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. ## 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. # 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. 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. # 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.

2

2

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: Which of the following paths are circuits? Select all that apply.

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

# 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: 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. # Question 5.1.2

Does this graph have an Euler circuit? If so, list it. If not, explain why. # 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. # Question 5.1.4

Here's a graph: 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).