Teacher Resources

Find a PDF Copy of the project, including student and teacher resources here. This may be used to help students who have difficulty using a computer.

Prerequisite Knowledge:

This project was not designed with one particular course in mind. Though it fits quite nicely with the Discrete Math curriculum, it could also be incorporated into sections of Integrated Math or certain parts of the IB Curriculum. Certainly, teachers looking to expand their students’ minds with some content outside of the set curriculum will find this project quite rewarding.
Before assigning this project, students should become relatively comfortable with the concept of a graph (specifically weighted graphs) and how they can be used to represent things. If students are not already at this stage, the teacher should consider splitting this project into two days, and provide considerable scaffolding for the creation of the graph.
The concept of a tree (a graph which contains no cycles) may or may not be introduced beforehand. The solution graph will be a minimal-weight spanning tree, and this project is one way to introduce the concept of trees. If trees have already been introduced, the teacher might consider asking more higher-level questions related to the solution graph and its properties as a tree.

Encouraging Higher-Order Thinking:

The graph of all the data will be the complete graph on five vertices (or K5) and will have exactly 10 edges. Because of the relatively low number of edges, students should be able to find the minimal-weight spanning tree for the set by inspection if given sufficient time. Since this can be done by inspection alone, make sure to ask students to attempt to generalize the process.
The questions for the group response ask for exactly this kind of higher-order thinking. Questions also ask students to engage in informal logic and deduction, particularly when asking about whether cycles may be a part of the minimal-weight graph. Students at some developmental stages may have difficulty grasping these concepts, and the proof is done by contradiction.

Utility of Graph Theory:

Indeed most students, and perhaps some mathematicians, see graph theory as simply a novel tool to solve problems that have other, more numerical solutions. It should be stressed to students that this is an important way to visualize and think about certain types of problems, specifically those involving networks (in this case, the connected sets of airports).
Students who are heavily visual learners may incorporate this method readily into their skill set. Others may use it only when specifically asked to do so. Both are perfectly acceptable, but asking students at this time to think only in these terms will help broaden all students’ understanding.

Sample Solution:

Enter data so that the entry corresponding to (City A, City B) represents the distances from City A to City B.

	City A	City B	City C	City D	City E
City A Code:_______	0	25	40	15	90
City B Code:_______	25	0	32	60	52
City C Code:_______	40	32	0	29	47
City D Code:_______	15	60	29	0	38
City E Code:_______	90	52	47	38	0

Weighted Graph of Data

Sample Weighted Graph

Solution Graph

Sample Solution Graph

Questions to Answer in Your Group Write-Up

Show and explain how you came up with your solution. Do you think this method would always work for solving this type of problem?
- Method should be to add edges of shortest length without creating cycles until all vertices are connected.
What are some properties of your solution graph? Does it contain cycles? Could it contain cycles?
- Minimal-weight spanning tree will NEVER contain cycles. Can prove via contradiction.
Is finding the shortest path connecting all these airports really the best way to do things? What problems do you think this might cause for the airport?
- No right or wrong answer here, just have students think critically about their results.

Rubric

	Excellent 5 4	Satisfactory 3 2	Below Expectations 1 0
Online Research ___________	Students navigated web resources easily and obtained accurate information from both websites.	Students navigated web resources and obtained accurate information from both websites.	Students needed help navigating web resources and/or obtained incorrect data.
Data Table ___________	Students’ data is organized neatly and accurately in the table.	Students’ data is organized somewhat neatly and accurately in the table.	Students’ data is unorganized or presented incorrectly in the table.
Graph ___________	Students’ data is organized neatly and accurately in the graph.	Students’ data is organized somewhat neatly and accurately in the graph.	Students’ data is unorganized or presented incorrectly in the graph.
Analysis and Conclusions ___________	Solution is correct and responses to questions are thoughtful and mathematically relevant. Shows full mastery of solution method.	Solution is correct and responses to questions are thoughtful and mathematically relevant. Shows some mastery of solution method.	Solution is incorrect and/or responses to questions are neither thoughtful nor mathematically relevant. Shows no mastery of solution method.
Individual Reflection ___________	Reflection shows thoughtful consideration and reflection on the mathematical process. It is well written and organized with no mechanics problems.	Reflection shows some consideration and reflection on the mathematical process. It is well written and organized with no mechanics problems.	Reflection shows no consideration or reflection on the mathematical process. It is poorly written and organized with mechanics problems.

Total: ______/ 25

Comments: