Subsection1.4.1Non-planar Graphs
¶
Activity26
For the complete graphs \(K_n\text{,}\) we would like to be able to say something about the number of vertices, edges, and (if the graph is planar) faces.
(a)
How many vertices does \(K_3\) have? How many edges? If \(K_3\) is planar, how many faces should it have?
(b)
How many vertices, edges and (if planar) faces would \(K_4\text{,}\) \(K_5\) and \(K_{23}\) each have?
(c)
What about complete bipartite graphs? How many vertices, edges, and faces (if it were planar) does \(K_{7,4}\) have?
Not all graphs are planar. If there are too many edges and too few vertices, then some of the edges will need to intersect. For example, consider \(K_5\text{.}\)
If you try to redraw this without edges crossing, you quickly get into trouble. There seems to be one edge too many. How could we prove this?
Activity27
(a)
The graph \(K_5\) has \(5\) vertices and 10 edges. Explain why it would need to have \(7\) faces if it were planar.
(b)
Now get at the number of faces another way: each face must be bordered by at least three edges. Why? Explain why we can conclude that \(3f \le 2e\text{.}\) Where does the 2 come from?
(c)
We now have that for \(K_5\text{,}\) the number of faces is \(f = 7\text{,}\) and also \(3f \le 20\text{.}\) How is this possible? What can we conclude?
Before proceeding, consider carefully the style of proof used here. This is a proof by contradiction. We assumed the opposite of what we wanted to show. From that, we arrived at a contradiction, a statement that is necessarily false. Is it valid to conclude that our original assumption is false?
Recall the truth table for an implication \(P \imp Q\text{:}\)
| \(P\) |
\(Q\) |
\(P\imp Q\) |
| T |
T |
T |
| T |
F |
F |
| F |
T |
T |
| F |
F |
T |
In a proof by contradiction, we assume \(P\) (which will be the negation of our desired conclusion) and derive \(Q\text{,}\) a contradiction. That valid derivation allows us to conclude \(P \imp Q\) is true! But we know that \(Q\) is false. What does that say about \(P\text{?}\) If the implication is true and the consequent (“then” part) is false, it must be that we are in row 4 of the truth table. In that row, \(P\) is false. So we are justified in concluding \(\neg P\text{.}\)
In our case, \(P\) was the statement “\(K_5\) is planar.” So when we get a contradiction (a false \(Q\)), we can conclude that \(K_5\) is not planar. Note that even though we are proving something about a graph that does not satisfy Euler's formula for planar graphs, by using a proof by contradiction, we get to use the formula.
Here are a few more examples of this proof strategy, specifically to show graphs are not planar.
Activity28
The other simplest graph which is not planar is \(K_{3,3}\)
(a)
Following the same proof outline as you used for \(K_5\text{,}\) what value do you find for \(f\) and what can you conclude from the inequality \(3f \le 2e\text{?}\)
HintIf you assume \(P\) and conclude \(Q\text{,}\) but \(Q\) is true, can you say anything about \(P\text{?}\) What row(s) of the truth table for \(P \imp Q\) are you in?
(b)
The 3 in \(3f \le 2e\) came from the observation that the any face in \(K_5\) must be bounded by at least three edges. Is that the best we can do for a bipartite graph? Find and justify an improved inequality between \(f\) and \(e\text{.}\)
In general, if we let \(g\) be the size of the smallest cycle in a graph (\(g\) stands for girth, which is the technical term for this) then for any planar graph we have \(gf \le 2e\text{.}\) When this disagrees with Euler's formula, we know for sure that the graph cannot be planar.
You might wonder whether every graph that is not planar can be shown to be non-planar this way.
Activity29
The graph show below is not planar. Let's prove it.
(a)
What is the girth of this graph? What can you conclude from Euler's formula and the inequality \(gf \le 2e\text{?}\)
(b)
Try proving the following graph is not planar using our standard approach.
(c)
Could it be that the original graph is planar but the subgraph is not? What can you conclude?
If a graph contains a non-planar subgraph, then the graph cannot itself be planar. This gives us another method of proving a given graph is not planar: find a non-planar graph, perhaps \(K_5\) or \(K_{3,3}\) inside it.
From the other direction, you can think of starting with \(K_5\) or \(K_{3,3}\) and adding edges as well as adding vertices in the middle of edges (called subdividing the edge) to build a larger graph that is definitely not planar. Surprisingly, every non-planar graph arises this way, a result called Kuratowski's Theorem.
Euler's formula can also be used to prove results about planar graphs.
Activity30
Prove that any planar graph with \(v\) vertices and \(e\) edges satisfies \(e \le 3v - 6\text{.}\)
HintThe girth of any graph is at least 3.
Activity31
Prove that any planar graph must have a vertex of degree 5 or less.
HintDo a proof by contradiction. What is the smallest number of edges such a graph would possess?
Subsection1.4.2Polyhedra
¶
Activity32
A cube is an example of a convex polyhedron. It contains 6 identical squares for its faces, 8 vertices, and 12 edges. The cube is a regular polyhedron (also known as a Platonic solid) because each face is an identical regular polygon and each vertex joins an equal number of faces.
There are exactly four other regular polyhedra: the tetrahedron, octahedron, dodecahedron, and icosahedron with 4, 8, 12 and 20 faces respectively. How many vertices and edges do each of these have?
Another area of mathematics that uses the terms “vertex,” “edge,” and “face” is geometry. A polyhedron is a geometric solid made up of flat polygonal faces joined at edges and vertices. We are especially interested in convex polyhedra, which means that any line segment connecting two points on the interior of the polyhedron must be entirely contained inside the polyhedron.
Notice that since \(8 - 12 + 6 = 2\text{,}\) the vertices, edges and faces of a cube satisfy Euler's formula for planar graphs. This is not a coincidence. We can represent a cube as a planar graph by projecting the vertices and edges onto the plane. One such projection looks like this:
In fact, every convex polyhedron can be projected onto the plane without edges crossing. Think of placing the polyhedron inside a sphere, with a light at the center of the sphere. The edges and vertices of the polyhedron cast a shadow onto the interior of the sphere. You can then cut a hole in the sphere in the middle of one of the projected faces and “stretch” the sphere to lay down flat on the plane. The face that was punctured becomes the “outside” face of the planar graph.
The point is, we can apply what we know about graphs (in particular planar graphs) to convex polyhedra. Since every convex polyhedron can be represented as a planar graph, we see that Euler's formula for planar graphs holds for all convex polyhedra as well. We also can apply the same sort of reasoning we use for graphs in other contexts to convex polyhedra. For example, we know that there is no convex polyhedron with 11 vertices all of degree 3, as this would make 33/2 edges.
Example1.4.1
Is there a convex polyhedron consisting of three triangles and six pentagons? What about three triangles, six pentagons and five heptagons (7-sided polygons)?
SolutionHow many edges would such polyhedra have? For the first proposed polyhedron, the triangles would contribute a total of 9 edges, and the pentagons would contribute 30. However, this counts each edge twice (as each edge borders exactly two faces), giving 39/2 edges, an impossibility. There is no such polyhedron.
The second polyhedron does not have this obstacle. The extra 35 edges contributed by the heptagons give a total of 74/2 = 37 edges. So far so good. Now how many vertices does this supposed polyhedron have? We can use Euler's formula. There are 14 faces, so we have \(v - 37 + 14 = 2\) or equivalently \(v = 25\text{.}\) But now use the vertices to count the edges again. Each vertex must have degree at least three (that is, each vertex joins at least three faces since the interior angle of all the polygons must be less that \(180^\circ\)), so the sum of the degrees of vertices is at least 75. Since the sum of the degrees must be exactly twice the number of edges, this says that there are strictly more than 37 edges. Again, there is no such polyhedron.
Activity33
I'm thinking of a polyhedron containing 12 faces. Seven are triangles and four are quadrilaterals. The polyhedron has 11 vertices including those around the mystery face. How many sides does the last face have?
Activity34
Consider some classic polyhedra.
(a)
An octahedron is a regular polyhedron made up of 8 equilateral triangles (it sort of looks like two pyramids with their bases glued together). Draw a planar graph representation of an octahedron. How many vertices, edges and faces does an octahedron (and your graph) have?
(b)
The traditional design of a soccer ball is in fact a (spherical projection of a) truncated icosahedron. This consists of 12 regular pentagons and 20 regular hexagons. No two pentagons are adjacent (so the edges of each pentagon are shared only by hexagons). How many vertices, edges, and faces does a truncated icosahedron have? Explain how you arrived at your answers. Bonus: draw the planar graph representation of the truncated icosahedron.
(c)
Your “friend” claims that he has constructed a convex polyhedron out of 2 triangles, 2 squares, 6 pentagons and 5 octagons. Prove that your friend is lying. Hint: each vertex of a convex polyhedron must border at least three faces.
To conclude this application of planar graphs, consider the regular polyhedra. Above we claimed there are only five. How do we know this is true? We can prove it using graph theory.
Theorem1.4.2
There are exactly five regular polyhedra.
Activity35
Recall that a regular polyhedron has all of its faces identical regular polygons, and that each vertex has the same degree. Consider the cases, broken up by what the regular polygon might be.
(a)
Case 1: Each face is a triangle. Let \(f\) be the number of faces and \(k\) the common degree of each vertex (since the polyhedron is regular). Find formulas for the number of edges and vertices in terms of \(f\) and \(k\text{.}\) Conclude from these the only possible values for \(f\) and \(k\text{.}\)
(b)
Case 2: each face is a square. Again, consider the possible cases for \(f\) and \(k\) (and conclude there is only one: the cube).
(c)
Case 3: Each face is a pentagon.
(d)
Explain why it is not possible for each face to be a \(n\)-gon with \(n \ge 6\text{.}\)
