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

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.

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.

• Thanks! I verified that your solution works! I tried antiprisms but didn't try crossing edges, so I missed such a graph. Sep 29, 2020 at 8:46
• @user21820 I think you can also use a truncated tetrahedron or cuboctahedron with some added diagonals to break the edge-flip-invariance (and edge transitivity in the latter case), but those are still 12 vertices. I think 11 vertices is impossible because it is prime and results in an 11-fold rotational symmetry which always leads to 11 mirror symmetries. I thought for a moment that a 10 vertex graph might be possible, but the only vaguely promising candidate is the Petersen graph, and that is edge-flip-invariant. Sep 29, 2020 at 9:33
• @user21820 I think 9 is possible. Stack three triangular prisms together, and then identify the top face with the bottom face but with a twist, like a Moebius band. I might update my answer when I have more time to check it is correct. Sep 29, 2020 at 9:40
• My idea for 9 vertices does not work, as it is edge-flip invariant. It contains a 9-cycle, and if you draw that as a regular nonagon, it has diagonals forming three regular triangles. This graph obviously has 9 mirror symmetries so you can flip every edge. Sep 29, 2020 at 11:18
• @JaapScherphuis Can you see deleted posts? If so, I posted an idea to insert face diagonals into a truncated tatrahedron, but it turned out to be the icosahedron. Maybe other diagonals work better. Sep 30, 2020 at 13:37

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.)

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.

I believe this graph on $$9$$ vertices is the smallest example: • I think this is the same as what I mentioned in a comment to my answer - stack three triangular prisms together, and then identify the top face with the bottom face but with a twist, like a Moebius band. Sep 29, 2020 at 10:12
• It might very well be, I've been staring at graphs for so long my brain is completely fried; I must admit that I am not entirely sure it isn't edge-flip invariant. Sep 29, 2020 at 10:17
• Actually, it is not the same. Yours has three twists, which is equivalent to no twists at all, so it is essentially just the 3x3 torus graph, and this is edge-flip invariant. Unfortunately my graph also does not work, as it too is edge-flip invariant. Sep 29, 2020 at 11:15
• @JaapScherphuis I'll need some time to verify your statements. Anyway, this graph was the only graph on at most $9$ vertices that I could not exclude. So assuming I made no errors in my (long, manual) check, any such graph must have at least $10$ vertices. Sep 29, 2020 at 11:22
• I used graphaffinity to draw it, and then moved around the vertices to simplify it. You could also use geogebra. Sep 29, 2020 at 11:26

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: 