3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

enter image description here

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.

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

The smallest example surely has $\leq \color{red}{8}$ vertices.

enter image description here

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:

enter image description here

Some vertices belong to triangular faces, some don't.

$\endgroup$
  • 1
    $\begingroup$ 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/…) $\endgroup$ – Samuel Coskey Feb 3 '17 at 4:21
  • 1
    $\begingroup$ @SamuelCoskey: exactly, it should not be difficult to check that the minimal counter-examples have $8$ vertices. $\endgroup$ – Jack D'Aurizio Feb 3 '17 at 8:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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