# 5.4 Universal Towns - Introduction and Ideas

## Overview

TCCNS Course | MATH 1332: Contemporary Mathematics |

UT Austin Course | M 302: Introduction to Mathematics |

# Introduction

**Overview and Student Objectives**

**Lesson Length:** 50 minutes

**Overview:** This activity expands on Lesson 5.1 by introducing new kinds of graphs -- the complete and directed graphs -- which allow for the study of so-called universal towns.

**Lesson Objectives:**

Students will understand that:

- The introduction of new kinds of graphs is conducive to the study of new properties, and;
- In a meta-mathematical sense, the correct framework is paramount to the development of new, tractable problems.

Students will be able to:

- Identify complete graphs, directed graphs, and universal towns and;
- Form simple conjectures through a trial-and-error process.

**Suggested Resources and Preparation**

**Materials and Technology:**

N/A

**Prerequisite Assumptions: **Lesson 5.1: Graphs and Circuits

**Suggested Instructional Plan**

**Frame the Activity**** **(5 minutes)

- Begin by summarizing our survery of graphs in Lessons 5.1 and 5.2, ask students what they've learned about graphs so far.
- Emphasize how the rigid (as demonstrated by e.g. the Euler characteristic) yet simple structure of graphs is conducive to the study of their properties (e.g. existence of an Euler circuit). You don't need much information to say a lot about a graph.
- Transition to lesson -- we will focus on a special kind of graph which provides just enough structure to deduce meaningful information.

**Activity Flow **(30 minutes)

- Instructor is advised to follow the body as presented in subsequent sections. Italicized questions provide opportunities for student engagement.
- Additional examples may be illuminating.

**Wrap-up/Transition**** **(15 minutes)

- Conclude by providing context for the lesson as exposited in the "Thinking Mathematically" section.
- Time permitting, either have students complete quiz questions in class followed by discussion as a means of formative assessment or guide students through the quiz questions to further solidify understanding.
- Foreshadow Lesson 5.5 by introducing the homework.

**Overview**

This activity expands on Lesson 5.1 by introducing new kinds of graphs -- the complete and directed graphs -- which allow for the study of so-called universal towns.

**Lesson Objectives**

You will understand that:

- The introduction of new kinds of graphs is conducive to the study of new properties, and;
- In a meta-mathematical sense, the correct framework is paramount to the development of new, tractable problems.

You will be able to:

- Identify complete graphs, directed graphs, and universal towns and;
- Form simple conjectures through a trial-and-error process.

# Complete and Directed Graphs

There are some special types of graphs we can study. One such example are the *complete *graphs. For these graphs every vertex is connected to all others by exactly one edge. So if you pick any two different vertices, there will always be one edge connecting them. The three graphs on the left, pictured below, are complete graphs, whereas the graph on the right is not a complete graph (so, we do *not *connect vertices to themselves and form loops).

**Example 1**

We can also talk about *directed *graphs. These are formed by taking any graph, and marking each edge with exactly one arrow. The two graphs on the left, pictured below, are directed graphs whereas the graph on the right is not (one edge is missing an arrow and one edge has two arrows, neither is allowed).

**Example 2**

Since any graph can be turned into a directed graph (simply by labelling all the edges with arrows), we can turn complete graphs into directed graphs. The middle graph in the above figure is a so-called *complete directed *graph since it is both complete and directed. A good way to think about these is to imagine a country where all the towns are vertices and roads are edges. A complete directed graph in this setting means that every pair of towns is connected by a one-way road.

**Terms**

- A
**complete****graph**is a graph where every pair of different vertices are connected -- no loops allowed! - A
**directed graph**is a graph where every edge is assigned exactly one arrow. - A
**complete directed graph**is a graph which is both complete and directed.

# Universal Towns

Let's stick with the analogy that directed graphs represent road systems and imagine any directed graph (so, all the roads are one-way, towns are vertices and roads are edges). Call a town *universal *if, starting at that town, you can follow the roads and get to any other town. You are allowed to use as many roads as you need, you can go over them several times, and you can go through the same town multiple times. You do not need to reach every town with one route -- you can restart at the original town, and choose another path. The only thing you cannot do is go against the direction of any road. For example, in the directed graph below town A is a universal town.

