What's the best (or at least, easiest-to-use) software for producing graph-theoretical diagrams in 3D space (similar to the pic below, which I found from the Wikipedia article on simple cubic graphs)? I want to use this to discuss the concept of resolving 2D nonplanarity of graphs by moving into 3D, perhaps pivoting into something about planar molecules in chemistry or other such applications.
Molecular Graphics
So if you want to show molecules in all their detail, then you will need some dedicated molecular graphics software. Thankfully, there are plenty of free options out there : Jmol, or PyMol are two, but there are many more.
Talking of these, I have a feeling that the image you show was made with Rasmol, however I can not be sure...
CaGe
What might work best for you is something like CaGe which can generate planar graphs of various types (including fullerenes) and then display them in 3D.
This would be easier than using some generic drawing package for these 'ball and stick' models as you have to get the 3D coordinates from the planar graph. Not a problem for graphs drawn in the plane, but more for those on a sphere.