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.

at leastfive and need not beexactlyfive. $\endgroup$ – Manfred Weis Apr 10 '15 at 15:19