**Example 3**

*Question: Why is town A universal? *

We can start by going to town B, then go to town D. So both town B and town D are accessible from town A. We just need to check if town C is. We cannot travel there from town D though. Starting a new route from town A, we take the other path and reach town C. Hence, all the towns are accessible from town A!

**Terms**

- A
**universal****town**is a vertex on a directed graph from which you can travel to every other vertex.

# Thinking Mathematically

With respect to the connection to the quiz, the first question explicitly has students construct directed graphs for which no universal towns exist, all towns are universal, and exactly one exists. There is no consistent answer you can give to the qustion "How many universal towns are there?" since it is possible that none exist. And even if at least one exists, the fact that you can go from both extremes (exactly one and all) suggests that any amount in-between can occur.

Throughout this lesson we have defined different some new graphs, e.g. complete directed graphs, and identified special vertices on these graphs, i.e. universal towns. You may be wondering why we're doing any of this. The answer is that math is all about solving problems. Taking a math course is less about the actual math being taught than it is the development of critical thinking and problem solving abilities. In order to solve problems, we need to have problems to start with! From a mathematical point of view the purpose of this lesson is to establish a framework conducive to generating (solvable) problems.

The quiz questions explore this idea. For example, we can ask "In a given directed graph, how many universal towns does it have?" Question 1 tells us that our framework (a generic directed graph) does not have enough structure to give a single answer. Question 2 tells us that if we work with a complete directed graph, then we can give an answer.

# Quiz Questions

**Solutions**

**Question 1**

Left: No universal towns, Center: All three are universal towns, Right: Only one is a universal town.

**Question 2**

**Part A**

### **Part B**

Since it is a conjecture, any answer is acceptable as long as it is backed up by evidence (with their three complete, directed graphs). The "correct" conjecture is "Every complete directed graph has at least one universal town."

**Teaching Tips**

It may be daunting as a student to write a conjecture, which is why a template is given. Have them complete the first part and identify any universal towns. Conjectures do not necessarily have to be correct (this is sometimes the case in math!), so encourage them to describe their results without worrying if it is actually correct in general.

**Question 1**

How many universal towns do each of the above graphs have?

**Question 2**

Draw three complete directed graphs, one with three vertices, one with four, and one with five.

**Part A**

Can you find any universal towns?

**Part B**

Write a conjecture of the form "_____ complete directed graph has _____ universal town(s)" (example words for the first blank include "every, none, some", for the second blank include "none, at least one, many," etc.)

# Homework Questions

**Solutions**

**Question 1**

Yes, you can create new universal towns.

**Question 2**

Any answer is fine so long as they counted correctly. You can make every universal town universal.

**Question 3**

Again, any answer is fine. The point is for the student to create a conjecture. In reality you only need at most one road change to make all towns universal.

**Teaching Tips**

The first part of this question is basically asking "is this even a good idea?" It could be that by changing road directions, you destroy previous universal towns at the same time as creating new ones, and there is zero overall effect. It actually turns out to be a good idea, and it should be pretty intuitive which directions they need to change. In particular, any town which has a road leading to a universal town is universal.

Answers for the second and third parts may vary depending on what students do. The point is they should try to increase the number of universal towns as much as possible (say they get half of them to be universal). Now, while doing that they've been changing road directions. Maybe you can do better, and get the same number of universal towns with less road changes. In fact you can, and you only need one change.

A road system like this -- formed from a directed complete graph -- is awful since there are some towns that you might not be able to even leave! An engineer is hired to try and fix this issue. First they think about adding new roads, but that's expensive. The engineer comes up with another idea -- why not just change the directions on some of the roads and see what happens. Try this yourself with your example graphs from the Quiz questions. Then, answer the following questions:

**Question 1**

By changing road directions, are you able to create new universal towns?

**Question 2**

How many universal towns were you able to create? Try to maximize this number. (e.g., can you ensure that there is at least one universal town? About half are universal? All are universal?)

**Question 3**

How many road directions did you need to change in Question 2? Can you minimize this number? Write your results.