
Copyright (c) 1998, C. Heeren, T. Magliery, and L. Pitt.
This lesson and supporting materials may be copied for nonprofit educational
use only.
Motivation:
This lesson is an introduction to graphs and their uses.
The term "graph" refers to something different than the perhaps
already familiar graph of data, or graph of a function.
Instead, the term refers to
a collection of vertices (dots) and edges (connecting lines
or curves), much as you might see depicted in the back of an airline
magazine: A map of the country has connecting arcs drawn between a
pair of cities to indicate that the airline flies between those cities.
Graphs are nothing more than a graphical (pictorial) way of showing
how different things relate. Because the vertices may represent
any objects (not just cities),
and the edges may represent any relationship
(not just flight routes), a graph is an incredibly useful tool for
helping to understand relationships and for solving problems
in a wide variety of domains.
Because graphs are so useful, many computer programs have
been written for solving problems about graphs (some of which
we'll see in future lessons). Finally,
from a purely mathematical perspective, there is a theory of
graphs that in elegance, depth, and richness, rivals that from any area.
Standards:
NCTM K4: 1, 2, 3, 4, 9.
NCTM 58: 1, 2, 3, 4, 12.
NCTM 912: 1, 2, 3, 4, 7, 12.
Materials:

County road
cards.

"Instructions for Achieving Bliss"
overhead.

Overhead image of the
state of Bliss.

Contemplation
handout for each county.

Handout of graph application problems,
and handout of
solutions.
Lesson Plan:

Distribute all the county road cards. If you don't have 30 people,
use chairs for some of the cities. Just put the city card on the
seat or tape it to the back of the chair. Also, place the Instructions
handout on the overhead. If you have many less than 30 students,
eliminate one or more of the colors from the stack of cards.

Allow the students, following the instructions, to connect themselves
into a map of the state of Bliss. Each city card contains the city
name on one side, and a list of the cities to which it is directly
connected via a road, on the other. The students should connect
themselves with rope to the people holding the cities on their list.
(If you've borrowed our kit, use the colorcoded plastic rings to
represent each city, and have the children connect the ropes to the
rings instead of to themselves. Each child representing a city can
hold the corresponding ring. All cards of the same color are in the
same county, and these cities, when they appear on the list, are
written in plain type. Each different color card represents a
different county. When a city of a different county appears on a
player's list, it is underlined. Players should use white rope to
connect cities within counties, and yellow rope to connect cities in
different counties. We suggest that the yellow ropes be approximately
10 ft., and that the white ropes be no longer than a few feet. The
children should first make connections to cities within the same
county (same color), before connecting to other counties. Also, if
city A and B are connected, for example, then each will appear on the
list on the back of the other's card. These represent the same
connection; only ONE ROPE should be used to connect city A to city
B.

When all connections are made, place the map of Bliss on the overhead and
ask the students if it's the same as their configuration. They will
probably look quite different! Explain that this particular structure
only describes connectivity, not necessarily geography. The rope
lengths don't correspond to distances as we commonly refer to them.

So what is the structure? It's called a graph, and it is made up of
vertices (the cities), and edges (the roadways).
(These are also sometimes called nodes and arcs, respectively.)
Graphs can be used not only to represent physical relationships (cities linked
via roads, computers or telephones linked via network lines), but also
to represent logical relationships, biological relationships,
arithmetic relationships, temporal relationships, justaboutanyrelationships.
(We'll see examples shortly.)
How can a computer "see" or "understand" a graph? We have already
seen how to represent a graph as a list of connections. Each vertex
(city) has associated with it a list of the other vertices to which it
is connected (an "adjacency" list).
The list of city names on the back of each card is the adjaceny list for
that city. To demonstrate this representation, give the students the
following list, and ask them to draw the graph that it describes. Ask
them which county graph it corresponds to (Orange county).
VERTEX 
CONNECTED TO 
1 
4, 5, 6 
2 
4, 5, 6 
3 
4, 5, 6 
4 
1, 2, 3 
5 
1, 2, 3 
6 
1, 2, 3 
Notice that vertex 6 is listed as one of the vertices connected to
vertex 1, and vertex 1 is listed as one of those connected to vertex
6. These two entries come from the same edge  the one connecting 1
and 6.
 What if there were oneway roads in Bliss?
Yes, we'd draw an arrow (called a directed edge) showing the
direction that the edge points. Graphs with directed edges are called
directed graphs. (In a directed graph, if the list for
vertices connected to vertex 1 contains vertex 6, it need not be the case
(but it might be) that the list for vertices connected to vertex 6
contains vertex 1.) We'll see examples of directed graphs soon.

Discussion, still using the overhead: (students can sit) What can
we tell about the state of Bliss? (The overhead doesn't have city
names on it, but the students can help you find the towns on the
map.)

Can we tell how far it is from McCook to Kearney? Not exactly, though
we can tell how many different roadways we use in any walk between
them. From now on we'll refer to the number of roadways between any
two cities as the distance between them. This is the same as
saying that all the roads are one unit long.

Which city has the most traffic? Again, we can't tell exactly, but
we can guess based on which city has the most roadways adjacent to it.
Asking this question about Bliss is the same as asking which node has highest
degree in the graph representing Bliss. The degree
of a node is just the number of edges adjacent to it.

What is the shortest route from Stockville to Hastings? This is a
harder question. You can't be sure of the answer just by looking
at the graph for a second, but you may be able to come up with a system
for finding the answer.
 Next have the students untie the county ropes and pass out the
Contemplating Bliss handout, one or more to each county. Let the
groups analyze their county graph using the questions on the handout
as a guide.
 The county graphs are designed so that they're each interesting
in some classical way. Allow each group time to briefly express to
the entire class what they think is "special" about their graph.
Here's what we hope they will say (if they don't mention these
characteristics, point them out):

Red  First, the graph is not connected, which means you can't
get from every vertex to every other. Second, no edge can be added to
the group of 4 vertices (nor actually to the group of 2) because every
possible edge is already included. Such a graph is said to be
complete. Are any of the county graphs complete? Answer: no,
you can add an edge to each one.

Orange  This is the hardest one. The vertices can be separated into
two groups so that no vertices within groups are attached. In other
words, the vertices can be divided into two groups so that all the
edges cross from one group to the other. Such a graph is called
bipartite. Are any of the other county graphs bipartite?
Answer: Yes, green and blue are. Let the students figure out
how.

Yellow  First, this graph can be drawn without crossing any
edges (but there may also be ways to draw it with crossing edges).
Such a graph is called a planar graph. Which of the other
county maps are planar? Answer: all but Orange. Second, when this
graph is drawn in the plane so that no edges cross, if you put your
pencil in any region (not on an edge or vertex), the boundary around
that region is made of 3 edges. Such a graph is called a
triangulation (even though the regions may not look like
triangles).

Green  This graph is a cycle. The graph can be drawn with
vertices arranged in a circular pattern, and edges only connecting
each vertex with the vertex to its right and to its left.

Blue  This graph is a tree. There are no cycles, and the
graph is connected. If any edge is removed, the graph is no longer
connected.

Say something like, "Whew. We've learned a lot about the structure of
graphs, now let's talk about the things they're good for! Select a
number of different graph usage problems,
and distribute them to your students, who can either work in pairs or
independently. Be sure to suggest the questions given at the top of
the sheet, as points to think about when trying to represent one of
the problems or situations as a graph. In some cases, there is some
problem to be solved (e.g., "how can I get from McCook to Kearney?".
Ask them to explain the relationship between the solution for the
original problem, and the solution for the problem represented as a
graph. (In this case, in the graph we'd look for a path (a sequence
of edges) leading from McCook to Kearney). You should probably do a
few examples first for the students. In particular, it will be
helpful to do an example for each "type" of graph modeling problem.
(A useful one to go through with them is the one involving the man
with the boat, fox, chicken, and seed.) Allow the students plenty of
work time.

Ask for volunteers to demonstrate their graph example. It is both fun
and enlightening to see a variety of models.
Conclusion:
We've seen that graphs are easy to represent in a computer, and useful
in describing a huge variety of problems. The next step in recognizing
the beauty of graphs is to begin solving problems on graphs.
Evaluation:
County group Contemplation handouts might not be very useful for
assessment because the county graphs are so diverse. If you are
interested in seeing students' reflections on their county graphs,
allow them to add more thoughts to the handout during the whole class
discussion of the other county graphs so they can contrast their graph
to the others. You may also want to have each student write up the
group observations independently.
The graph examples completed by the students should reflect their
understanding of the material. Use a simple rubric to assess the
model writeups. An example rubric: 3 points for a clear correct
solution, 2 points for a correct but disorganized solution, and 1
point for an incorrect attempt.
Extensions:
The extensions to this lesson are endless.
A good place to start is the
graph theory
lessons and activities at the
Mega Math
web site.
Copyright (c) 1998, C. Heeren, T. Magliery, and L. Pitt.
This lesson and supporting materials may be copied for nonprofit educational
use only.
