From Nonplanarity to an Exact Crossing Number
A planar graph has a drawing in the plane with no crossings. A graph that is not planar needs at least one crossing in every drawing, but that fact alone does not determine its crossing number: a drawing might require several crossings. For \(K_5\) and \(K_{3,3}\), the exact answer follows by combining a lower bound from planar edge counts with a drawing that has just one crossing.
All graphs considered here are finite and simple. A drawing places distinct vertices at distinct points and represents each edge by a curve joining its endpoints. A drawing is in general position if no edge passes through a vertex other than its endpoints, no three edge interiors meet at one point, and intersections between edge interiors are proper crossings. The crossing number \(\operatorname{cr}(G)\) is the minimum number of such crossing points over all general-position drawings of \(G\). Edges that meet at a common endpoint do not make a crossing.
The argument uses Euler’s formula for a connected plane graph, a graph drawn without crossings: if it has \(n\) vertices, \(m\) edges and \(f\) faces, then \(n-m+f=2\). We use this standard result from planar graph theory. The length of a face boundary walk counts edge-sides, so an edge contributes two boundary-sides in total, even when both sides belong to the same face.
Planar Edge Bounds Needed Here
Proof. First consider a hypothetical plane drawing of \(K_5\). It is connected and has no bridges: deleting any one edge leaves the graph connected, since its endpoints are still joined by a two-edge path through a third vertex. In a connected plane graph, a face boundary walk of length two would either use parallel edges or traverse a bridge twice. Neither is possible here, because the graph is simple and has no bridges. A length-one boundary walk would require a loop, also impossible. Thus every face has boundary length at least three. The sum of the face-boundary lengths is \(2m\), so \(3f\leq 2m\). Euler’s formula gives \(f=2-n+m\). Substitution yields \(3(2-n+m)\leq 2m\), hence \(m\leq 3n-6\).
Now consider a hypothetical plane drawing of \(K_{3,3}\). It is connected and has no bridges: after deleting any edge \(a_i b_j\), choose \(a_k\neq a_i\) and \(b_\ell\neq b_j\); the remaining edges give the alternate path \(a_i-b_\ell-a_k-b_j\). The graph is simple, so no face boundary walk has length one. A length-two boundary walk would require parallel edges or a bridge traversed twice, neither of which occurs. A length-three closed walk in a simple bipartite graph would be a triangle, which is impossible because each step alternates between the two parts. Therefore every face boundary walk has length at least four, and \(4f\leq 2m\). Euler’s formula gives \(f=2-n+m\), so \(4(2-n+m)\leq 2m\), which rearranges to \(m\leq 2n-4\). \(\square\)
The two bounds have different strengths because the second proof uses the absence of odd cycles in a bipartite graph: its face boundaries cannot have length three. We now apply each bound to its corresponding graph.
Worked Example: The Edge Count Rules Out a Planar \(K_5\)
Let \(V(K_5)=\{1,2,3,4,5\}\), with \(E(K_5)\) consisting of all ten pairs of distinct vertices. Every vertex has degree \(4\). Summing degrees counts each edge twice, so \(2m=4+4+4+4+4=20\), and \(m=20/2=10\). Independently, count edges once by their first vertex in the ordering \(1,2,3,4,5\): the counts are \(4,3,2,1,0\), giving \(m=4+3+2+1+0=10\).
If \(K_5\) were planar, the first bound would require \(m\leq 3n-6=3(5)-6=15-6=9\). But its edge count is \(10\), and \(10>9\). Thus it has no crossing-free drawing, so \(\operatorname{cr}(K_5)\geq 1\).
Check: both counts give \(10\) edges, and the planar bound gives \(9\); the contradiction is exactly \(10>9\).
Worked Example: The Bipartite Bound Rules Out a Planar \(K_{3,3}\)
Let the parts be \(A=\{a_1,a_2,a_3\}\) and \(B=\{b_1,b_2,b_3\}\), with \(E(K_{3,3})=\{a_i b_j:1\leq i\leq 3,\ 1\leq j\leq 3\}\). There are \(n=6\) vertices. Each has degree \(3\), so \(2m=3+3+3+3+3+3=18\), giving \(m=18/2=9\). Counting by endpoint in \(A\) independently gives \(3+3+3=9\) edges.
If this graph were planar, the bipartite bound would require \(m\leq 2n-4=2(6)-4=12-4=8\). Since \(9>8\), it is not planar and \(\operatorname{cr}(K_{3,3})\geq 1\).
Check: the part sizes give \(3\cdot3=9\) edges, while the applicable planar bound is \(8\), not the general bound \(3n-6=12\).
Drawings with One Crossing
To turn the lower bounds into exact values, we need drawings with at most one crossing. The following constructions specify every edge and describe where the single crossing occurs. They can be drawn with curves chosen so that the crossing is proper and no other edges intersect improperly.
Worked Example: A One-Crossing Drawing of \(K_5\)
Take \(V=\{a,b,c,d,e\}\) and \(E=\{ab,ac,bc,ad,bd,cd,ae,be,ce,de\}\). Begin with \(a,b,c\) on the boundary of a triangle. Place \(d\) inside the triangle and draw \(ad,bd,cd\) inside it without crossings. Place \(e\) outside the triangle and draw \(ae,be,ce\) outside it without crossings. At this stage every edge of \(K_5\) except \(de\) has been drawn.
Route \(de\) from \(d\) through the region bounded by \(d,a,b\), cross the interior of edge \(ab\) once, and continue through the region bounded by \(a,b,e\) to \(e\). The curve can be chosen to avoid the other edges: on each side of \(ab\), its segment lies in the indicated face. It crosses \(ab\) at an interior point, not at a vertex. Thus the resulting drawing has exactly one crossing.
Check: the listed edge set has \(3+3+3+1=10\) edges: three in triangle \(abc\), three from \(d\), three from \(e\), and \(de\). These are all the pairs of five vertices. The only crossing is between \(de\) and \(ab\), so \(\operatorname{cr}(K_5)\leq 1\).
Worked Example: A One-Crossing Drawing of \(K_{3,3}\)
Use \(A=\{a_1,a_2,a_3\}\) and \(B=\{b_1,b_2,b_3\}\), and draw the six edges of the cycle \(a_1b_3a_2b_1a_3b_2a_1\) as a simple closed hexagon. Draw the additional edge \(a_1b_1\) on one side of the hexagon, and draw the additional edge \(a_2b_2\) on the other side. Each side contains just one added chord, so these eight edges form a crossing-free drawing.
The only missing edge of \(K_{3,3}\) is \(a_3b_3\). On the side containing \(a_1b_1\), the chord separates the regions incident with \(a_3\) and \(b_3\). Route \(a_3b_3\) from \(a_3\) to that chord, cross it once, and continue to \(b_3\). This adds exactly one crossing, with \(a_1b_1\), and no others.
Check: the hexagon contributes six edges, and \(a_1b_1\) and \(a_2b_2\) contribute two more, for \(6+2=8\). Adding \(a_3b_3\) gives \(8+1=9\), which agrees with the independent count \(3\cdot3=9\) for \(K_{3,3}\). The drawing has one crossing, so \(\operatorname{cr}(K_{3,3})\leq 1\).
Exact Values and the Main Argument
Proof. The planar edge-count arguments show that neither graph has a crossing-free drawing. Therefore every general-position drawing of either graph has at least one crossing, giving \(\operatorname{cr}(K_5)\geq 1\) and \(\operatorname{cr}(K_{3,3})\geq 1\). The two explicit constructions give drawings with one crossing, so \(\operatorname{cr}(K_5)\leq 1\) and \(\operatorname{cr}(K_{3,3})\leq 1\). Combining the lower and upper bounds gives \(\operatorname{cr}(K_5)=1\) and \(\operatorname{cr}(K_{3,3})=1\). \(\square\)
The logic is worth keeping explicit: nonplanarity proves only that the crossing number is positive. The constructions are essential to prove that it is no greater than one. A lower bound without a matching upper bound would not establish an exact crossing number.
Common Pitfall: Miscounting the Edges of \(K_5\)
A tempting but incorrect calculation is to write \(5+4+3+2+1=15\) and treat that as the number of edges of \(K_5\). Those terms are not the degrees of its vertices, and this sum does not correctly count its edges. The degrees are all \(4\), so the degree sum is \(4+4+4+4+4=20\); dividing by \(2\), because each edge has two endpoints, gives \(m=10\). Alternatively, count each edge once by its first endpoint: \(4+3+2+1+0=10\). The correct comparison is therefore \(10>3(5)-6=9\).
A second common error is to use the bound \(m\leq 3n-6\) to rule out a planar \(K_{3,3}\). With \(n=6\), that bound gives \(m\leq 12\), which does not contradict its nine edges. The bipartite bound \(m\leq 2n-4=8\) is the one that supplies the required contradiction.
Check Your Understanding
In each question, distinguish what the edge-count lower bound proves from what an explicit drawing proves.
- For \(K_5\), show that summing degrees and counting edges by their first endpoint both give \(10\).
- Why does the general planar bound \(m\leq 3n-6\) not rule out a planar \(K_{3,3}\)?
- In the described \(K_5\) construction, which two edges cross, and why do the other edges remain uncrossed?
- List the six cycle edges and the two additional edges in the crossing-free part of the \(K_{3,3}\) construction. Which edge is added last?
- Explain why proving that a graph is nonplanar gives a positive lower bound on its crossing number but does not, by itself, prove that the crossing number is one.