Proving K3,3 Is Nonplanar

The Count That Rules Out a Plane Embedding

The graph \(K_{3,3}\) is a basic example of a nonplanar graph. Its nonplanarity can be proved without a picture: if it had a plane embedding, its edges and faces would have to satisfy a numerical constraint that it violates. The key is to use the sharper edge bound for bipartite planar graphs, rather than the bound for all simple planar graphs.

A graph is planar if it can be drawn in the plane with edges meeting only at shared endpoints. A particular such drawing is a plane embedding; its regions are called faces. The graph \(K_{3,3}\) has two parts of three vertices each, with every vertex in one part adjacent to every vertex in the other part, and no edges within either part. Thus it is simple and bipartite.

For a simple bipartite planar graph with \(n\ge3\) vertices, the bipartite planar edge bound is \(m\le 2n-4\). This bound was established in the earlier material on planar edge bounds. We will apply it with \(n=6\). To make the contradiction transparent, we will also trace how face lengths and Euler’s formula give this inequality in the specific hypothetical embedding of \(K_{3,3}\).

Checking the Graph Data

The explicit count matters. The bound concerns the number of edges in the graph, not a number inferred from a drawing. No drawing is needed to establish that \(K_{3,3}\) has six vertices, nine edges, and a bipartition of the stated form.

Faces in a Hypothetical Embedding

Suppose, for contradiction, that \(K_{3,3}\) has a plane embedding. It is connected: vertices in opposite parts are adjacent, and any two vertices in the same part have a common neighbor. Euler’s formula for a connected plane graph therefore applies. The face-boundary facts established earlier also apply: each edge has two face-sides, counted with multiplicity, and an edge is a bridge exactly when both its sides belong to the same face.

Proof. Take any edge \(xy\), where \(x\in X\) and \(y\in Y\). Choose \(x'\in X\) with \(x'\ne x\) and \(y'\in Y\) with \(y'\ne y\); both choices exist because each part has three vertices. By the definition of \(K_{3,3}\), all four edges \(xy\), \(x'y\), \(x'y'\), and \(xy'\) are present. The vertices \(x,y,x',y'\) are distinct, so \(x,y,x',y',x\) is a cycle of length \(4\) containing \(xy\). Deleting \(xy\) leaves the other three edges of this cycle as a path between its endpoints. Hence deleting \(xy\) does not disconnect the graph, so \(xy\) is not a bridge. \(\square\)

In the hypothetical embedding, every face boundary has length at least \(4\). A boundary of length \(1\) would require a loop, which this simple graph does not have. A boundary of length \(2\) would use the same edge in both directions, since the graph has no parallel edges; that edge would have both sides incident with the same face and hence would be a bridge. The lemma rules this out. Finally, a boundary of length \(3\) would be a closed walk of odd length. In a bipartite graph, each step switches parts, so a walk can return to its starting part only after an even number of steps. Thus length \(3\) is impossible.

Let \(f\) be the number of faces in the hypothetical embedding. Adding all face-boundary lengths counts each edge-side once, for a total of \(2m\). Since each face has boundary length at least \(4\),

Euler’s formula for a connected plane graph is \(n-m+f=2\), so \(f=2-n+m\). Substitute this expression into the face-length inequality:

Subtract \(2m\) from both sides and rearrange: \(8-4n+2m\le0\), so \(2m\le4n-8\), and therefore \(m\le2n-4\). This recovers the bipartite planar edge bound in the setting needed here. The use of the face-boundary facts is legitimate because the assumed embedding is connected, simple, bipartite, and has no bridges.

The Nonplanarity Proof

Proof. Assume for contradiction that \(K_{3,3}\) is planar, so it has a plane embedding. It is simple and bipartite, and its order is \(n=6\), so the bipartite planar edge bound gives

But the explicit edge set of \(K_{3,3}\) has \(m=9\) edges. This would require \(9\le8\), which is false. The assumed plane embedding cannot exist, so \(K_{3,3}\) is nonplanar. \(\square\)

This proof uses the bound’s hypotheses directly: \(K_{3,3}\) is simple, bipartite, and has at least three vertices. The contradiction is strict by exactly one edge: the graph has nine edges, while a bipartite planar graph on six vertices can have at most eight.

What the Bound Does—and Does Not—Show

The edge bound is a necessary condition for planarity in this setting: if a simple bipartite graph with at least three vertices is planar, it must satisfy \(m\le2n-4\). Consequently, violating the bound proves nonplanarity. Passing the bound does not, by itself, prove that a graph is planar; it only means this particular obstruction has not ruled planarity out.

Common Mistakes

Using the general simple planar bound instead. The general bound \(m\le3n-6\) would give \(m\le3\cdot6-6=12\). Since \(9\le12\), it produces no contradiction. Concluding from this that \(K_{3,3}\) is planar would be incorrect: satisfying a necessary inequality is not proof of planarity. Use the stronger bound \(m\le2n-4\) because \(K_{3,3}\) is bipartite.

Forgetting the face-length condition. The inequality \(4f\le2m\) requires every face boundary to have length at least \(4\). It is not a general rule for every plane graph: triangles can occur in non-bipartite graphs, and bridges can cause repeated appearances on a face boundary. Here the graph is bipartite and simple, and the lemma shows that it has no bridges, which rules out the shorter boundaries.

Reversing the inequality. If every face has length at least \(4\), summing the face-boundary lengths gives \(4f\le2m\), not \(4f\ge2m\). In the proposed embedding, five faces would require at least \(20\) boundary incidences, but nine edges provide only \(18\). This mismatch is the contradiction.