# What is the smallest example of a connected regular graph which is not vertex-transitive?

Without the word "connected" the answer is the disjoint union of a triangle and a square, per Smallest Graph that is Regular but not Vertex-Transitive?

I also know per wikipedia that the Frucht graph is a connected example with twelve vertices. This is a 4-regular connected graph on 7 vertices which is not vertex-transitive. (Reason: the vertex labelled 1 is contained in 3 triangles, whereas the vertex labelled 2 is contained in 2 triangles)

Note that all regular graphs (connected or disconnected) on $$\leq 6$$ vertices are vertex-transitive.

• Thank you! This is the graph complement of the disjoint union of a square and a triangle. So sorry for bothering you, internet! – Samuel Coskey Aug 1 '19 at 20:16

The smallest example surely has $\leq \color{red}{8}$ vertices. The depicted graph is a planar cubic graph, but is not vertex-transitive: there are three pentagonal faces meeting at the central point, and the central point is the only vertex with such a property. By a similar principle, here it is an example with $8$ vertices: Some vertices belong to triangular faces, some don't.

• Thanks! It remains to check 7 vertices, but this seems to be done in other postings - there is no 3-regular graph and there ar only very simple 2 and 4-regular graphs (math.stackexchange.com/questions/90492/…) – Samuel Coskey Feb 3 '17 at 4:21
• @SamuelCoskey: exactly, it should not be difficult to check that the minimal counter-examples have $8$ vertices. – Jack D'Aurizio Feb 3 '17 at 8:31