Request for examples of 4-regular, non-planar, girth at least 5 graphs

Question

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.

Answer 1

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.

Answer 2

If a planar graph has girth four or more, it can have at most $2n-4$ edges, but every 4-regular graph has exactly $2n$ edges, so every 4-regular graph with girth $\ge 4$ is nonplanar. That is, your requirement that the graph be nonplanar is redundant.

The projective plane of order 3 has 13 points, 13 lines, four points per line and four lines per point. Its Levi graph (a graph with 26 vertices, one for each point and one for each line, and with an edge for each point-line incidence) is bipartite with girth six. According to the link in the comment by user35593 it is the unique smallest 4-regular graph with this girth.

You can get bigger examples like this from other configurations with four points per line and four lines per point, such as the 256 points and 256 axis-parallel lines of a $4\times 4\times 4\times 4$ hypercube.

Answer 3

The graph from the page provided by user35593 is indeed non-planar:

sage: g = Graph(':R____```aDaEaFbDbEGbFHcDLcEIJcFGhJOiKMP')
sage: g.order()
19
sage: g.is_regular(4)
True
sage: g.girth()
5
sage: g.is_planar()
False

Answer 4

One natural way of constructing such graphs is to take a group $G$, say $G=\text{SL}_2(p)$ or $G=A_n$, take $x,y\in G$ uniformly at random, and form the Cayley graph of $G$ with generators $x,y,x^{-1},y^{-1}$.

The probability that this graph has small girth, or in particular loops or double edges, is vanishingly small if $G$ is sufficiently nonabelian. For example consider the case of $G=\text{SL}_2(p)$. A small cycle in the Cayley graph corresponds to a short nontrivial word $w$ such that $w(x,y)=1$. By considering the standard generators we know that there is no $w$ of length less than $\log p$ or so such that $w(x,y)=1$ identically, and since $w(x,y)=1$ is a system of polynomials for each fixed $w$ we thus know that $\mathbf{P}(w(x,y)=1)\leq c/p$ by the Schwartz-Zippel bound. So we expect no relation between $x$ and $y$ of length less than $c\log p$.

Such graphs are extremely unlikely to be planar, though I'm not sure what the simplest argument is. I suppose one could probably find a $K_5$ minor fairly easily. In fact the graph will be an expander, and expanders cannot be planar.