Lesson 4

We now know that many graphs are not planar. In particular, all planar graphs are sparse. A natural question arises: with what minimum number of pairwise edge crossings can a given graph be drawn? For a graph \(G\) denote this number by \(\operatorname{cr}(G)\). Thus, if \(G\) is planar, then \(\operatorname{cr}(G)=0\). The function \(\operatorname{cr}\) can be viewed as a measure of non-planarity of the graph.

Theorem. For a graph \(G\) with \(|V(G)| \ge 3\) the following holds: \[\begin{equation*}\operatorname{cr}(G) \ge |E(G)|-3|V(G)|+6 \ .\end{equation*}\]

Proof. Take an optimal drawing and repeat the following: while there is a crossing in the drawing, remove from the graph (and the drawing) one of the edges involved in the crossing. In the resulting graph, the number of edges will be, on the one hand, at least \(|E(G)|-\operatorname{cr}(G)\), and on the other hand, at most \(3|V(G)|-6\) (since the remaining graph will be planar).◼