The Edge-Count Obstruction
A planar graph is one that has a drawing in the plane with no edges crossing except at shared endpoints. Such a crossing-free drawing is a plane embedding. To prove that a graph is not planar, it is enough to assume a plane embedding exists and derive a contradiction from a necessary condition for planar graphs.
For simple planar graphs with at least three vertices, the simple planar edge bound gives such a condition: if a simple planar graph has \(n\) vertices and \(m\) edges, then \(m\leq 3n-6\). The hypothesis that the graph is simple matters: loops and multiple edges are excluded. The bound applies whether or not the graph is connected. We use this earlier result on planar edge bounds to examine the complete graph on five vertices.
The proof will turn on comparing that edge count with the largest number of edges permitted by the simple planar edge bound at order \(5\). We will also examine graphs whose counts reach or fall below that limit, since a necessary condition for planarity is not automatically a sufficient one.
Proving \(K_5\) Is Nonplanar
Proof. Suppose, for a contradiction, that \(K_5\) is planar. Then it has a plane embedding, and it is a simple planar graph with \(n=5\) vertices. The simple planar edge bound therefore requires \(m\leq 3n-6\). Substituting \(n=5\) gives \(m\leq 3\cdot 5-6=15-6=9\).
But every pair of distinct vertices in \(K_5\) is an edge. There are \(\binom{5}{2}=\frac{5\cdot4}{2}=10\) such pairs, so \(m=10\). The supposed embedding would therefore require \(10\leq9\), which is false. The assumption that \(K_5\) is planar leads to a contradiction, so \(K_5\) is nonplanar. \(\square\)
The argument needs only a necessary condition: any simple planar graph of this order must have at most nine edges. Since \(K_5\) has ten, there is no need to try to construct or analyze a drawing. The contradiction is numerical, but its force comes from applying the bound only after checking its hypotheses.
Worked Example: Count the Edges of \(K_5\) Two Ways
Let \(G=K_5\), with \(V(G)=\{1,2,3,4,5\}\) and \(E(G)=\{12,13,14,15,23,24,25,34,35,45\}\). Count the edges by listing pairs, then verify the result using degrees.
Each of the five vertices is adjacent to the other four. Thus each vertex has degree \(4\), and the sum of the degrees is \(5\cdot4=20\). Each edge contributes \(1\) to the degree of each of its two endpoints, so the degree sum is twice the number of edges. Hence \(m=20/2=10\).
Independently, an edge is an unordered pair of distinct vertices. There are \(5\cdot4=20\) ordered choices of two distinct vertices, and each unordered pair is counted in both orders. Therefore there are \(20/2=10\) edges. The two counts agree: \(|E(G)|=10\).
Check: the edge list contains \(12,13,14,15,23,24,25,34,35,45\), which is ten entries. The degree count also gives \(20/2=10\), confirming the list count.
Using a Nonplanar Subgraph
The same obstruction can prove a larger graph nonplanar when that graph contains \(K_5\) as a subgraph. A subgraph is obtained by retaining some of the vertices and some of the edges; here, it is enough that the retained vertices have every pair joined. We first record why planarity passes from a graph to its subgraphs.
Proof. Suppose \(G\) is planar, and let \(H\) be a subgraph of \(G\). Choose a plane embedding of \(G\). To obtain a drawing of \(H\), delete from that drawing every edge not in \(H\), and delete every vertex not in \(H\), together with its incident edges. The remaining edges are a subset of the edges in the original crossing-free drawing, so no two remaining edges cross except at shared endpoints. This is a plane embedding of \(H\), proving that \(H\) is planar. \(\square\)
Consequently, if a graph contains \(K_5\) as a subgraph, it cannot be planar: otherwise the lemma would make that copy of \(K_5\) planar, contrary to the theorem. The next example shows how to use this conclusion when the whole graph’s edge count does not violate the bound.
Worked Example: \(K_5\) with an Isolated Vertex
Let \(G\) have \(V(G)=\{1,2,3,4,5,6\}\) and \(E(G)=\{12,13,14,15,23,24,25,34,35,45\}\). Vertex \(6\) is isolated. Decide whether \(G\) is planar.
The graph has \(n=6\) vertices. Its ten listed edges are exactly the pairs among vertices \(1,2,3,4,5\), so \(m=10\). The bound for a simple planar graph of order \(6\) is \(m\leq3\cdot6-6=18-6=12\). Since \(10\leq12\), applying the bound to the whole graph does not give a contradiction.
However, the subgraph induced by \(\{1,2,3,4,5\}\) has all ten pairs as edges, so it is \(K_5\). If \(G\) were planar, the subgraph lemma would imply that this \(K_5\) is planar. The theorem rules that out, so \(G\) is nonplanar.
Check: the degree sequence is \(4,4,4,4,4,0\). Its sum is \(5\cdot4+0=20\), giving \(m=20/2=10\), as in the edge list. The whole-graph bound permits up to \(12\) edges, explaining why that count alone is inconclusive; the \(K_5\) subgraph supplies the obstruction.
When the Bound Does Not Decide
The simple planar edge bound is a necessary condition, not a test that always decides planarity. If a simple graph with \(n\geq3\) has more than \(3n-6\) edges, the bound proves it is nonplanar. If it has at most \(3n-6\) edges, the bound has not ruled out planarity; another argument may still be needed. In particular, meeting the bound exactly does not by itself prove that a graph is planar.
Worked Example: Removing One Edge from \(K_5\)
Let \(H\) have \(V(H)=\{1,2,3,4,5\}\) and \(E(H)=\{13,14,15,23,24,25,34,35,45\}\). This is \(K_5\) with the edge \(12\) removed. Determine what the simple planar edge bound says.
There are five vertices, so the bound for a simple planar graph of this order is \(m\leq3\cdot5-6=15-6=9\). The displayed edge set has nine edges, so \(m=9\), exactly the permitted maximum. The necessary inequality is satisfied, and this calculation alone does not prove that \(H\) is nonplanar.
Verify the count by degrees. Vertices \(1\) and \(2\) each have degree \(3\), because they are not adjacent to one another and each is adjacent to \(3,4,5\). Vertices \(3,4,5\) each have degree \(4\). The degree sum is \(3+3+4+4+4=18\), so the number of edges is \(18/2=9\), agreeing with the list.
Check: the nine listed pairs are all pairs from the ten edges of \(K_5\) except \(12\). The count \(10-1=9\) agrees with the independent degree calculation \(18/2=9\). Since \(9\leq9\), the simple planar edge bound gives no contradiction; it is not, on its own, a planarity proof.
A Reliable Proof Pattern
For a proof based on this obstruction, keep the assumptions and the comparison visible. First, specify the graph and confirm that it is simple. Then state its order \(n\), count its edges \(m\), and apply the bound \(m\leq3n-6\), whose hypothesis is \(n\geq3\). If \(m>3n-6\), the graph cannot be planar. If the inequality holds, stop short of claiming planarity: the count has only passed this necessary test.
The most common error is to reverse that last implication. The edge bound says that planarity implies the inequality; it does not say that the inequality implies planarity. Another mistake is to use the bound without checking the graph’s order or simplicity. In the \(K_5\) proof, the graph is simple and has order \(5\), so the bound applies; the exact comparison is \(10>3\cdot5-6=9\).
Subgraphs provide a complementary use of the result. A graph may have a total edge count below the bound for its order, yet contain a smaller nonplanar subgraph. When that happens, the subgraph lemma rules out planarity of the larger graph. This keeps the argument precise: use an edge-count contradiction when one is available, and use a nonplanar subgraph when the overall count is inconclusive.
Check Your Understanding
For each question, distinguish what the simple planar edge bound proves from what it leaves undecided.
- State the hypotheses and conclusion of the simple planar edge bound used here.
- Why does \(K_5\) violate the bound? Show the calculation of both its edge count and the bound at order \(5\).
- A simple graph has \(6\) vertices and \(13\) edges. Does the bound prove it is nonplanar? Explain by computing the limit.
- A graph contains a subgraph isomorphic to \(K_5\). Prove that the graph is nonplanar.
- A simple graph has \(5\) vertices and \(9\) edges. Does meeting the bound prove that it is planar? Explain.