MathWorld defines complete regularity only for polyhedral graphs, so the Platonic graphs are the only completely regular graphs. But, given a suitable definition of duality that extends that notion to (some) nonplanar graphs, we should be able to say that, for example, K₅ is also completely regular. What I’m wondering is this: Is a graph’s being completely regular in this extended sense equivalent to its being distance-transitive?

Appendix on why I’m asking: I’m nothing like a mathematician, and I don’t have a good understanding of graph theory, but I find it fascinating and want to understand more. This particular question came up as I was thinking about ways to remove the edges and corners from Go (Baduk/Weiqi). At first I thought all 4-regular graphs would do the trick, but some such graphs still have something like corners. An example is playing on the squares of a Rubik’s cube, where some squares are easier to surround with a chain of connected stones. I learned that this feeling that «not all vertices are equal» was due to the fact that the Rubik’s cube graph (not the «skeleton», but the result of making adjacent squares into adjacent vertices) is not vertex-transitive. Looking into graphs that are vertex-transitive I realized that there is a sort of hierarchy of uniformness. Some graphs are also edge-transitive. But some graphs are intuitively even more uniform than the ones that are both vertex- and edge-transitive. 4-regular examples are the octahedral graph, K₅ and the torus grid graph. My informal understanding of the property I’m looking for is that all the faces of the graph has the same number of sides. This can be made precise in the case of the octahedral graph: its dual is also regular. It seemed to be the right property, but I thought only planar graphs had duals, so I looked further, and it seemed that all distance-transitive graphs looked like the ones I intuitively understood as the «most» uniform. So when I learned that one could give a sense to the notion of the dual (not sure about the «the») of a non-planar graph, I had to wonder: what is the relation between these two properties? The one (complete regularity) seems to fit my intuition, but no one uses the term in this extended sense, and the other (distance-transitivity) is quite opaque to me. I don’t know if it is an accident that the graphs that have «faces with the same number of sides» are distance-transitive. When I'm talking about "faces" I'm imagining the graph on a surface on which its crossing number is 0.

It was this forum post that first lit my curiosity.

  • $\begingroup$ Your right that we can generalize the definition of complete regularity to non-planar graphs. It doesn't require a notion of "duality" however. Essentially complete regularity means a (graph) automorphism is available that swaps any two specified vertices. $\endgroup$
    – hardmath
    Aug 20, 2017 at 13:46
  • $\begingroup$ I must admit, I find it hard to understand these kinds of definitions. What you said sounds like the definition of a vertex-transitive graph. Here is MathWorld: every pair of vertices is equivalent under some element of its automorphism group. $\endgroup$ Aug 20, 2017 at 13:56
  • $\begingroup$ Yes, that is so. To say a graph is regular says only that all vertices have equal degrees, and since graph automorphisms preserve adjacency, vertex transitivity implies regularity but is not equivalent to that (vertex transitivity is a stronger condition). The Wikipedia article on regular graphs points out some additional properties, like strongly regular, which is a condition of intermediate "strength". $\endgroup$
    – hardmath
    Aug 20, 2017 at 14:10
  • 1
    $\begingroup$ omeyer.gmxhome.de/On_Completely_Regular.pdf has some interesting ideas. In particular I think the complete graph $K_5$ is being identified as completely regular through embedding on a torus, rather than in the plane. $\endgroup$
    – user399601
    Aug 20, 2017 at 14:11
  • $\begingroup$ Thank you, @user399601! I'll look into this. @hardmath: Are you saying that complete regularity is the same as vertex-transitivity? In that case, you are giving the words a different sense than me. There are many vertex-transitive graphs that are not completely regular (that is, that does not have regular duals). $\endgroup$ Aug 20, 2017 at 14:24

1 Answer 1


First, I do not think that "completely regular", as defined by Mathworld, is a standard term in Graph Theory. (It is used in connection with distance-regular graphs, but with a completely different meaning.)

Second, their definition has nothing to do with automorphisms. They state that a graph is regular if all vertices have the same degree, and that a polyhedral graoh is "completely regular" if the graph is regular and its dual is regular.

Third, since there are (many) diatance-regular graphs with no non-identity automorphisms, it is going to be very difficult to come up with a set of useful regularity conditions that imply a graph is distance-transitive. (I am excluding statements such as "cubic girth five diameter two on 10 vertices".)

Finally the polyhedral case (planar, 3-connected) is a poor guide to what goes on in general. It might be worth noting that there are "regular" polytopes (120-cell, 600-cell) in $\mathbb{R}^4$ that are very symmetric but not distance-transitive. Note also that here "regular" means transitive on flags, and is a very strong condition.

  • $\begingroup$ Thanks a lot for this! I’m having trouble understanding you third point. Let me restate my question in two parts: 1: If a graph is distance-transitive and is embedded in a surface in which its crossing number is 0, will all its faces be bounded by the same number of edges? 2: If a graph is regular and all its faces are bounded by the same number of edges when it is embedded in a surface in which its crossing number is 0, will it be distance-transitive? Are you saying that it is very hard to answer these questions because the two properties are defined in very different terms? $\endgroup$ Aug 20, 2017 at 18:49
  • $\begingroup$ I am not claiming that these questions are hard to answer, I am claiming that the answer to both questions is no. There are embeddings of the 3-cube in surfaces with two faces of different sizes (e.g. digitalcommons.library.umaine.edu/cgi/…). The Cartesian product of two cycles of length least five has an embedding on on the torus with all faces of degree four, but this product is not distance-transitive - not even distance regular. $\endgroup$ Aug 20, 2017 at 19:42
  • $\begingroup$ That's crystal clear. Thanks! Also: Wikipedia tells me the Biggs-Smith graph is the largest 3-regular distance-transitive graph. If there is such a thing as the largest 3-regular distance-transitive graph, then the graph you get from tiling the torus with hexagons cannot be distance-transitive, for it can be arbitrarily large. Still, all its faces are obviously the same. I have obviously not understood the concept of distance-transitivity. $\endgroup$ Aug 20, 2017 at 20:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .