MA 323A Combinatorial Geometry!
Notes on Planar Graph Theory
The following are brief notes on some of the graph theory concepts
that we'll be using.
Definition: A graph G is any network of points and lines.
We usually call the points vertices and the lines edges.
Since every graph is determined by it's set of vertices and edges,
we usually denote a graph by G=< V,E> .
A graph is called a planar graph if it is drawn in such a way that
the edges never cross, except at where they meet at vertices.
There is a direct connection between polyhedra and planar graphs,
namely that we can take any polyhedron and "project" it down onto
a flat piece of paper, turning it into a graph. This is sometimes
nice to do because graphs are easier to draw than 3D polyhedra, and
the planar graph contains all the network structure information
of the polyhedron, like how many vertices, edges, and faces it has.
Below is shown how we can turn the cube into a planar graph.
In class we drew the planar graphs of other polyhedra, like
the tetrahedron, which has 4 triangle faces and each vertex degree 3.
 the octahedron, which has 8 triangle faces and each vertex degree 4.
 the dodecahedron, which has 12 pentagon faces and each vertex degree 3.
We also talked about the icosahedron, which has 20 triangle faces and each
vertex degree 5, but we didn't draw one. These 5 polyhedra (including the
cube) are the five Platonic solids They are the only polyhedra in
existence that have all sides the same and whose sides are regular polygons.
(We might try to prove that later!)
Definition: If G is the graph of a polyhedron, let G* denote
the graph of the planar dual of G. We construct G* in
the following way:
 for every face of G we make a vertex of G*, and
 two vertices in G* will form an edge if and only if the corresponding
faces in G are next to one another (that is, they share an edge).
Below is shown how we make the dual of the cube:
But look! If we rearrange the vertices in the dual G* we get the following:
Thus we see that the dual of the cube is the octahedron! Wow!
It also makes sense that if we took the dual of the octahedron then
we'd get the cube back, right?
Euler's Formula
The following are some things that we learned on the Thursday, Jan. 27th
class, or things that we'll be learning soon!
Euler's Formula: If G is a planar graph with V vertices and E
edges and F faces, then we have the following formula:
V  E + F = 2
We'll be proving Euler's Formula in class, and the proof will be by induction!
So get ready for it.
Now, I mentioned in class that we can use Euler's Formula to prove
that there are exactly 5 Platonic solids, and I ask you to do this
yourself on an upcoming problem set. Here are some notes that help you
get started:
Definition: If v is a vertex in a graph, then the degree of
v is the number of edges coming out of v. We denote this by deg(v).
Similarly, the degree of a face f in a planar graph is the number
of edges going around the face. (Thus a triangle face has degree 3, a
hexagon face has degree 6, etc.) We denote this by deg(f).
Here's a classic graph theory Theorem:
Theorem: Let G be any graph and let E be the number of edges in G.
Then if v1, v2, v3, ... vn denote the vertices in G, we have
deg(v1) + deg(v2) + deg(v3) + ... + deg(vn) = 2E
Proof: Go to every vertex in G and add up the number of edges
coming out of that vertex. This is just suming up the degrees of
the vertices, so we'll get the lefthand side of the above formula.
On the other hand, this will be adding up the total number of edges in
the graph, EXCEPT that we'll actually be counting each edge twice, right?
This is because each edge is adjacent to two vertices. So if an edge
e is connecting vertices vi and vj, we'll count e once at vertex vi and
again at vertex vj. Thus we're counting each edge exactly twice, which
gives us 2E, the righthand side of the above formula. Q.E.D.
Exercise: Use the same argument to show that if f1, f2, ..., fm
are the faces of a planar graph G, then
deg(f1) + deg(f2) + deg(f3) + ... + deg(fm) = 2E
So what does this tell us about the Platonic solids? Well, remember that
each Platonic solid must have each face be the same regular polygon,
which means that each face has the same degree. Also, each vertex will have
the same degree. (Hmmm ... does that need a proof, or do we already know this?
Hmmm...). Thus the previous Theorem tells us that if V is the number of
vertices in a Platonic solid and F is the number of faces, and if each vertex
has degree d and each face has degree k, then
dV = 2E and kF = 2E
There are lots of things we could do with this! For example, we could
write these as V = (2/d)E and F = (2/k)E, and then plug them into Euler's
Formula to get
(2/d + 2/k  1)E = 2
But E is positive, and so is 2. Thus (2/d + 2/k  1) must be positive.
That is,
2/d + 2/k > 1
Now, can you turn this into
(d2)(k2)<4
hmmmm? Sure you can! Now check out all the tools we have here.
We want to determine how many Platonic solids there are, and we can do this
by experimenting with different values of d and k. But some values of d and k
won't work at all! For instance, it doesn't make sense for a polyhedron
to have vertices of degree 1 or 2, right? So we know that d is greater than
or equal to 3. Also, a polyhedron can't have faces with fewer sides than
a triangle, so k is greater than or equal to 3. Further, by Problem (3) in
Probem Set number 1, we know that every planar graph must have a vertex of
degree less than or equal to 5. But since all the vertices in a Platonic solid
have the same degree, we must then have d < = 5. And since the same
must be true of the dual of this Platonic solid, we have k < = 5.
In summary,
3 < = d < = 5 and 3 < = k < = 5
which cuts down on the number of cases for d and k that we have to check!
So go ahead! Use (d2)(k2)<4 to see if any other cases of d and k are
impossible, and for the ones that are possible use (2/d + 2/k  1)E = 2
to compute how many edges the Platonic solid must have, and then use
V = (2/d)E and F = (2/k)E to compute the number of vertices and faces.
You should recognize the numbers that you get (is one the cube? is one the
octahedron? etc) and in this way prove that there are only 5
possibilities for the Platonic solids.
Return to Combinatorial Geometry Page
