Smallest graph that is vertex-transitive but neither edge-transitive nor edge-flip-invariant?

Question

Take any undirected graph $G$. We say that $G$ is vertex-transitive iff for every vertices $v,w$ there is an automorphism on $G$ that maps $v$ to $w$. We say that $G$ is edge-transitive iff for every edge $e,f$ there is an automorphism on $G$ that maps $e$ to $f$. We say that $G$ is edge-flip-invariant iff for every edge with endpoints $v,w$ there is an automorphism on $G$ that maps $v$ to $w$ and maps $w$ to $v$.

Upon seeing these three kinds of symmetry, I had a curious question:

Question: What is the smallest $n$ such that there is a graph with $n$ vertices that is vertex-transitive but neither edge-transitive nor edge-flip-invariant?

The best I could think of was the snub cube (image from here):

It is clearly vertex-transitive, since every vertex is a vertex of a square. It is also not edge-transitive, since an edge between two triangles cannot be mapped by an automorphism to an edge next to a square. And it is not edge-flip-invariant, since no automorphism can flip an edge that is next to a triangle that is surrounded by triangles.

But is there a smaller graph with this property? I had found the snub cube by looking through 'nice' polyhedra (so that it is easy to verify vertex-transitivity), and I am unsure whether there is a better way of finding such graphs.

Answer 1

I think the following graph with $12$ vertices does the job, but I don't know if it is minimal.

It is basically a hexagonal (anti)prism with extra diagonals. Label the vertices $A_1$, $A_2$, $A_3$, $A_4$, $A_5$, $A_6$ and $B_1$, $B_2$, $B_3$, $B_4$, $B_5$, $B_6$. The edges are $\{A_i, A_{i+1}\}$, $\{B_i, B_{i+1}\}$, $\{A_i, B_i\}$, $\{A_i, B_{i+1}\}$, $\{A_i, B_{i+3}\}$, where the indices are modulo $6$.

Here is a picture to be wrapped around a cylinder, connecting the left and right sides together.

I don't think this kind of construction can work using a prism with fewer sides without introducing a mirror symmetry which would make it edge-flip-invariant.

Answer 2

My original answer below was incorrect, that graph is edge-flip invariant. It is in fact a $3\times3$ torus, from which it is not hard to see that it has all the necessary automorphisms to be edge-flip invariant. I'm now quite convinced there is no such graph on fewer than $10$ vertices.

Old, incorrect answer:

I believe this graph on $9$ vertices is the smallest example:

Answer 3

This is a negative answer: I wanted to try the idea by Jaap on how to maybe get other 12-vertex examples. The idea was to add diagonals to the truncated tetrahedron or cuboctahedron. At least those instances that I tried failed, because both gave the edge-graph of the icoshedron.

truncated tetrahedron:

cuboctahedron:

Maybe we have to add body diagonals instead.

Answer 4

To flesh out the possible combinations of these three kinds of symmetry:

Note that edge-flip-invariance implies vertex transitivity for all connected graphs, because given any two vertices $U,V$ connected by a path, we can concatenate the automorphisms taking each vertex on this path to the next one and produce an automorphism sending $U$ to $V$.

All other 6 combinations are possible, however. Denoting vertex transitivity by $V$, edge-transitivity by $E$, and flip-transitivity by $F$:

• $V, E, F$: Triangle

• $V, E, \neg F$: Holt graph

• $V, \neg E, F$: Truncated tetrahedron

• $V, \neg E, \neg F$: Snub cube, and the other answers to this question

• $\neg V, E, \neg F$: Star graphs

• $\neg V, \neg E, \neg F$: Any asymmetric graph

(Note that a symmetric graph is just a graph satisfying all of $V, E,$ and $F$, because to send one arc to another, we send the associated edge to its target and flip if necessary.)