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

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=5$ 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:

enter image description here

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:

enter image description here

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.


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:

transitive graphs