Are there only seven 3-connected planar graphs with certain symmetries?

Question

There are only five regular polyhedra, and only two more if we allow for quasi-regular polyhedra. So in the sum, there are seven (convex) polyhedra which are both vertex- and edge-transitive.

Since the 1-skeletons of (convex) polyhedra are exactly the 3-connected planar graphs (by Steinitz' theorem), and the vertex- and edge-transitivity of a polyhedron implies the same symmetries for its 1-skeleton, I came to the following "realization":

There are only seven vertex- and edge-transitive, 3-connected, planar graphs (one for each quasi-regular polyhedron).

Is this true or am I missing something?

Answer 1

The following paper seems to prove the existence of only nine edge-transitive 3-connected planar graphs:

• Grünbaum, Branko, and Geoffrey C. Shephard. "Edge‐transitive planar graphs." Journal of graph theory 11.2 (1987): 141-155.

These graphs belong to the seven quasi-regular polyhedrons mentioned in my question, and two other, not vertex-transitive polyhedrons (the rhombic dodecahedron and the rhombic triacontahedron). So by ignoring the not vertex-transitive graphs, we are indeed left with exactly seven vertex- and edge-transitive 3-connected planar graphs.

I have not checked the full proof, so I cannot tell how elementary it is to show this.

Answer 2

Yes. With all those restrictions, you're restricted to those seven polyhedra.

If you take out the planar part, you can put a $7\times7$ grid on a torus. There are also many other graphs you can make, such as the following:

Answer 3

As noted in the comments, your conclusion doen't follow as there might be such a graph that does not come from a (quasi)-regular polyhedron. It's an interesting question though, and I think I have a proof. I have little knowledge of graph theory so perhaps I've overcomplicated things. First some notation:

Let $G$ be a finite vertex- and edge-transitive $3$-connected planar graph. Because $G$ is vertex-transitive it is regular, say of degree $d$. Because $G$ is edge-transitive it has at most two types of faces. That is to say, there exist integers $n_2\geq n_1\geq3$ such that every face of $G$ has either $n_1$ or $n_2$ edges. If all faces have the same number of edges, set $n_2=n_1$. Let $V$, $E$ and $F$ denote the number of vertices, edges and faces of $G$, respectively, and let $F_i$ denote the number of faces with $n_i$ edges.

Proposition 1. The degree $d$ satisfies $3\leq d\leq5$.

Clearly $E=\frac{d}{2}V$ and $F\leq\frac{d}{3}V$. By Euler we have $$2=V-E+F\leq V-\frac{d}{2}V+\frac{d}{3}V=\left(1-\frac{d}{6}\right)V,$$ which shows that $d<6$. Clearly $d>2$ because $G$ is $3$-connected, so $3\leq d\leq5$.

Proposition 2. The number of edges of the smaller faces $n_1$ satisfies $3\leq n_1\leq 5$.

Note that $F\leq\frac{d}{n_1}V$ with equality if and only if $n_1=n_2$, so again by Euler $$2=V-E+F\leq V-\frac{d}{2}V+\frac{d}{n_1}V=\left(1-\frac{d}{2}+\frac{d}{n_1}\right)V,$$ and because $d\geq3$ and $n_1>2$ it follows that $1-\frac{3}{2}+\frac{3}{n_1}>0$, which is equivalent to $n_1<6$.

Remark 3. From the above it is also clear that if $n_1>3$, then $$0<1-\frac{d}{2}+\frac{d}{n_1}\leq1-\frac{d}{2}+\frac{d}{4}=1-\frac{d}{4},$$ which shows that $d<4$, and hence $d=3$ by proposition 1.

Proposition 4. The number of edges of the larger faces $n_2$ satisfies $3\leq n_2\leq 5$.

If $n_1=n_2$ we are done, so suppose $n_1\neq n_2$. Then every edge is adjacent to two faces of distinct sizes, hence every vertex is adjacent to an even number of faces, and so $d$ is even. By proposition 1 we get $d=4$ and hence by remark 3 we get $n_1=3$.

Because $G$ is edge-transitive, counting the number of edges for each type of face shows that $n_iF_i=E$ for $i=1,2$. As noted before $E=\frac{d}{2}V=2V$ and $3F_1=n_2F_2=E=2V$, so we see that $$2=V-E+F=V-2V+F_1+F_2 =\left(1-2+\frac{2}{3}+\frac{2}{n_2}\right)V =\left(-\frac{1}{3}+\frac{2}{n_2}\right)V,$$ which as before shows that $n_2<6$.

---

This leaves us with the following table of seven possible combinations of values for $n_1$, $n_2$ and $d$, and the corresponding value of $V$ is easily computed: \begin{align*} n_1&&n_2&&d&&V\\ \hline 3&&3&&3&&4 \\ 3&&3&&4&&6 \\ 3&&3&&5&&12\\ 4&&4&&3&&8 \\ 5&&5&&3&&20\\ 3&&4&&4&&12\\ 3&&5&&4&&30 \end{align*} By some inelegant ad hoc arguments I've been able to prove that for the first six combinations there is a unique edge- and vertex-transitive $3$-connected planar graph $G$ with these values, which is then of course the graph coming from a (quasi)-regular polyhedron. The seventh has been a bit too big for me to rule out other graphs than that of the icosidodecahedron, but with some effort it shouldn't be too difficult to do so. (I'm quite convinced there are no others.)

---

Addendum: As an example of some of the nontrivial 'ad-hockery', I'll illustrate sixth case above, with a few small gaps to be filled in by the reader. Here $n_1=3$, $n_2=4$, $d=4$ and $V=12$. In every vertex, two squares and two triangles meet alternatingly, and every edge is adjacent to a triangle and a square. So for any given a vertex $A$, we can immediately draw vertices $B$, $C$, $D$ and $E$ adjacent to it, which form two triangles, say $ABC$ and $ADE$. Note that $B$ and $C$ cannot be adjacent to $D$ and $E$, as otherwise three triangles would meet in $A$. Then for two squares to meet in $A$, without loss of generality $B$ and $E$ have a common neighbour, say $F$, and $C$ and $D$ have a common neighbour, say $G$, yielding the following image:

Note that $F$ and $G$ are indeed distinct, as otherwise the edges $BC$ and $DE$ would be adjacent to two triangles. The dashed lines in the image represent remaining edges for the drawn vertices, as we know the graph is $4$-regular. As every edge is adjacent to a square and a triangle, we get the following image:

Because no two triangles can share an edge, the vertices at adjacent corners of the picture are indeed distinct. That is, $T\neq U$ and $T\neq W$ and $V\neq U$ and $V\neq W$. If $T=V$ and $U=W$ then we have a $4$-regular graph on $9$ vertices, which can clearly not be extended to a $3$-connected graph on $12$ vertices. If $T=V$ and $U\neq W$ then there are two vertices left to be drawn, and only two vertices in the drawn graph that they can connect to, contradicting $4$-regularity. So $T\neq V$ and by symmetry $U\neq W$.

Then only one vertex remains to be drawn, and by $4$-regularity it must share an edge with precisely $T$, $U$, $V$ and $W$. Then only two edges between $T$, $U$, $V$ and $W$ remain. They cannot be $TU$ or $VW$ because then two triangles would share an edge. In fact they must be $TW$ and $UV$ for the edges $UO$, $OE$ and $EV$ as well as $TC$, $CB$ and $CW$ to be adjacent to squares. And so we have the $1$-skeleton of the cuboctahedron.