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.
 A: Geoff Exoo has a good program that works well for small graphs.  I worked with him for identifying what we called the Crossing Number Graphs, which attain some high crossing number.
Initially, Geoff's program optimizes some random embedding.  99.9% of the time, it will find some reasonably good crossing.  We were looking for the graphs with highest crossing number, so any that had something lower, we would discard. 
For 22 vertex cubic graphs, we were left with 4 graphs that the "fast" program said had 7 crossings.  Geoff also had a "slow" program, that would study a single graph for something like 10 hours.  I also looked at each of these graphs extensively by hand, and subsequently many others have as well.
Post the graph, and I can take a look at it.  
A: 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.
