Edit: As David Eppstein points out (in his answer below) the assumption that the graph is non-planar is redundant. 


Thank you to everyone who answered/commented.




---


I have a problem about geometric embeddings of graphs for which the case I cannot prove is when the (simple, connected) graph is 4-regular, non-planar and has girth at least 5.


I would like to get some intuition for such graphs - e.g. 


\*small(est) examples, 


\*do such graphs have any interesting special properties?


\*I assume there are many when the number of vertices is large, 


\*a book or paper that might help.


Apologies if this is too easy for math overflow, I'm not a graph theorist.



Request for examples of 4-regular, non-planar, girth at least 5 graphs
A random 4-regular graph will have large girth and will, I expect, not be planar. This suggests that that there are a lot of the graphs you want, and they have no particular special properties. Markus Mehringer's program genreg will produce 4-regular graphs quickly and, as $n$ increases. Brendan McKay's geng program can also be used. My recollection is that things will start to bog down around 16. But a computer search has a good chance of producing small examples.


