Proving that crossing number for a graph is the lowest possible How would one go about proving that the crossing number for a graph is the lowest possible? 
To be more specific, given a specific representation of a particular cubic graph $G$, how do I prove that the crossing number can not be lowered any further? 
This $G$ has $|V|<20$, and $\operatorname{cr}{(G)}\geq 2$. Furthermore, various online sources say the $\operatorname{cr}{(G)}$ I have found is correct, but offer no proof of why.
Complexity for this in general is hard, supposedly NP-hard, and no general solution is known, but given that the number of vertices is small enough and graph is 3-regular, there must be a way.

If the graph is small enough and you were willing to prove it by hand, you could do a case analysis similar to how students show a graph is non-planar ($cr(G) \geq 1$) by hand.
Take a long cycle (hopefully Hamiltonian), and place it evenly spaced on a circle, then start adding in edges. You're done if you can show by case analysis that no matter how the edges are added, more than one crossing is created.
