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.
Draw, if possible, two different planar graphs with the same number of vertices, edges, and faces.
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:
That is because we can redraw it like this:
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:
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.
Is there a connection between the number of vertices (\(v\)), the number of edges (\(e\)) and the number of faces (\(f\)) in any connected planar graph? Let's investigate this. For each planar graph, we can associate a triple \((v,e,f)\) containing the number of vertices, edges and faces. For example, the triple for \(K_4\) drawn above is \((4,6,4)\text{.}\)
Draw a lot of planar graphs and for each record the triple \((v,e,f)\text{.}\) What triples are possible? Is there a graph with the triple \((5, 9, 6)\text{?}\) What about \((5,7,5)\text{?}\)
If we want to understand the relationship between the number of vertices, edges and faces of a planar graph, we could first try to decide which triples can be realized by a graph and which cannot. At first this might seem like a daunting task. The key is to think of it recursively. Perhaps start with simple graphs and build up to more complicated ones.
What happens to the triple \((v,e,f)\) when you add an edge to a graph?
Start with a single pair of adjacent vertices (that is, the graph \(P_1\)). What is \((v,e,f)\text{?}\) What happens to the triple if you extend the path to \(P_2\text{?}\) How do \(v\text{,}\) \(e\text{,}\) and \(f\) change?
You could add another vertex and edge to \(P_2\) (which would either give \(P_3\) or a star graph), or you could add an edge connecting two vertices not already adjacent. What would these two operations do to \((v,e,f)\text{?}\)
Generalize. Say you know a specific triple \((a,b,c)\) describes a graph \(G\text{.}\) Give two new triples that also describe some graphs, each with one more edge than \(G\text{.}\)
Conjecture a relationship between \(v\text{,}\) \(e\text{,}\) and \(f\) that should hold for any connected planar graph.
It appears that whenever \((v,e,f)\) describes some graph, then there is a graph with triple \((v+1, e+1, f)\) and a graph with triple \((v,e+1, f+1)\text{.}\) Perhaps there are other ways we could add an edge we haven't thought of yet, but so far it seems like this completely describes how any triple must be created.
If this is the case, what could we conclude? Every time we add an edge, either the number of vertices or the number of faces increases by 1. Perhaps then \(e = v + f\text{?}\) But this is not true, since for \(P_1\) we would have \(1 = 2 + 1\text{,}\) clearly false. Okay, at least we might guess \(v + f - e\) is constant. And from \(P_1\text{,}\) we see that constant would need to be \(2 + 1 - 1 = 2\text{.}\) This leads us to conjecture the following theorem.
For any planar graph with \(v\) vertices, \(e\) edges, and \(f\) faces, we have
We will soon see that this really is a theorem. The equation \(v-e+f = 2\) is called Euler's formula for planar graphs. To prove this, we will want to somehow capture the idea of building up more complicated graphs from simpler ones. That is a job for mathematical induction!
The proof technique we will use to establish Euler's formula for planar graphs is called mathematical induction. This is a technique we will return to many times throughout our studies, so let's take a few moments to understand the logical structure for this style of proof and why it is a valid proof technique. Additional general practice on induction can be found in Section B.6.
What is the units digit of \(6^n\text{?}\) How do you know?
Suppose you knew that the units digit of \(6^{217}\) was a 2. Without calculating \(6^{218}\) directly, can you say what its units digit would be?
Is the units digit of \(6^{217}\) a 2? How do you know?
We often wish to prove a statement is true for all natural numbers \(n\) (or all integers larger than some smallest example). Mathematical induction uses the fact that the (infinitely many) cases we wish to prove are in a nice order with a least element. To show that \(6^n\) has units digit 6 for all \(n \ge 1\text{,}\) we notice that \(6^n = 6^{n-1}\cdot 6\text{.}\) Assuming that we have already shown that \(6^{n-1}\) has units digit 6, we can multiply this number by 6, and note that the units digit will still be a 6, since the units digit of \(x \cdot 6\) is just 6 times the units digit of \(x\text{,}\) and \(6\cdot 6\) has units digit 6.
But this seems sneaky. Is it valid to assume that we already know the units digit of \(6^{n-1}\text{?}\) That is the power of induction.
Suppose we hope to prove that \(P(n)\) is true for all \(n \ge 0\text{.}\) What we will really prove is that \(P(0)\) is true, and that for all \(k\text{,}\) if \(P(k-1)\) is true, then \(P(k)\) is true. In other words, we are proving the implication
This implication being true for all \(k \ge 1\) really means we have proved infinitely many implications
Can we conclude \(P(n)\) is true for all \(n\text{?}\) Well take any \(n\text{.}\) For example, \(n = 3\text{.}\) We know \(P(0)\) is true, and the implication \(P(0) \imp P(1)\) is true, so we can conclude \(P(1)\text{.}\) From \(P(1)\) and \(P(1) \imp P(2)\text{,}\) we can conclude \(P(2)\text{.}\) From \(P(2)\) and \(P(2) \imp P(3)\text{,}\) we can conclude \(P(3)\text{.}\) If we wanted a different value of \(n\text{,}\) we would just need to keep going until we got up to it. Since every value of \(n\) can be reached by some finite number of steps starting at 0, we will know, for each \(n\) that \(P(n)\) is true.
The above discussion is meant to explain why it is reasonable to believe that induction is a valid proof technique. 2 Technically, induction must be assumed as an axiom or deduced from the equivalent well-ordering principle which says that every subset of \(\N\) contains a least element; our justification for it is circular, since to prove the justification is valid would be done by induction itself. Once we believe induction works, we can just use it. That means just proving two things: \(P(0)\) and for all \(n \ge 0\text{,}\) \(P(n) \imp P(n+1)\text{.}\) We call \(P(0)\) the base case and the implication the inductive case. Here is an example of what a proof by induction looks like.
Prove by induction that for all \(n \ge 0\text{,}\) the number \(n^2 + n\) is even.
First note that induction is NOT necessary here. We could give a non-inductive prove as follows.
Fix \(n \ge 0\text{.}\) Now \(n^2 + n = n(n+1)\text{.}\) Either \(n\) or \((n+1)\) is even, and the product of an even number and an odd number is even, so \(n^2 + n\) is even.
To contrast, here is a proof by induction.
First note that \(0^2 + 0 = 0\) is even, so the case when \(n = 0\) is true. Now assume for an arbitrary \(n\ge 0\) that \(n^2 + n\) is even. Consider the case for \(n+1\text{:}\)
But \(n^2 + n\) is even, and \(2n + 2\) is even, and the sum of two even numbers is even, so \((n+1)^2 + n+1\) is even.
Now that we have some sense for mathematical induction in general, let's consider how induction can be applied in graph theory.
First, we need something to play the role of \(n\text{,}\) since induction is used to prove statements are true for all natural numbers \(n\text{.}\) For the most part, we cannot think of all graphs as lined up in some natural order. But we could use induction on the number of edges of a graph (or number of vertices, or any other notion of size). That is we can prove that for all \(n\ge 0\text{,}\) all graphs with \(n\) edges have ….
Notice that the thing we are proving for all \(n\) is itself a universally quantified statement. This means that our base case become, “for all graphs with 0 edges …” (which for not-necessarily connected graphs is infinitely many graphs). To prove the inductive case we get to assume that for all graphs with \(n\) edges …, but then we must prove that for all graphs with \(n+1\) edges ….
Because of this added complication, the usual way to approach the inductive case for graphs is to start with an arbitrary graph that has \(n+1\) edges. Then remove an edge to drop down to a graph with \(n\) edges, which we know something about (our inductive hypothesis). Then make sure that moving back to the original graph, we maintain our desired property.
Let's try a simple example.
Recall that a tree is a connected graph with no cycles. We wish to prove that every tree with \(v = n\) vertices has \(e = n-1\) edges. (This is actually a special case of Euler's formula for planar graphs, as a tree will always be a planar graph with 1 face).
First, prove a lemma (not using induction): every tree contains at least two vertices of degree 1.
Look at paths in the tree. Let \(v_0, v_1, \ldots, v_n\) be a path of maximal length. What can you say about \(v_0\) and \(v_n\text{?}\)
We will give a proof by induction on the number of vertices in a tree. What should the base case be? Prove it.
What is the smallest number of vertices that make sense? You will need to prove that all trees with one vertex have the correct number of edges. This should be very easy.
Now for the inductive case. Start with an arbitrary tree \(T\) with \(n\) vertices and assume that all trees with \(n-1\) vertices have \(n-2\) edges (why is the the right thing to assume)? Prove that \(T\) has \(n-1\) edges.
To get to a tree with \(n-1\) vertices, you need to trim \(T\) somehow. Which vertex should you get rid of? What will this do to the number of edges?
We will use induction for many graph theory proofs, as well as proofs outside of graph theory. As our first example, we will prove Theorem 1.3.1
The proof we will give will be by induction on the number of edges of a graph. This means we will need a way to reduce the number of edges, so we can get down to our inductive hypothesis. There are two ways to remove an edge that will be useful here and for future problems.
A deletion is the result of removing an edge from the edge set (everything else in the graph stays the same). For a specific edge \(e\) in the graph \(G\text{,}\) we write the new graph as \(G - e\text{.}\)
Slightly more complicated is a contraction. The idea is we take an edge and shrink it down to a vertex. The two endpoints of the vertex collide and all their incident edges follow along and become incident to this new vertex consisting of the edge and two vertices contracted together. The resulting graph is written \(G/e\) (read “\(G\) contract \(e\)”).
To be a little more precise, given a graph \(G\) and edge \(e = \{u,v\}\text{,}\) the graph \(G/e\) is formed by
Removing vertices \(u\) and \(v\) and all their incident vertices.
Adding a new vertex \(E\) and edges from \(E\) to each vertex that was previously adjacent to \(u\) or \(v\text{.}\)
Notice that \(G/e\) might be a multigraph (if \(u\) and \(v\) were both adjacent to a common vertex). If \(G\) was already a multigraph, and had two edges connecting \(u\) and \(v\text{,}\) then \(E\) will get a loop (since only one of the edges was contracted). We can avoid multigraphs by being careful which edge we contract along.
Let \(G\) be any planar graph with \(v\) vertices, \(e\) edges, and \(f\) faces.
Let \(e_0\) be any edge part of a cycle in \(G\text{.}\) Would it make more sense to remove \(e_0\) using a deletion or a contraction? What will happen to \(v - e + f\text{?}\)
Let \(e_0\) be an edge incident to a vertex of degree 1. Should we remove \(e_0\) by deletion or contraction? What will happen to \(v- e + f\)
Prove Euler's formula for planar graphs using induction on the number of edges in the graph.
You can take \(n = e = 1\) as your base case. For the inductive case, start with an arbitrary graph with \(n\) edges. Consider two cases: either \(G\) contains a cycle or it does not.
It is a good exercise to give proofs by induction on the number of vertices or the number of faces. You will need to think about how to remove a vertex or a face, and how doing so changes the other quantities.