Graph Theory Lesson Plan
This lesson is designed to develop students' modeling skills by introducing them to graphical representations of
real world data, maps, and graphs.
Organize and consolidate their mathematical thinking through communication
Communicate their mathematical thinking coherently and clearly to peers, teachers, and others
Analyze and evaluate the mathematical thinking and strategies of others
Use the language of mathematics to express mathematical ideas precisely
Teachers will need:
Students should have:
- a firm understanding of maps and how to navigate them.
Students must be able to:
- perform basic mouse manipulations such as point,
click and drag.
- use a browser such as Netscape for experimenting with
Students will need:
- Focus and Review
- Have students work on the
Town of Iceberg
problem as a review of graphs and an introduction to edges and vertices.
Students will lean how mathematics can be used to model real world situations. Students
will be exposed to algorithmic thinking and problem solving.
- Guided Practice
- Have students hypothesize a graphical model of them shaking hands with
everyone in the room.
- After all of the students have a model, allow students to actually get up and act
out the model.
- Record the results up on the board, or allow students to
develop a method to prove their initial model.
- Teacher Input
- Explain the Hand-Shaking Lemma to the students. This is what they just acted out.
- Define edge and vertex.
- Ask the students, "What will happen when more people are added?" or "When less people are present?"
- Define the term complete graph.
- Split students up into small groups, and have them explore other types of graphs with the
- Assign each group to a specific applet or type of graph.
- Each group should understand their graph well enough to explain its characteristics to the
- Have students draw an example of their graph on the board and explain its characteristics.
- In our workshop we discussed circuits, wheels, bipartite, and planar graphs.
- Explain that there are other types of graphs as well, and that some graphs can represent
two types of graphs. Venn Diagrams can be introduced here if you desire.
- Hand out the Different Types of Graphs worksheet.
- Assign groups of students to one of the graphs on the sheet.
- Have students decide what
makes their graph different from the other graphs on the hand-out.
- Draw a chart on the board with the graph titles along the y-axis and questions along the x-axis.
- Questions -
- Can the graph type have multiple edges going to the same vertex?
- Are loops allowed?
- Is the graph
- Tell students which graph they have and allow them time to fill in the chart.
- Make the connection that these graphs can be represented by a circuit, wheel, bipartite, or planar
- Discuss real world applications of these types of graphs.
- Explain the rules of
Toss n' Sort .
- With the balls, play Toss n' Sort on the big graph outlined on the floor, or ground.
- Let students play the game with different variations. More/Less people/balls. Allowing them to
add more edges or take edges away.
- Toss n' Sort - Illustrates deadlock and routing in computer networks.
- Discuss what made the game easier and what elements made it harder to play.
- Talk about how the game relates to deadlock and routing in computer networks.
- Explain to the class the difference between a path and a circuit.
- Mention that a path can be of edges or vertices and the same applies to circuits.
- Define the rules for the circuit & path discovery activity.
- Either with large graphs the students can walk on or smaller graphs drawn on handouts.
- Split the students up into groups and assign them to a particular graph.
- Students should find a path through all the edges, a path through all the vertices, a circuit
through all the edges, and a circuit through all the vertices.
- Graphs do not always contain each of
these four characteristics.
- Students should record their paths and circuits on a piece of paper.
- Discuss the different types of graphs each student covered.
- Define Euler Path/Circuit and Hamiltonial Path/Circuit.
- Have students describe the paths and circuits they found using vocabulary words.
- Point out that not all graphs will have a Euler Path/Circuit or a Hamiltonian Path/Circuit.
- Talk about the Konigsberg Bridge Problem, and how to tell if a graph has an Euler
- Point out that there are different ways to move between vertices and other elements such as time
or distance, which influence the popularity of each route.
- Introduce the term weighted graph.
- Independent Practice
- Direct students to the Dijkstra's Applet.
- Allow students to play with and make conjectures about how the algorithm works to find
the shortest path.
- Discuss what the students think is Dijkstra's Algorithm.
- Define Dijkstra's Algorithm and walk through one example with the class.
- Explain that the algorithm looks for an Euler Path.
- Discuss the shortest Hamiltonian circuit problem and Traveling Sales-Being Problem with the class.