Mixing
Are there only seven 3-connected planar graphs with certain symmetries?
Clash Royale CLAN TAG#URR8PPP
up vote
5
down vote
favorite
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?
combinatorics graph-theory symmetry polyhedra planar-graph
edited Jul 28 at 14:33
Especially Lime
19.1k22252
asked Jul 27 at 10:34
M. Winter
17.6k62764
add a comment |Â
up vote
5
down vote
favorite
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?
combinatorics graph-theory symmetry polyhedra planar-graph
edited Jul 28 at 14:33
Especially Lime
19.1k22252
asked Jul 27 at 10:34
M. Winter
17.6k62764
2
I think this is correct, but it doesn't immediately follow: note that not every vertex- and edge-transitive planar graph will necessarily have a realization as a suitably symmetric polyhedron, because you might lose symmetry along the way. (For instance, there might be no embedding in which all edges have the same length.)
– Steven Stadnicki
Jul 28 at 1:18
@StevenStadnicki You are right! How do we know that the symmetries can always be realized in the polyhedron? Do you have some elementary proof, or a source for this?
– M. Winter
Jul 28 at 7:34
add a comment |Â
up vote
5
down vote
favorite
up vote
5
down vote
favorite
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?
combinatorics graph-theory symmetry polyhedra planar-graph
edited Jul 28 at 14:33
Especially Lime
19.1k22252
asked Jul 27 at 10:34
M. Winter
17.6k62764
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?
combinatorics graph-theory symmetry polyhedra planar-graph
edited Jul 28 at 14:33
Especially Lime
19.1k22252
asked Jul 27 at 10:34
M. Winter
17.6k62764
edited Jul 28 at 14:33
Especially Lime
19.1k22252
edited Jul 28 at 14:33
Especially Lime
19.1k22252
edited Jul 28 at 14:33
Especially Lime
19.1k22252
19.1k22252
asked Jul 27 at 10:34
M. Winter
17.6k62764
asked Jul 27 at 10:34
M. Winter
17.6k62764
asked Jul 27 at 10:34
M. Winter
17.6k62764
17.6k62764
2
I think this is correct, but it doesn't immediately follow: note that not every vertex- and edge-transitive planar graph will necessarily have a realization as a suitably symmetric polyhedron, because you might lose symmetry along the way. (For instance, there might be no embedding in which all edges have the same length.)
– Steven Stadnicki
Jul 28 at 1:18
@StevenStadnicki You are right! How do we know that the symmetries can always be realized in the polyhedron? Do you have some elementary proof, or a source for this?
– M. Winter
Jul 28 at 7:34
add a comment |Â
2
I think this is correct, but it doesn't immediately follow: note that not every vertex- and edge-transitive planar graph will necessarily have a realization as a suitably symmetric polyhedron, because you might lose symmetry along the way. (For instance, there might be no embedding in which all edges have the same length.)
– Steven Stadnicki
Jul 28 at 1:18
@StevenStadnicki You are right! How do we know that the symmetries can always be realized in the polyhedron? Do you have some elementary proof, or a source for this?
– M. Winter
Jul 28 at 7:34
2
2
I think this is correct, but it doesn't immediately follow: note that not every vertex- and edge-transitive planar graph will necessarily have a realization as a suitably symmetric polyhedron, because you might lose symmetry along the way. (For instance, there might be no embedding in which all edges have the same length.)
– Steven Stadnicki
Jul 28 at 1:18
I think this is correct, but it doesn't immediately follow: note that not every vertex- and edge-transitive planar graph will necessarily have a realization as a suitably symmetric polyhedron, because you might lose symmetry along the way. (For instance, there might be no embedding in which all edges have the same length.)
– Steven Stadnicki
Jul 28 at 1:18
@StevenStadnicki You are right! How do we know that the symmetries can always be realized in the polyhedron? Do you have some elementary proof, or a source for this?
– M. Winter
Jul 28 at 7:34
@StevenStadnicki You are right! How do we know that the symmetries can always be realized in the polyhedron? Do you have some elementary proof, or a source for this?
– M. Winter
Jul 28 at 7:34
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
5
down vote
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_2geq n_1geq3$ 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 $3leq dleq5$.
Clearly $E=fracd2V$ and $Fleqfracd3V$. By Euler we have
$$2=V-E+Fleq V-fracd2V+fracd3V=left(1-fracd6right)V,$$
which shows that $d<6$. Clearly $d>2$ because $G$ is $3$-connected, so $3leq dleq5$.
Proposition 2. The number of edges of the smaller faces $n_1$ satisfies $3leq n_1leq 5$.
Note that $Fleqfracdn_1V$ with equality if and only if $n_1=n_2$, so again by Euler
$$2=V-E+Fleq V-fracd2V+fracdn_1V=left(1-fracd2+fracdn_1right)V,$$
and because $dgeq3$ and $n_1>2$ it follows that $1-frac32+frac3n_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-fracd2+fracdn_1leq1-fracd2+fracd4=1-fracd4,$$
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 $3leq n_2leq 5$.
If $n_1=n_2$ we are done, so suppose $n_1neq 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=fracd2V=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+frac23+frac2n_2right)V
=left(-frac13+frac2n_2right)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:
beginalign*
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
endalign*
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, $Tneq U$ and $Tneq W$ and $Vneq U$ and $Vneq 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 $Uneq 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 $Tneq V$ and by symmetry $Uneq 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. They cannot be $TV$ or $UW$ because [argument missing for now]. Hence they are $TW$ and $UV$, and so we have the $1$-skeleton of the cuboctahedron.
answered Jul 28 at 14:20
Servaes
20k33484
Tiny matho: when you say 'the number of small faces', 'the number of larger faces' I think you mean 'the number of edges/verts on a small/large face'. This looks good elsewise, though it'd be great to see at least some of the ad-hockery.
– Steven Stadnicki
Jul 28 at 16:24
The first four graphs are small enough to quickly draw, using the facts that they are planar, $d$-regular and all faces have $n_1$ edges. The next two have taken me some time, though for the sixth case it is very helpful to use the fact that in every vertex, two triangles and two squares meet in an alternating manner. Can't elaborate more than this until Monday, unfortunately. I will try committing my thoughts to paper, maybe that will clarify the arguments to myself.
– Servaes
Jul 28 at 19:31
add a comment |Â
up vote
1
down vote
Yes. With all those restrictions, you're restricted to those seven polyhedra.
If you take out the planar part, you can put a $7times7$ grid on a torus. There are also many other graphs you can make, such as the following:
answered Jul 28 at 1:42
Ed Pegg
9,13932486
Thanks for your answer. Do you have a source or proof for this? Steven Stadnicki brought up a good point in the comments to my question that makes it non-obvious.
– M. Winter
Jul 28 at 7:38
2
-1 This answer lacks any justification.
– Servaes
Jul 28 at 14:22
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
5
down vote
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_2geq n_1geq3$ 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 $3leq dleq5$.
Clearly $E=fracd2V$ and $Fleqfracd3V$. By Euler we have
$$2=V-E+Fleq V-fracd2V+fracd3V=left(1-fracd6right)V,$$
which shows that $d<6$. Clearly $d>2$ because $G$ is $3$-connected, so $3leq dleq5$.
Proposition 2. The number of edges of the smaller faces $n_1$ satisfies $3leq n_1leq 5$.
Note that $Fleqfracdn_1V$ with equality if and only if $n_1=n_2$, so again by Euler
$$2=V-E+Fleq V-fracd2V+fracdn_1V=left(1-fracd2+fracdn_1right)V,$$
and because $dgeq3$ and $n_1>2$ it follows that $1-frac32+frac3n_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-fracd2+fracdn_1leq1-fracd2+fracd4=1-fracd4,$$
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 $3leq n_2leq 5$.
If $n_1=n_2$ we are done, so suppose $n_1neq 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=fracd2V=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+frac23+frac2n_2right)V
=left(-frac13+frac2n_2right)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:
beginalign*
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
endalign*
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, $Tneq U$ and $Tneq W$ and $Vneq U$ and $Vneq 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 $Uneq 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 $Tneq V$ and by symmetry $Uneq 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. They cannot be $TV$ or $UW$ because [argument missing for now]. Hence they are $TW$ and $UV$, and so we have the $1$-skeleton of the cuboctahedron.
answered Jul 28 at 14:20
Servaes
20k33484
Tiny matho: when you say 'the number of small faces', 'the number of larger faces' I think you mean 'the number of edges/verts on a small/large face'. This looks good elsewise, though it'd be great to see at least some of the ad-hockery.
– Steven Stadnicki
Jul 28 at 16:24
The first four graphs are small enough to quickly draw, using the facts that they are planar, $d$-regular and all faces have $n_1$ edges. The next two have taken me some time, though for the sixth case it is very helpful to use the fact that in every vertex, two triangles and two squares meet in an alternating manner. Can't elaborate more than this until Monday, unfortunately. I will try committing my thoughts to paper, maybe that will clarify the arguments to myself.
– Servaes
Jul 28 at 19:31
add a comment |Â
up vote
5
down vote
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_2geq n_1geq3$ 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 $3leq dleq5$.
Clearly $E=fracd2V$ and $Fleqfracd3V$. By Euler we have
$$2=V-E+Fleq V-fracd2V+fracd3V=left(1-fracd6right)V,$$
which shows that $d<6$. Clearly $d>2$ because $G$ is $3$-connected, so $3leq dleq5$.
Proposition 2. The number of edges of the smaller faces $n_1$ satisfies $3leq n_1leq 5$.
Note that $Fleqfracdn_1V$ with equality if and only if $n_1=n_2$, so again by Euler
$$2=V-E+Fleq V-fracd2V+fracdn_1V=left(1-fracd2+fracdn_1right)V,$$
and because $dgeq3$ and $n_1>2$ it follows that $1-frac32+frac3n_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-fracd2+fracdn_1leq1-fracd2+fracd4=1-fracd4,$$
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 $3leq n_2leq 5$.
If $n_1=n_2$ we are done, so suppose $n_1neq 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=fracd2V=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+frac23+frac2n_2right)V
=left(-frac13+frac2n_2right)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:
beginalign*
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
endalign*
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, $Tneq U$ and $Tneq W$ and $Vneq U$ and $Vneq 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 $Uneq 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 $Tneq V$ and by symmetry $Uneq 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. They cannot be $TV$ or $UW$ because [argument missing for now]. Hence they are $TW$ and $UV$, and so we have the $1$-skeleton of the cuboctahedron.
answered Jul 28 at 14:20
Servaes
20k33484
Tiny matho: when you say 'the number of small faces', 'the number of larger faces' I think you mean 'the number of edges/verts on a small/large face'. This looks good elsewise, though it'd be great to see at least some of the ad-hockery.
– Steven Stadnicki
Jul 28 at 16:24
The first four graphs are small enough to quickly draw, using the facts that they are planar, $d$-regular and all faces have $n_1$ edges. The next two have taken me some time, though for the sixth case it is very helpful to use the fact that in every vertex, two triangles and two squares meet in an alternating manner. Can't elaborate more than this until Monday, unfortunately. I will try committing my thoughts to paper, maybe that will clarify the arguments to myself.
– Servaes
Jul 28 at 19:31
add a comment |Â
up vote
5
down vote
up vote
5
down vote
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_2geq n_1geq3$ 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 $3leq dleq5$.
Clearly $E=fracd2V$ and $Fleqfracd3V$. By Euler we have
$$2=V-E+Fleq V-fracd2V+fracd3V=left(1-fracd6right)V,$$
which shows that $d<6$. Clearly $d>2$ because $G$ is $3$-connected, so $3leq dleq5$.
Proposition 2. The number of edges of the smaller faces $n_1$ satisfies $3leq n_1leq 5$.
Note that $Fleqfracdn_1V$ with equality if and only if $n_1=n_2$, so again by Euler
$$2=V-E+Fleq V-fracd2V+fracdn_1V=left(1-fracd2+fracdn_1right)V,$$
and because $dgeq3$ and $n_1>2$ it follows that $1-frac32+frac3n_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-fracd2+fracdn_1leq1-fracd2+fracd4=1-fracd4,$$
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 $3leq n_2leq 5$.
If $n_1=n_2$ we are done, so suppose $n_1neq 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=fracd2V=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+frac23+frac2n_2right)V
=left(-frac13+frac2n_2right)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:
beginalign*
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
endalign*
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, $Tneq U$ and $Tneq W$ and $Vneq U$ and $Vneq 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 $Uneq 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 $Tneq V$ and by symmetry $Uneq 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. They cannot be $TV$ or $UW$ because [argument missing for now]. Hence they are $TW$ and $UV$, and so we have the $1$-skeleton of the cuboctahedron.
answered Jul 28 at 14:20
Servaes
20k33484
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_2geq n_1geq3$ 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 $3leq dleq5$.
Clearly $E=fracd2V$ and $Fleqfracd3V$. By Euler we have
$$2=V-E+Fleq V-fracd2V+fracd3V=left(1-fracd6right)V,$$
which shows that $d<6$. Clearly $d>2$ because $G$ is $3$-connected, so $3leq dleq5$.
Proposition 2. The number of edges of the smaller faces $n_1$ satisfies $3leq n_1leq 5$.
Note that $Fleqfracdn_1V$ with equality if and only if $n_1=n_2$, so again by Euler
$$2=V-E+Fleq V-fracd2V+fracdn_1V=left(1-fracd2+fracdn_1right)V,$$
and because $dgeq3$ and $n_1>2$ it follows that $1-frac32+frac3n_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-fracd2+fracdn_1leq1-fracd2+fracd4=1-fracd4,$$
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 $3leq n_2leq 5$.
If $n_1=n_2$ we are done, so suppose $n_1neq 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=fracd2V=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+frac23+frac2n_2right)V
=left(-frac13+frac2n_2right)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:
beginalign*
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
endalign*
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, $Tneq U$ and $Tneq W$ and $Vneq U$ and $Vneq 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 $Uneq 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 $Tneq V$ and by symmetry $Uneq 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. They cannot be $TV$ or $UW$ because [argument missing for now]. Hence they are $TW$ and $UV$, and so we have the $1$-skeleton of the cuboctahedron.
answered Jul 28 at 14:20
Servaes
20k33484
edited Jul 30 at 12:41
answered Jul 28 at 14:20
Servaes
20k33484
answered Jul 28 at 14:20
Servaes
20k33484
answered Jul 28 at 14:20
Servaes
20k33484
20k33484
Tiny matho: when you say 'the number of small faces', 'the number of larger faces' I think you mean 'the number of edges/verts on a small/large face'. This looks good elsewise, though it'd be great to see at least some of the ad-hockery.
– Steven Stadnicki
Jul 28 at 16:24
The first four graphs are small enough to quickly draw, using the facts that they are planar, $d$-regular and all faces have $n_1$ edges. The next two have taken me some time, though for the sixth case it is very helpful to use the fact that in every vertex, two triangles and two squares meet in an alternating manner. Can't elaborate more than this until Monday, unfortunately. I will try committing my thoughts to paper, maybe that will clarify the arguments to myself.
– Servaes
Jul 28 at 19:31
add a comment |Â
Tiny matho: when you say 'the number of small faces', 'the number of larger faces' I think you mean 'the number of edges/verts on a small/large face'. This looks good elsewise, though it'd be great to see at least some of the ad-hockery.
– Steven Stadnicki
Jul 28 at 16:24
The first four graphs are small enough to quickly draw, using the facts that they are planar, $d$-regular and all faces have $n_1$ edges. The next two have taken me some time, though for the sixth case it is very helpful to use the fact that in every vertex, two triangles and two squares meet in an alternating manner. Can't elaborate more than this until Monday, unfortunately. I will try committing my thoughts to paper, maybe that will clarify the arguments to myself.
– Servaes
Jul 28 at 19:31
Tiny matho: when you say 'the number of small faces', 'the number of larger faces' I think you mean 'the number of edges/verts on a small/large face'. This looks good elsewise, though it'd be great to see at least some of the ad-hockery.
– Steven Stadnicki
Jul 28 at 16:24
Tiny matho: when you say 'the number of small faces', 'the number of larger faces' I think you mean 'the number of edges/verts on a small/large face'. This looks good elsewise, though it'd be great to see at least some of the ad-hockery.
– Steven Stadnicki
Jul 28 at 16:24
The first four graphs are small enough to quickly draw, using the facts that they are planar, $d$-regular and all faces have $n_1$ edges. The next two have taken me some time, though for the sixth case it is very helpful to use the fact that in every vertex, two triangles and two squares meet in an alternating manner. Can't elaborate more than this until Monday, unfortunately. I will try committing my thoughts to paper, maybe that will clarify the arguments to myself.
– Servaes
Jul 28 at 19:31
The first four graphs are small enough to quickly draw, using the facts that they are planar, $d$-regular and all faces have $n_1$ edges. The next two have taken me some time, though for the sixth case it is very helpful to use the fact that in every vertex, two triangles and two squares meet in an alternating manner. Can't elaborate more than this until Monday, unfortunately. I will try committing my thoughts to paper, maybe that will clarify the arguments to myself.
– Servaes
Jul 28 at 19:31
add a comment |Â
up vote
1
down vote
Yes. With all those restrictions, you're restricted to those seven polyhedra.
If you take out the planar part, you can put a $7times7$ grid on a torus. There are also many other graphs you can make, such as the following:
answered Jul 28 at 1:42
Ed Pegg
9,13932486
Thanks for your answer. Do you have a source or proof for this? Steven Stadnicki brought up a good point in the comments to my question that makes it non-obvious.
– M. Winter
Jul 28 at 7:38
2
-1 This answer lacks any justification.
– Servaes
Jul 28 at 14:22
add a comment |Â
up vote
1
down vote
Yes. With all those restrictions, you're restricted to those seven polyhedra.
If you take out the planar part, you can put a $7times7$ grid on a torus. There are also many other graphs you can make, such as the following:
answered Jul 28 at 1:42
Ed Pegg
9,13932486
Thanks for your answer. Do you have a source or proof for this? Steven Stadnicki brought up a good point in the comments to my question that makes it non-obvious.
– M. Winter
Jul 28 at 7:38
2
-1 This answer lacks any justification.
– Servaes
Jul 28 at 14:22
add a comment |Â
up vote
1
down vote
up vote
1
down vote
Yes. With all those restrictions, you're restricted to those seven polyhedra.
If you take out the planar part, you can put a $7times7$ grid on a torus. There are also many other graphs you can make, such as the following:
answered Jul 28 at 1:42
Ed Pegg
9,13932486
Yes. With all those restrictions, you're restricted to those seven polyhedra.
If you take out the planar part, you can put a $7times7$ grid on a torus. There are also many other graphs you can make, such as the following:
answered Jul 28 at 1:42
Ed Pegg
9,13932486
answered Jul 28 at 1:42
Ed Pegg
9,13932486
answered Jul 28 at 1:42
Ed Pegg
9,13932486
answered Jul 28 at 1:42
Ed Pegg
9,13932486
9,13932486
Thanks for your answer. Do you have a source or proof for this? Steven Stadnicki brought up a good point in the comments to my question that makes it non-obvious.
– M. Winter
Jul 28 at 7:38
2
-1 This answer lacks any justification.
– Servaes
Jul 28 at 14:22
add a comment |Â
Thanks for your answer. Do you have a source or proof for this? Steven Stadnicki brought up a good point in the comments to my question that makes it non-obvious.
– M. Winter
Jul 28 at 7:38
2
-1 This answer lacks any justification.
– Servaes
Jul 28 at 14:22
Thanks for your answer. Do you have a source or proof for this? Steven Stadnicki brought up a good point in the comments to my question that makes it non-obvious.
– M. Winter
Jul 28 at 7:38
Thanks for your answer. Do you have a source or proof for this? Steven Stadnicki brought up a good point in the comments to my question that makes it non-obvious.
– M. Winter
Jul 28 at 7:38
2
2
-1 This answer lacks any justification.
– Servaes
Jul 28 at 14:22
-1 This answer lacks any justification.
– Servaes
Jul 28 at 14:22
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2864283%2fare-there-only-seven-3-connected-planar-graphs-with-certain-symmetries%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
2
I think this is correct, but it doesn't immediately follow: note that not every vertex- and edge-transitive planar graph will necessarily have a realization as a suitably symmetric polyhedron, because you might lose symmetry along the way. (For instance, there might be no embedding in which all edges have the same length.)
– Steven Stadnicki
Jul 28 at 1:18
@StevenStadnicki You are right! How do we know that the symmetries can always be realized in the polyhedron? Do you have some elementary proof, or a source for this?
– M. Winter
Jul 28 at 7:34