Presenting a theorem or definition and then allowing students to consider whether figures met the criteria described worked well. This enabled them to then construct their own representations and provided for deeper discussions on the characteristics of graphs. The idea of proving ideas really took hold during the unit. One example was during the discussion of Hamilton circuits. When asked what characteristics would indicate the existence or absence of a circuit, students discussed the presence of vertices of degree 1 or the presence of cut edges. They were able to articulate specifically why this would preclude the presence of a Hamilton circuit. They were then able to extend this idea for multiple vertices of degree 1 and provide an argument that for a Hamilton path to exist the number of vertices of degree 1 would have to be less than 3. To me, this was exciting stuff. This example is reflective of how the entire unit progressed.
The next unit covers number theory and cryptography. As this veers back to a more cerebral topic, the graph theory provided a good break into a more visual and hands-on topic.
Unit 2
– Graph Theory
The second unit focuses on graphs and trees. This unit includes graph
representation, traversing paths, coloring graphs, tree traversal and spanning
trees. Both historical problems such as the bridges of Konigsberg and current
issues will be discussed in the context of graphs and trees.
1.
U3-01 intro to graphs
a.
Mail delivery problem
i.
What’s the shortest time you found
b.
Delivery Investigations
i.
Five paths
c.
Konigsberg Bridges
i.
State problem and see what students think
ii.
Show representation and discuss
d.
Define graph
i.
Show example of same graph drawn two different ways
1.
Be sure students understand how these are representing the same graph
e.
Define loop, adjacent vertices, path, circuit, Euler path, Euler circuit
i.
Clarify using graph to illustrate definitions
f.
Define degree of vertex, even and odd, connected, component, and cut
edge
g.
Practice drawing graphs with specific characteristics
i.
Problem 7. Draw a graph which has 6 vertices, 4 loops and 2 multiple edges.
ii.
Problem8. Draw a graph with 5 vertices, each of degree 4, which has no loops or
multiple edges.
iii.
Problem 9. Draw a graph with 3 vertices of degree 2 and 2 vertices of degree 3.
iv.
Problem 10. Draw a graph with 2 vertices of degree 2 and 3 vertices of degree 3.
v.
Problem 11. Draw a graph with 1 vertex of degree 1, 2 vertices of degree 2, 3
vertices of degree 3 and 4 vertices of degree 4.
vi.
Problem 12. Draw a graph with 8 vertices and 6 edges which contains no circuit at
all.
vii.
Problem 13. Draw a connected graph with exactly 3 edges that does not have an Euler
path.
h.
Exit
i.
What graph terms make the most sense to you? What makes
these understandable to you?
ii.
What graph terms are the most confusing to you? What are some
things you can associate with each term that will help you to recognize and
understand their meaning?
2.
U3-02 Graph Theorems
a.
Odd vertex theorem
i.
State and have students discuss why
ii.
[bring in
induction here or in conjunction with some Euler theorems?]
b.
Even vertex theorem
i.
State and have students discuss why
c.
What does Odd and Even vertex theorems imply about graphs having Euler
paths and Euler circuits?
d.
First Euler path and circuit theorems
i.
First Euler Path Theorem. If a graph has an Euler path,
then
1.
it must be connected and
2.
it must have either 0 or 2 odd vertices.
ii.
First Euler Circuit Theorem. If a graph has
an Euler circuit, then
1.
it must be connected and
2.
it must have no odd vertices.
iii.
Draw examples
e.
Theorems tell when graphs won’t have Euler path or circuit
i.
Will all remaining connected graphs have Euler paths or
circuits?
ii.
discuss
f.
Fleury’s Theorem
i.
Explain steps
g.
Show graph #5 from prior lesson
i.
Does Fleury’s theorem apply?
ii.
How can you modify the graph so that Fleury’s theorem applies?
h.
Students modify graph and traverse following rules
i.
What conclusions can you make about when a graph has an Euler path or an
Euler circuit?
j.
Second Euler Path theorem and circuit theorem
i.
Second Euler Path Theorem
1.
If a graph is connected and has exactly 2 odd vertices,
then it has an Euler path.
ii.
Second Euler Circuit Theorem
1.
If a graph is connected and has no odd vertices, then it
has an Euler circuit (which is also an Euler path).
k.
Show graph #5, can’t bulldoze through neighborhood
i.
Minimum multiple edges that can be added to apply Fleury’s theorem is
called Eulerization of graph
l.
Euler path circuit ws1
m.
Euler path circuit ws2
n.
Exit
i.
Summarize understanding of Euler paths and Euler circuits
ii.
What questions do you have about graphs, paths, and circuits
3.
U3-03 Mail route practice
a.
Simple graph (page 12 of Clark’s graph theory)
b.
Original neighborhood problem from U3-01
c.
Park-pond graph (page 13 from Clark’s graph theory)
i.
Mail Route Practice Handout
d.
Exit
i.
What are things to remember when making an Eulerization of a graph or
finding an Euler path or circuit?
4.
U3-A1 quiz on graphs
5.
U3-04 Paths
a.
Hamilton path - a simple path
that passes through every vertex exactly once
b.
Hamilton circuit – a simple circuit that passes through every vertex
exactly once
c.
What are the similarities and differences between Euler and Hamilton
paths and circuits?
d.
Examples
i.
Questions about which could ever have path or circuit
ii.
Have student’s conjecture about when a graph cannot have a Hamilton path
and/or circuit
1.
A simple graph with one vertex of degree one cannot have a
Hamilton circuit.
2.
A simple graph with 3 or more vertices of degree one cannot have a
Hamilton path.
3.
A simple graph with a cut
edge cannot have a Hamilton circuit.
4.
A simple graph with an Euler path has a Hamilton path.
e.
Dirac’s Theorem – a simple graph with 3 or more vertices such that the
degree of every vertex equals at least half the number of vertices has a
Hamilton circuit
i.
Show previous graphs and ask if any fit the theorem’s requirements
f.
Ore’s Theorem – a graph with 3 or more vertices such that the degrees of
every pair of non-adjacent vertices sum to the total number of vertices has a
Hamilton circuit.
i.
Show previous graphs and ask if any fit the theorem’s requirements
g.
For each theorem, draw a graph that meets the theorem’s requirements
h.
Practice
i.
Use the theorems to determine if a Hamilton circuit exists
i.
Exit
i.
The reason I find Hamilton path and circuits easy to work with is
because____________.
ii.
The aspect of Hamilton paths and circuits I found most confusing and/or
difficult was ____________ because __________.
6.
U3-05 Planar graphs (Rosen page 718 and JIBLM)
a.
Can these three houses be connected to the three utilities without any
utility lines crossing?
b.
Planar graph: A graph that can be drawn in the plane without and edges
crossing and maintains all the same edge connections.
c.
When attempting to determine if a graph is planar, it is often helpful
to think of the edges as being made from rubber bands. Vertices may be moved
around if that is helpful. Are any of the following graphs planar? (Show four
graphs from JIBLM)
d.
Can this graph be drawn as planar? (Show 3-D cube.)
e.
How might you determine if a graph is planar or not?
i.
Discuss ideas and check
f.
Look at the following graph. What is the largest subset of vertices that
can be easily drawn as a planar graph.
g.
Using the idea just discussed, can the following be drawn as a planar
graph? (Show original house-utility problem.)
h.
Euler’s formula
i.
Follow jiblm investigation
ii.
On a separate sheet of paper, draw seven different connected
planar graphs. Label them G1, G2, G3, G4, G5, G6 and G7.
iii.
Create a table for the numbers faces (f), vertices (v) and edges
(e) for each graph.
iv.
When you are finished examine your answers and look for a
relationship between these values that would allow you to predict one of them
if someone tells you the other two.
v.
I have a connected planar graph with 257 vertices and 192 faces.
How many edges does it have? How can you know for sure if your guess is
correct?
vi.
On a separate sheet of paper draw a connected planar graph G with
exactly 9 edges. You may include in it a loop (edge connecting a vertex to
itself) and a multiple edge (more than one edge between the same two vertices).
Be sure that it has several different faces. Now, on another sheet,“grow” the
same graph as a sequence of 10 partial connected planar graphs labled G1, G2,
G3, G4, G5, G6, G7, G8, G9, G10 = G, like this.
1.
1. Start with a single vertex as G1.
2.
2. Construct each graph from the previous one doing one of the
following:
3.
(a) Add a new vertex and a new edge connecting it to an old
vertex.
4.
(b) Add a new edge connecting two existing vertices.
vii.
Examine each of your graphs and complete the table.
viii.
Do each of the following.
1.
Tell what the value of f
+v−e is for a single vertex (G1).
2.
Tell how the construction
2(a) affects the value of each of f , v, e and f +v−e.
3.
Tell how the construction
2(b) affects the value of each of f , v, e and f +v−e.
ix.
Euler’s Theorem
1.
If a connected planar graph
has f faces, v vertices, and e edges
then f + v - e = ?
i.
Prove that a graph is not planar using Euler’s Theorem.
i.
Need help on justifying
lemma before can include this piece.
j.
Exit
i.
The most interesting thing I learned about planar graphs was
____________. I found this interesting because ____________.
ii.
One question I have about planar graphs is _________?
7.
U3-06 Isomorphisms and Complete and Self-complimentary graphs
a.
Provide an example of two drawings that represent the same graph
b.
Two drawings are isomorphic if and only if all adjacent vertex
relationships are maintained. Label and demonstrate this using the example
graph.
c.
What are conditions that would indicate that two graphs are not
isomorphic?
i.
Have students discuss and list ideas
1.
Have students provide counter-examples for those that are incorrect
d.
Using these ideas, determine if the following pairs of graphs are
isomorphic or not (using examples from Rosen)
e.
Complete the Isomorphic Graphs Worksheet and indicate explicitly why or
why not each pair of graphs is isomorphic.
i.
For problem 6, draw in extra edges to make each vertex degree five and
ask students to consider whether these are now isomorphic.
f.
A complete graph of n vertices, denoted by Kn, is a simple
graph that contains exactly one edge between each pair of distinct vertices.
i.
Draw Kn for n=1-6
g.
Counting connection
i.
Counting edges
1.
How many edges does K10 have?
2.
How many edges does K100 have?
3.
How many edges does Kn have?
ii.
Counting Hamilton circuits
1.
How many Hamilton circuits exist for K1 - K5?
2.
How many Hamilton circuits exist for Kn?
iii.
Note: these
problems spiral nicely back to counting, Pascal’s triangle, figurate numbers,
finite differences, and Gaussian summation
h.
The complement of a graph G, consisting of n vertices, is a graph
that also has n vertices and contains all of the edges that are not in G but
are in Kn. The complement is denoted by G-bar or Gc.
i.
Can make connections to complements in probability.
ii.
Draw the complement of the
following graphs
1.
Use rectangle, star, and triangle
i.
If two graphs G and H are isomorphic, does this mean that G-bar
and H-bar are also isomorphic? Prove or provide a counter-example?
j.
Can a graph ever be self-complementary? What would this look like?
k.
What characteristics must a graph possess in order for G to be
isomorphic to G-bar?
i.
Note: this question is posed as
a preview to the number theory work, specifically modular congruences, in the
next unit.
l.
Exit
i.
What did you find most interesting about isomorphisms, complete
graphs, and complementary graphs?
ii.
What questions do you still have about these topics?
8.
U3-07 Graph coloring (Rosen page 727) [needs to be developed – no time this year]
a.
Definitions
b.
Chromatic number
c.
Four color theorem
d.
Examples
e.
Practice
9.
U3-08 Simple graph proofs
a.
These are a series of problems presented by Dr. Patty McKenna at the
annual NCTM conference in Denver, 2013. [include
if time permits – may want to make some of these mid-term questions]
10. U3-A1 Assessment
on graphs
