In my graph theory class we've had several questions where we were to find the crossing number of a graph and prove our answer. In all of these questions, $Cr(G) = 1$, so we need only show a drawing of the graph with 1 crossing and that the graph is not planar either using one of the 2 common inequalities relating vertices ($q \leq 3p - 6$ for any planar graph $q \leq 2p - 4$ for a planar bipartite graph) or by edge and vertex contraction to find a resulting graph that contained either $K_{3,3}$ or $K_5$ (If either of these graphs were found, the graph is nonplanar by Kuratowski's Theorem).

I've come across a problem in my textbook where it asks the reader to prove that a graph has crossing number 5 and provides a picture (included below) that shows a drawing of the graph with exactly 5 crossings.

enter image description here

So, clearly $Cr(G) \leq 5$ given the drawing, but to complete the proof I must show that $Cr(G) \geq 5$, but I know only that I have been able to contract vertices and edges to find $K_{3,3}$ or $K_5 \implies Cr(G) \geq 1$. What should I do to show that the crossing number is $\geq 5$?

Or, more generally how to show that $Cr(G) \geq n, n \in \mathbb{N} - \{1\}$?


After further review I have found a proof as follows:

We have that $cr(G) \leq 5$ given the drawing presented. If $cr(G) < 5$ then removing 4 edges may create a planar graph, but $\forall$ planar graph we have $q \leq 3p - 6$. Given $p=10, q=29$ in the graph shown we would then have $29-4=25 \leq 3(10) - 6 = 24$, a contradiction. Thus $cr(G) \geq 5$. Then, necessarily, $cr(G) = 5$. $\square$

  • $\begingroup$ You mean $29-4$ instead of $29-5$ right? I think your proof works. $\endgroup$ – mathpadawan Nov 28 '18 at 13:47
  • $\begingroup$ Yeah dunno how that got there. Fixed $\endgroup$ – rjm27trekkie Nov 29 '18 at 15:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.