|
Study Guide
Tucker: Applied Combinatorics
§1.4 Planar Graphs
Dr. Lee Eimers
Revised 12 Sept. 2007 |
|
|
Introduction: An important question in graph theory is that of
whether a given graph can be drawn in the plane without any edges crossing
except when they meet at a vertex. In this section, we meet the definition
of planar graph and the conditions under which a planar graph is impossible,
starting from rather ad hoc arguments, proceeding with Kuratowski's Theorem,
and ending with Euler's formula.
Concepts and Vocabulary:
The following boldfaced (or italic) terms and phrases introduced
in this section.
Configuration
Connected |
Dual graph
Euler's Formula |
Kuratowski's Theorem
Planar graph |
Points of Interest:
1. The question of whether a map can be colored with a maximum
of four colors (The Four-Color Theorem) has been proven, but only with
the aid of the computer. Some people contend that since no human
has actually gone through the proof, that the theorem has not yet been
proven. What do you think?
2. Theorem 1 is also known as Kuratowski's Theorem, and is very
important in graph theory. It is interesting that it is obvious that
having a K5 or a K3,3 graph is sufficient to cause a graph to be nonplanar,
but its necessity is not obvious, that is, that any nonplanar graph MUST
have a K5 or a K3,3 configuration.
3. Euler's Formula only applies to connected graphs. Note
also that it only applies to planar graphs. (What would "region"
mean for nonplanar graphs anyway?) The corollary is also very important
in considerations of whether a particular graph is planar or nonplanar.
Homework Assignment:
Required Reading:
Chapter 1, Section 4 of text
Look up vocabulary terms above in Bondy and Murty
and Diestel, and read relevant sections
Graph Theory Lessons, Lesson 21: Planar Graphs
Graph Theory Lessons, Lesson 22: Dual Graphs
Do to hand in:#3(a,c,e,g only), 5, 9, 11, 15, 16, 18, 20, 27
(Hint for #9: Model the torus by a rectangle where the top edge
and the bottom edges will be
glued together and then the left and right edges are glued.
Thus, for example, you can draw
your lines to run off the top edge and back on the bottom.)
Enrichment problems:;
#6,7,10,12,13,17,19,24,25.
Thought for the Day
Whoever digs a pit will fall into it,
And he who rolls a stone will have it
roll back on him.
(Prov. 26:27, NKJV)
What goes around, comes around.
(Contemporary saying)
References:
Graph
Theory with Applications, by J. A. Bondy and U. S. R. Murty,
Online text found at http://www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/gtwa.html
Graph Theory, 3rd Ed., by R. Diestel,
Online text found at http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/