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.

  • 2
    $\begingroup$ According to mathe2.uni-bayreuth.de/markus/reggraphs.html#GIRTH5 the smallest such graph has 19 vertices. $\endgroup$
    – user35593
    Apr 10, 2015 at 9:04
  • $\begingroup$ However I am not 100% sure it it is non-planar $\endgroup$
    – user35593
    Apr 10, 2015 at 9:35
  • $\begingroup$ It should be noted, that the girth should be at least five and need not be exactly five. $\endgroup$ Apr 10, 2015 at 15:19

4 Answers 4


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.

  • 1
    $\begingroup$ Actually for this size (19+ vertices), genreg will be much better. But as Chris says, there are zillions of these graphs, with 132 million already by 26 vertices. We'd normally expect most to be non-planar, so (again reiterating Chris) there's unlikely to be anything more special about them than what you started with (4-regular, girth 5). $\endgroup$ Apr 10, 2015 at 14:53
  • $\begingroup$ @gordonRoyle: I was thinking there might be examples on fewer than 19 vertices? $\endgroup$ Apr 10, 2015 at 15:04
  • $\begingroup$ No, the (4,5)-cage has 19 vertices so there's nothing smaller. $\endgroup$ Apr 11, 2015 at 13:14

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.

  • $\begingroup$ Thanks! I'll edit the question. I see now that it's quite easy to prove that 4-regular and planar implies there are triangles. $\endgroup$
    – user62562
    Apr 11, 2015 at 6:50

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

sage: g = Graph(':R____```aDaEaFbDbEGbFHcDLcEIJcFGhJOiKMP')
sage: g.order()
sage: g.is_regular(4)
sage: g.girth()
sage: g.is_planar()
  • 2
    $\begingroup$ This is the Robertson graph en.m.wikipedia.org/wiki/Robertson_graph $\endgroup$ Apr 10, 2015 at 10:38
  • $\begingroup$ how do you get this encoding of the graph? For me, it returns graph with loops... $\endgroup$ Apr 10, 2015 at 10:44
  • $\begingroup$ Anyway: g=Graph({1:[ 2,3,4,5 ], 2:[ 1,6,7,8 ], 3:[ 1,9,10,11 ], 4:[ 1,12,13,14 ], 5:[ 1,15,16,17 ], 6:[ 2,9,12,15 ], 7:[ 2,10,13,16 ], 8:[ 2,11,14,17 ], 9:[ 3,6,13,17 ], 10:[ 3,7,14,18 ], 11:[ 0, 3,8,16 ], 12:[ 4,6,16,18 ], 13:[ 0,4,7,9 ], 14:[ 4,8,10,15 ], 15:[ 0,5,6,14 ], 16:[ 5,7,11,12 ], 17:[ 5,8,9,18 ], 18:[ 0,10,12,17 ], 0:[ 11,13,15,18 ]}) $\endgroup$ Apr 10, 2015 at 10:45
  • $\begingroup$ sage: g.minor(graphs.CompleteBipartiteGraph(3,3)) {0: [0, 15], 1: [17], 2: [1, 4, 5], 3: [2, 6, 9], 4: [3, 8, 11, 14], 5: [7, 10, 13, 18]} $\endgroup$ Apr 10, 2015 at 10:46

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.