# Prove a Graph $G$ Has Crossing number $Cr(G) = 5$

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.

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\}$$?

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$$
• You mean $29-4$ instead of $29-5$ right? I think your proof works. – mathpadawan Nov 28 '18 at 13:47