Loading [MathJax]/jax/output/HTML-CSS/jax.js
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

4.2: Planar Graphs

( \newcommand{\kernel}{\mathrm{null}\,}\)
















































































!

When a connected graph can be drawn without any edges crossing, it is called planar. When a planar graph is drawn in this way, it divides the plane into regions called faces.

  1. Draw, if possible, two different planar graphs with the same number of vertices, edges, and faces.
  2. Draw, if possible, two different planar graphs with the same number of vertices and edges, but a different number of faces.

When is it possible to draw a graph so that none of the edges cross? If this is possible, we say the graph is planar (since you can draw it on the plane).

Notice that the definition of planar includes the phrase “it is possible to.” This means that even if a graph does not look like it is planar, it still might be. Perhaps you can redraw it in a way in which no edges cross. For example, this is a planar graph:

image-101.svg

That is because we can redraw it like this:

image-102.svg

The graphs are the same, so if one is planar, the other must be too. However, the original drawing of the graph was not a planar representation of the graph.

When a planar graph is drawn without edges crossing, the edges and vertices of the graph divide the plane into regions. We will call each region a face. The graph above has 3 faces (yes, we do include the “outside” region as a face). The number of faces does not change no matter how you draw the graph (as long as you do so without the edges crossing), so it makes sense to ascribe the number of faces as a property of the planar graph.

WARNING: you can only count faces when the graph is drawn in a planar way. For example, consider these two representations of the same graph:

image-103.svg image-104.svg

If you try to count faces using the graph on the left, you might say there are 5 faces (including the outside). But drawing the graph with a planar representation shows that in fact there are only 4 faces.

There is a connection between the number of vertices (v), the number of edges (e) and the number of faces (f) in any connected planar graph. This relationship is called Euler's formula.

Definition: Euler's Formula for Planar Graphs

For any (connected) planar graph with v vertices, e edges and f faces, we have

ve+f=2

Why is Euler's formula true? One way to convince yourself of its validity is to draw a planar graph step by step. Start with the graph P2:

image-105.svg

Any connected graph (besides just a single isolated vertex) must contain this subgraph. Now build up to your graph by adding edges and vertices. Each step will consist of either adding a new vertex connected by a new edge to part of your graph (so creating a new “spike”) or by connecting two vertices already in the graph with a new edge (completing a circuit).

image-106.svgimage-107.svg

What do these “moves” do? When adding the spike, the number of edges increases by 1, the number of vertices increases by one, and the number of faces remains the same. But this means that ve+f does not change. Completing a circuit adds one edge, adds one face, and keeps the number of vertices the same. So again, ve+f does not change.

Since we can build any graph using a combination of these two moves, and doing so never changes the quantity ve+f, that quantity will be the same for all graphs. But notice that our starting graph P2 has v=2, e=1 and f=1, so ve+f=2. This argument is essentially a proof by induction. A good exercise would be to rewrite it as a formal induction proof.

Non-planar Graphs

!

For the complete graphs Kn, we would like to be able to say something about the number of vertices, edges, and (if the graph is planar) faces. Let's first consider K3:

  1. How many vertices does K3 have? How many edges?
  2. If K3 is planar, how many faces should it have?

Repeat parts (1) and (2) for K4, K5, and K23.

What about complete bipartite graphs? How many vertices, edges, and faces (if it were planar) does K7,4 have? For which values of m and n are Kn and Km,n planar?

Not all graphs are planar. If there are too many edges and too few vertices, then some of the edges will need to intersect. The first time this happens is in K5.

image-108.svg

If you try to redraw this without edges crossing, you quickly get into trouble. There seems to be one edge too many. In fact, we can prove that no matter how you draw it, K5 will always have edges crossing.

The other simplest graph which is not planar is K3,3

image-109.svg

Proving that K3,3 is not planar answers the houses and utilities puzzle: it is not possible to connect each of three houses to each of three utilities without the lines crossing.

Note the similarities and differences in these proofs. Both are proofs by contradiction, and both start with using Euler's formula to derive the (supposed) number of faces in the graph. Then we find a relationship between the number of faces and the number of edges based on how many edges surround each face. This is the only difference. In the proof for K5, we got 3f2e and for K3,3 we go 4f2e. The coefficient of f is the key. It is the smallest number of edges which could surround any face. If some number of edges surround a face, then these edges form a cycle. So that number is the size of the smallest cycle in the graph.

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 gf2e. When this disagrees with Euler's formula, we know for sure that the graph cannot be planar.

Polyhedra

Investigate!

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 where you might have heard 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. 2 

An alternative definition for convex is that the internal angle formed by any two faces must be less than 180o.

Notice that since 812+6=2, 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:

image-110.svg

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.

Example 4.2.3

Is there a convex polyhedron consisting of three triangles and six pentagons? What about three triangles, six pentagons and five heptagons (7-sided polygons)?

Solution

How 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 v37+14=2 or equivalently v=25. 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), 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.

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.


This page titled 4.2: Planar Graphs is shared under a CC BY-SA license and was authored, remixed, and/or curated by Oscar Levin.

  • Was this article helpful?

Support Center

How can we help?