Can we reduce the crossing number of a graph by two by just removing only one edge? I only know that if it is true, then there must be two edges crossing the same edge. Can you give me some hints or examples?
 A: On the crossing number of planar graphs by Petr Hlinený and Gelasio Salazar has a construction for any crossing number.
Basically, take the polyhedron formed by sticking two $2n$-sided pyramids together base to base. Their edges form a planar graph, like any convex 3d polyhedron. If you add an edge between opposite vertices of the base, it becomes a graph with crossing number $n-1$. This is proved by induction in the paper (Proposition 3.1).
A: Here is a very non-constructive argument for the existence of $n$-vertex graphs where the deletion of one edge can reduce the crossing number by not just one or two, but $\Omega(n^2)$ crossings.
By the crossing number inequality, the complete graph $K_n$ has a crossing number of $\Omega(e^3/n^2) = \Omega(n^4)$. On the other hand, if you remove all $\binom n2$ edges, you get the empty graph, which has a crossing number of $0$.
As a result, if we remove the edges of $K_n$ one at a time, in arbitrary order, there must be at least one step at which the crossing number goes down by $\Omega(n^4)/\binom n2 = \Omega(n^2)$.
