# Smallest Graph that is Regular but not Vertex-Transitive?

I'm trying to find the smallest graph that is regular but not vertex-transitive, where by smallest I mean "least number of vertices", and if two graphs have the same number of vertices, then the smaller is the one with the lower number of edges.

I currently have that the smallest such graph is the disjoint union of the three-cycle and the four-cycle.

Are there any smaller graphs?

• Is that easy? There are many graphs on at most six vertices. Even to eliminate all the ones with valency $> 2$ would still leave me checking on the order of $2^{15}$ graphs. Is there a particular technique you have in mind? – Newb Apr 21 '14 at 12:00
• Okay, I sketched it out. The regular graphs on $n$ vertices with valency $2$ are all just cycles, which are vertex-transitive. Is that correct? This leads me to believe that I've found the minimal example (seeing as a regular graph on 7 vertices with fewer than 7 edges is not possible). – Newb Apr 21 '14 at 12:12
• @Newb Yes. A regular graph with valency $0$ is trivially transitive. Regular with valency $1$ is always vertex transitive (it's just a bunch of isolated edges). Regular with valency $2$ means we have disjoint cycles; as each must have length $\ge3$, to even have more than one cycle (which is always transitive) we need $n\ge 6$; with $n=6$ we could have two $3$-cycles, still transitive; with $n=7$, we have your example. – Hagen von Eitzen Apr 21 '14 at 12:27