Author:
Kenneth DeMason
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.5 Universal Towns - Induction and Hamiltonian Paths

    5.5 Universal Towns - Induction and Hamiltonian Paths

    Overview

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

    Introduction

    Overview and Student Objectives

    Lesson Length: 60 minutes

    Overview: We prove the following claim: by changing at most one road direction, all towns in a complete directed graph can be made universal. To do this we introduce a new type of path, the Hamiltonian path, and relate it to the existence of universal towns. This allows us to rephrase our claim to be more compatible with a new proof technique: induction.

    Lesson Objectives

    Students will understand that:

    • The existence of universal towns is related to the existence of Hamiltonian paths;
    • There is utility in reformulating claims and;
    • Specific examples can sometimes highlight generic properties.

    Students will be able to:

    • Identify Hamiltonian paths on a directed graph and;
    • Use induction to prove basic claims.

    Suggested Resources and Preparation

    Materials and Technology

    • Possible exit slip based off Questions 2 and 3 in the quiz.

    Prerequisite Assumptions 

    This is a continuation of Lesson 5.4 and should be done the following class. Students should have completed the homework prior to this lesson. 

    Suggested Instructional Plan

    Frame the Activity (5 minutes)

    • Re-introduce the homework problem from Lesson 5.4.
    • Have students present and discuss their results.
    • Guide them towards the preliminary results in Section 2, then continue into the main lesson.

    Activity Flow (45 minutes)

    • Instructor is advised to follow the body as presented in subsequent sections. Italicized questions provide opportunities for student engagement.

    Wrap-up/Transition (10 minutes)

    • Conclude by providing context for the lesson as exposited in the "Thinking Mathematically" section. This also gives the instructor time to review and clarify key concepts as defined in the lesson objectives.
    • Time permitting have students answer quiz questions in class. The latter two are short and can be used for an exit slip.

    Overview

    We prove the following claim: by changing at most one road direction, all towns in a complete directed graph can be made universal. To do this we introduce a new type of path, the Hamiltonian path, and relate it to the existence of universal towns. This allows us to rephrase our claim to be more compatible with a new proof technique: induction.

    Lesson Objectives

    You will understand that:

    • The existence of universal towns is related to the existence of Hamiltonian paths;
    • There is utility in reformulating claims and;
    • Specific examples can sometimes highlight generic properties.

    You will be able to:

    • Identify Hamiltonian paths on a directed graph and;
    • Use induction to prove basic claims.

    Creating Universal Towns

    We saw in the first part that every complete directed graph has at least one universal town. The homework problem asked you to play with changing the directions of roads for such graphs in order to create more. 

    Question: What were you able to discover? For example, how many universal towns could you create?

    It turns out that you can turn every town into a universal town just by changing the road directions. Here's an example:

    Example 1

     left, a four vertex graph with one universal town. Three edges are highlighted with comment "change these three." right, after changing the direction of the three edges, the same graph now has four universal towns.
    By making all the outer edges go clockwise, the vertices become universal towns.

    In the above complete directed graph there is exactly one universal town. But, we can change all the road directions on the "exterior" or "circumference" to continue one after the other, for example in a clockwise motion. Doing this will require at most \(n\) many changes, where \(n\) is the number of vertices.

    Question: Can we do better? In other words, can we get the same number of universal towns by changing fewer road directions?

    One improvement comes from examining the previous argument more carefully. Count how many exterior edges produce clockwise motion and how many produce counter-clockwise motion. The total amongst the two will always sum to \(n\), because there are \(n\) vertices and we are travelling to each once. So by the pigeonhole principle -- where the pigeons are the \(n\) exterior edges and the pigeonholes are the two types of motion -- one of these groups will always have at least \(n/2\) (rounded up) many exterior edges. We just need to change the directions in the other group, which holds the remaining \(n/2\) (rounded down) exterior edges. 

    Example 2

      Left, four vertex graph with six edges. Three outer edges are marked counterclockwise and the top edge is marked clockwise. Right, after changing the direction of the clockwise edge, all towns become universal.
    There is only one clockwise edge. Changing this makes all towns universal.

    Example 3

     Left, a five vertex graph with three clockwise edges around the outside and two counterclockwise edges. Right, after changing the directions of the two counterclockwise edges, all towns become universal.
    There are \(5/2\) (rounded down) many counter-clockwise edges. Changing these makes all the towns universal.

    In fact we can do even better than this. Surprisingly, the following claim is true!

    Claim: In a complete directed graph at most one change in road direction is necessary to make every town universal.

    We can prove this claim but we'll need a few more tools in our toolbox first.

    Hamiltonian Paths

    Our first tool will be a Hamiltonian path, which is a path that visits each vertex exactly once. In an undirected graph, edges can be traversed in either direction; in a directed graph however, edges must be traversed in the specified direction.

    Hamiltonian paths are similar to Eulerian circuits but should not be confused -- remember that an Eulerian circuit visits each edge once. Also, paths do not need to end at the same vertex they started whereas circuits must (so each circuit is a path but not vice-verse).

    Question: How do Hamiltonian paths help us prove our claim?

    If our graph has a Hamiltonian path then the starting town is a universal town. Now because our graph is complete there is a road connecting the first and last towns. If the direction completes the path so that we have a Hamiltonian circuit, then in fact every town is already universal! If the direction is opposite, then we just need to change that one edge. We've just shown that we only need to change one direction in order to make every town universal under a crucial assumption. In other words we've just reduced our original claim to proving the following new claim.

    New claim: Every complete directed graph has a Hamiltonian path.

    Terms

    • A Hamiltonian path is a path in a graph which passes through every vertex exactly once.

    Induction

    To show our new claim, that every complete directed graph has a Hamiltonian path, we'll invoke a new proof method called a proof by induction

    Imagine you have a robot which is programmed to do exactly two things:

    1. When placed at the bottom of a staircase, go onto the staircase.

    2. When standing on a stair, move up to the next one.

    Question: If I place this robot at the bottom of a staircase, does it reach the top?

    It does! It'll first move onto the staircase. Then, since it is on a stair, it'll move up to the next. But it'll likely still be on a stair, so it moves up again, and again, and again until there are no more stairs. If hypothetically there were infinitely many stairs then the robot would continue ascending forever.

    What does our robot friend here have to do with Hamiltonian paths? Our claim is that "Every complete directed graph has a Hamiltonian path", but this is the same thing as saying that 

    • "A complete directed graph with three vertices has a Hamiltonian path" (claim 1), and

    • "A complete directed graph with four vertices has a Hamiltonian path" (claim 2), and

    • "A complete directed graph with five vertices has a Hamiltonian path" (claim 3), and so on...

    Instead of proving one claim, we can instead prove infinitely many. At first glance this seems impossible but with induction we'll only need to show:

    1. Claim 1 is true. This is called the base case.

    2. If claim \(n\) is true then claim \(n+1\) is also true. In other words, by assuming claim \(n\) we can prove claim \(n+1\). This is called the inductive step.

    Why does induction work? This is where our robot friend comes into play. The analogy goes like this: each step is a claim, and if the robot can ascend to a certain step, then that claim is proven. So if the robot can reach the first step, claim 1 is proven. If it can move up to the second step, claim 2 is proven, and so on. In this analogy, the two necessary criteria for induction are that the robot can reach the first step, and if the robot is on step \(n\) it can move to step \(n+1\). This is exactly the process described at the beginning of this section! We agreed there that if the robot is placed on an infinitely tall staircase, it'll keep ascending forever. By analogy, every claim will be proven! Let's put it in practice.

    Terms

    • A proof by induction is a proof method used to prove infinitely many claims at once. It consists of two parts: the base case and the inductive step.
    • The base case in a proof by induction is the first claim you must prove. Typically, this will be the simplest one.
    • The inductive step in a proof by induction is a way to use previous information to prove the next claim. It starts by assuming claim \(n\) is true and we must prove that claim \(n+1\) is true. It is always written in the form "If ... then ..."

    Induction and Hamiltonian Paths

    For a more detailed explanation of the cases in the inductive step, let's first count the possible number of complete directed graphs we need to consider. Only the edges connecting the remaining vertex to each of the other vertices matter, and there are such edges. Each one has two choices of direction, either leading into the path or away, giving a total of 2n graphs. We carefully group the graphs into cases, so that case 1 proves the claim for 2n-1 many graphs, case 2 proves it for 2n-2 many and so on. Then case n-1 proves it for one graph, and the final case (which is assuming none of them hold) also proves it for one graph. You can check that \(2^n = 1+\sum_{k=1}^n 2^{n-k}\).

    Remember that we're trying to prove our new claim:

    New Claim: Every complete directed graph has a Hamiltonian path.

    Proof: We will use induction, meaning we have to show two things:

    1. A complete directed graph with three vertices has a Hamiltonian path (the base case).

    2. If a complete directed graph with \(n\) vertices has a Hamiltonian path, then a complete directed graph with \(n+1\) vertices does too (the inductive step).

    Remember that the base case is the simplest case. Here, the simplest complete graph we can make has three vertices. Also keep in mind that the inductive step must be proven in full generality. This means that it is not enough to prove, for example, that if claim 1 is true then claim 2 is true too. This tells us no information about any of the later claims!

    Base Case

    To prove the base case there are two sub-cases to consider. Either all the edges point in the same direction, or two do and one doesn't. These cases are shown below:

     Left, a three vertex directed graph with vertices A, B, C. Edges are C to A, A to B, B to C. Right, a three vertex complete graph with vertices A, B, and C. Edges are A to B, C to B, A to C.

    In either case we have a Hamiltonian path -- choose any two edges which go in the same direction. 

    Inductive Step

    Now we need to prove the inductive step, which is a little more tricky. Consider a complete directed graph with \(n+1\) vertices. We want to show it has a Hamiltonian path. By assumption, every complete directed graph with only \(n\)vertices has a Hamiltonian path. Take our graph and remove one vertex and all the edges connecting to it. We'll obtain a complete directed graph with \(n\) vertices, which by our assumption has a Hamiltonian path. Keep track of this path and add the vertex and all the edges (with the directions they had before) back in. We just need to connect this vertex to our path and form a new Hamiltonian path.

    Here's how the proof works. We'll start by focusing only on the Hamiltonian path, the vertex we added back in, and all the edges connected to it. We don't know which way the arrows on these edges point, so we'll leave them blank as depicted below.

    n vertices across the top labeled v_1 through v_n. Directed edges leading from v_1 to v_2 all the way to v_n. One vertex at the bottom, v, with undirected edges connecting v to every v_i
    Setup to the inductive step. The path \(v_1\) to \(v_n\) is the old Hamiltonian path, which is incomplete until we add in the vertex \(v\). 

    We'll then consider many cases. In each case we'll assume that certain edges point in certain directions. When we do this we'll depict the corresponding arrows. All the other blank edges (which are still directed) will not be used in the proof of that case. So, it doesn't matter which way they point. 

    For example, let's first assume that the edge connecting \(v_1\) to \(v\) points into the path. Then we can form a Hamiltonian path by starting at \(v\), travelling to \(v_1\), then following the path to \(v_n\). Since we've passed through all \(n+1\) vertices we have a Hamiltonian path. Notice that we didn't need any information about the directions on the edges connecting \(v\) to \(v_2,...,v_n\). These edges played no role in forming the new Hamiltonian path. Therefore they can be directed in any way -- it doesn't matter. 

    Next let's see what happens if the edge connecting \(v_n\) to \(v\) points away the path. Here too we have a Hamiltonian path -- travel along the old one, then down to \(v\).

    Because of the above two arguments, we only need to focus when neither of the above occur. In other words when we have the following picture

     n vertices across the top labeled v_1 through v_n. Directed edges leading from v_1 to v_2 all the way to v_n. One vertex at the bottom, v, with edges connecting v to every v_i. v_1 to v is a directed edge, and v to v_n is directed, the others are undirected.
    We can assume that the graph is directed as above.

    Case 1

    Now assume that the second edge goes into the path. Then, starting at the path we can go down the first edge and back up the second edge into the path -- continuing down the path we reach all the vertices, so we have a Hamiltonian path. In this way the added vertex becomes the second town in the path. We can now assume that the second edge is directed towards the remaining vertex.

    gif showing two paths. First is v_1 to v to v_2, then through to v_n. Second is v_1 to v_2, down to v, up to v_3, then all the way to v_n.
     The Hamiltonian paths formed in Cases 1 and 2

    Case 2

    For the next case, assume that the third edge points to the path. Then by the same logic we can re-route the path so that the added vertex is the third town visited -- follow the first two towns in the path, then go down to the added vertex, then back up and continue. So, there's a Hamiltonian path in this case too.

    Following the same logic, we can assume that all the edges connecting \(v\)  and \(v_1,...,v_n\) are directed away from the old path except for the edge between \(v\) and \(v_n\)

    Thinking Mathematically

    Let's summarize what we did from a more general point of view. We started with a framework (universal towns in complete directed graphs) and asked a question ("Can we produce universal towns by changing road directions; if so, what's the best we can do?"). By working with specific examples we showed this was possible and collected data on how many direction changes it took to create new universal towns. Analyzing this data led us to a conjecture ("With only one change in direction every town can be made universal") which we later proved. Like every other scientific discipline, math utilizes the scientific method to produce results. Half of the battle within mathematics is creating a useful framework.  

    Proving our conjecture also illustrated some important, general math concepts. We started with an initial conjecture about universal towns, and after introducing Hamiltonian paths we reformulated it to a conjecture about them ("Every complete directed graph has a Hamiltonian path"). We benefited from this because complete graphs contain smaller complete graphs within them -- this works well with our new proof method, induction. The key idea is to discover meaningful properties of the framework and translate challenging problems into ones more compatible with these properties.

    Quiz Questions

    Question 1

    C.

    Teaching Tips

    Students may not know where to start, for example due to being uncomfortable with mathematical language. Have them start by writing out the positive integers {1,2,3,...}, then testing the inequality with some of these. They will realize the inequality is probably true and be able to eliminate A. To prove this by induction, students need to identify a base case and an inductive step. As is usual, the base case is the simplest one, here it is testing the inequality for the smallest positive integer 1. The inductive step in words would be something like "If the inequality is true at a positive integer, it is true for the next one". We write an arbitrary positive integer as \(n\), so that the next one is \(n+1\). We cannot just test the inequality for \(n+1\) and work backwards, using the inductive hypothesis somewhere, to arrive at a truth. We must work forwards from the inductive hypothesis to arrive at the inequality for \(n+1\). Starting from \(n \leq n^2\), adding 1 to both sides gives \(n+1 \leq n^2 +1\). This is almost what we want, but the right hand side is \(n^2 +1\) not \((n+1)^2\). However, since \(n \geq 0\) we can add \(2n\) and get \(n+1 \leq n^2+1 \leq n^2+2n+1 = (n+1)^2\). So choice C is correct.

    B sounds tempting because we know that \(1 \leq n\) and we can just multiply both sides by \(n\). Although another proof exists, this doesn't mean that a proof by induction doesn't exist! Asserting that a type of proof does not exist is a rather strong statement.

    Question 3

    Base case: There is a prime number. Inductive step: Given a prime number, we can always construct another larger than it.

    Teaching Tips

    There are a couple points to make here. First, we're trying to show that there are infinitely many prime numbers. So the simplest claim is that there is a prime number. The statement "1 is a prime number" is false, and is meant to remind students that the base case is not necessarily

    Question 1

    Consider the following claim.

    Claim: For every positive integer \(n\) we have that \(n \leq n^2\).

    Which of the following is true?

    A. The claim is false.

    B. The claim is true, but not provable by induction.

    C. The claim can be proven using induction.

    Question 2

    Consider the following claim.

    Claim: There are infinitely many prime numbers.

    We know the claim is true from Lesson 2.1 using a proof by contradiction. If we were to prove this by induction, what would the base case and inductive steps be? Choose one option from each column.

    Base case:

    Inductive Step:
    There is a prime number.Given a specific prime number, we can always construct another.
    1 is a prime number.Given an arbitrary prime number, we can always construct another.
    There are infinitely many integersGiven a prime number, we can always construct another larger than it.

     

    Homework Questions

    Solutions

    Question 1

    Part A

    One, two, and three scales, respectively.

    Part B

    An example conjecture is "Discerning the magic stone between \(3^n\) identical-looking stones requires \(n\) many scales." Anything similar is valid.

    Teaching Tips

    Part A is just going back to the original Magic Stone Puzzle lesson and homework, guide them towards it if necessary.

    Part B is pattern recognition -- writing \(3=3^1, \ 9=3^2, \ 27=3^3\) may make this more obvious.

    Question 2

    Part A

    The base case is "It take one scale to find the magic stone between three identical-looking stones." The inductive step is "If it takes \(n\) many scales to find the magic stone in \(3^n\) many identical-looking stones, then it takes \(n+1\) many scales to find it when there are \(3^{n+1}\) many identical-looking stones" (or similar).

    Part B

    The base case is proven by weighing one rock one each side of the scale, and leaving the remaining one off to the side. Either the scale tips, in which case the magic stone is the heavier one, or it does not, in which case the magic stone is not on the scale.

    To prove the inductive step, assume for \(3^n\) many identical-looking stones it takes \(n\) scales to find the magic stone. We need to show that it takes \(n+1\) many scales for \(3^{n+1}\) many stones. Divide the stones into three groups of \(3^n\) many each. Weigh two of the three groups and leave the remaining one off to the side. As before, either the scale tilts or it does not -- either way we know which group of \(3^n\) stones the magic stone is in. This process used one scale, and by applying the inductive hypothesis we know \(n\) many more scales are required. In total this gives \(n+1\) scales as desired.

    Teaching Tips

    For Part A, remember that the base case is heuristically the simplest one. Here, simplest should be smallest number, so three it is. Some students may be confused why it isn't one -- remind them that the conjecture is really for positive powers of three. It's also true for \(n=0\) (since the only stone must be the magic stone, and thus we need no scales), but this isn't a valid base case since the proof is a tautology.

    In Part B, the base case is proven in the Magic Stone Puzzle lesson, and students are welcome to cite this instead of repeating the argument. However, going through the proof may be useful for proving the inductive step, since the form is nearly the same. If students are having trouble with the inductive step, have them work backwards. What is the inductive hypothesis? We need to use it somewhere, so how do we get there? In other words, the inductive hypothesis is a statement about \(3^n\) many stones. The first thing we should do is try to narrow down the magic stone's location to a group of \(3^n\).

    In the Magic Stone Puzzle we saw how to use a scale to find a magic stone between identical-looking stones.

    Question 1

    Part A

    Write how many scales were necessary to find the magic stone when there were three, nine, and twenty seven identical-looking stones.

    Part B

    Conjecture how many scales are necessary to find the magic stone between \(3^n\) identical-looking stones. 

    Question 2

    We can use induction to determine how many scales are necessary to find the magic stone.

    Part A

    State the base case and inductive step.

    Part B

    Using your answer to Part A, prove the conjecture. You may use pictures to prove the base case and inductive step.