ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 20 (2021) 143–149
https://doi.org/10.26493/1855-3974.2194.eab
(Also available at http://amc-journal.eu)
Strongly involutive self-dual polyhedra
Javier Bracho *
Instituto de Matemáticas, UNAM, Mexico
Luis Montejano †
Instituto de Matemáticas, UNAM-Campus Juriquilla, Mexico
Eric Pauli Pérez ‡
Instituto de Matemáticas, UNAM-Campus Juriquilla and IMAG, Univ. Montpellier,
CNRS, Montpellier, France
Jorge Luis Ramı́rez Alfonsı́n §
UMI2924 - Jean-Christophe Yoccoz, CNRS-IMPA and IMAG, Univ. Montpellier,
CNRS, Montpellier, France
Received 10 December 2019, accepted 11 October 2020, published online 2 September 2021
Abstract
A polyhedron is a graph which is simple, planar and 3-connected. In this note, we
classify the family of strongly involutive self-dual polyhedra. The latter is done by using
a well-known result due to Tutte characterizing 3-connected graphs. We also show that
in this special class of polyhedra self-duality behaves topologically as the antipodal map-
ping. These self-dual polyhedra are related with several problems in convex and discrete
geometry including the Vázsonyi problem.
Keywords: Polyhedra, graphs, duality, self-dual, antipodal.
Math. Subj. Class. (2020): 05C15, 05C10
*Supported by PAPIIT-UNAM under project IN109218.
†Supported by CONACyT under project 166306 and support from PAPIIT-UNAM under project IN112614.
‡Supported by CONACyT Grant 268597.
§Supported by MATHAMSUD 18-MATH-01, Project FLaNASAGraTA and by PICS07848 CNRS.
E-mail addresses: jbracho@im.unam.mx (Javier Bracho), luis@im.unam.mx (Luis Montejano),
eric@im.unam.mx (Eric Pauli Pérez), jorge.ramirez-alfonsin@umontpellier.fr (Jorge Luis Ramı́rez Alfonsı́n)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
144 Ars Math. Contemp. 20 (2021) 143–149
1 Introduction
A planar and 3-connected graph G = (V,E) can be drawn in essentially one way on the
sphere or the plane. This fundamental fact is a result of the work of Whitney [14]. It
tells us that we not only have the sets V and E defined, but that the set F of faces is
also determined, and furthermore the dual graph G∗ is well defined. The dual graph G∗ is
the graph whose vertex set V ∗ is the set of faces F of G, and two new vertices in G∗ are
connected by an edge if and only if the faces that define them are adjacent in G.
In this class of graphs, each face f is determined by its boundary walk, that is, a cycli-
cally ordered sequence (v1, v2, . . . , vk) consisting of the vertices (and the edges) that are
in the closure of the region defining the face f (see [4]). In this sense we can say that u
incides on f , if it is any of the elements v1, v2, . . . , vk of the cycle defining the face f . We
denote this situation simply by u ∈ f . From Steinitz’s theorem [12] we know that it is
the same to talk about polyhedra in the sense of convex polytopes and to talk about these
graphs, so we will refer to them as polyhedra. A polyhedron is a graph G that is simple
(without loops and multiple edges), planar and 3-connected.
A polyhedron P is said to be self-dual if there exists an isomorphism of graphs τ : P →
P∗. This isomorphism is called a duality isomorphism. There may be several of these
duality isomorphisms and each of them is a bijection between vertices and faces of P ,
such that adjacent vertices correspond to adjacent faces. We are interested in such an
isomorphism that satisfies two more properties:
(1) For each pair u, v of vertices, u ∈ τ(v) if and only if v ∈ τ(u).
(2) For every vertex v, we have that v /∈ τ(v).
Such an isomorphism will be called a strong involution. If P is a self-dual polyhedron
admitting a strong involution τ , we will say that P is a strongly involutive polyhedron.
Strongly involutive self-dual polyhedra are very common, like for example wheels on
n-cycles with n odd and hyperwheels on n-cycles with n-even (see [11]). In fact the
relevance of strongly involutive self-dual polyhedra is partially related with the famous
Vázsonyi problem. Let T be a finite set of points of diameter h in Euclidean d-space.
Characterize those sets T for which the diameter is attained a maximal number of times
as a segment of length h with both endpoints in T . Y. S. Kupitz et al. [5], call these sets
extremal configurations. For d = 3, if T is an extremal configuration and V is the inter-
section of balls of radius h with centers in points of T , a facial structure can be defined on
the boundary of V that is strongly self-dual in the sense that it admits an duality isomor-
phism that is involution and is fixed-point free when acting as an automorphism of the first
barycentric subdivision of the boundary cell complex of V (see [5]). Indeed, this unusual
connection between discrete and convex geometry attracted the attention of several mathe-
maticians to this and other related problems. See, for example L. Lóvasz [6], L. Montejano
and E. Roldán-Pensado [9], L. Montejano et al. [8] and the work of Bezdek et al. [2]. For
more about the Vázsonyi problem see [7].
In order to have a good understanding of strongly involutive self-dual polyhedra, we
will use a result due to Tutte [13] establishing that every 3-connected graph is either a
wheel (a cycle where every vertex is also connected with a central vertex o) or it can be
obtained from a wheel by a finite sequence of two operations: adding an edge between any
pair of vertices and splitting a given vertex v, with degree δ(v) ≥ 4, into two new adjacent
vertices v′ and v′′ in such a way that the new graph obtained is still 3-connected.
J. Bracho et al.: Strongly involutive self-dual polyhedra 145
In the following section we briefly summarize the notions and notation in relation with
the above Tutte’s result restricted to the case of simple and planar graphs. In [1], Grünbaum
and Barnette used this idea for giving two proofs of Steinitz’s Theorem. In Section 3, we
show our main results that classify the strongly involutive self-dual polyhedra. Finally, in
Section 4, we give a geometric interpretation of strong involutions by proving that such a
duality is topologically equivalent to the antipodal mapping on the sphere.
2 Tutte’s theorem for polyhedra
In this section we summarize the main ideas and terminology of a recursive classification
of spherical polyhedra. These results are deduced from Tutte’s work and the details can be
found in [10]. Let G be a polyhedron and e = (uv) any edge of G. We write G\e for the
graph obtained from G by deleting e. We write G/e for the graph obtained from G\e by
identifying its endpoints u and v in a single vertex uv. In the same way, given any subset
X of V , we write G\X for the graph obtained from G by ommiting the elements of X and
any edge such that one of its endpoints is an element of X . We will say that e = (uv)
can be deleted if G\e is a polyhedron and we say that e = (uv) can be contracted if G/e
is a polyhedron. We will say that X is an n-cutting set if it has n vertices and G\X is
not connected. According to Tutte’s terminology, we will say that an edge e is essential if
neither G\e nor G/e are polyhedra. In other words, e is essential if it cannot be deleted and
it cannot be contracted.
Theorem 2.1 ([10]). The following statements are equivalent.
(1) G is a wheel.
(2) Every edge is essential.
(3) Every edge is on a triangular face and has one of its endpoints of degree 3.
This result can be rephrased as follows.
Remark 2.2. Every polyhedron is either a wheel or it can be obtained by a wheel by adding
new edges within faces of the polyhedron or its dual’s. Equivalently: if a polyhedron is not
a wheel there is always a not essential edge, this means, an edge we can delete or contract
in order to obtain a new polyhedron with one fewer edge.
In this way we can reduce any polyhedron by a finite sequence of this operations until
we obtain a wheel. It happens that one can obtain different wheels from a given polyhedron
by selecting different sequences of non essential edges.
3 Strongly involutive polyhedra
Throughout this section, we let P = (V,E, F, τ) be a strongly involutive self-dual poly-
hedron and (ab) ∈ E any edge of P . By definition τ(a) and τ(b) are adjacent faces of P ,
thus there must be an edge (xy) ∈ E such that τ(a) ∩ τ(b) = (xy) and condition (1) of
strong involution implies that τ(x) ∩ τ(y) = (ab). We will write τ(ab) for the edge (xy).
We will say that (ab) is a diameter if and only if a ∈ τ(b) (and therefore b ∈ τ(a)).
Lemma 3.1. If (ab) and (xy) are both diameters, then P is the tetrahedron K4.
146 Ars Math. Contemp. 20 (2021) 143–149
Proof. From the hypotheses we deduce a ∈ τ(x)∩τ(y)∩τ(b) and x ∈ τ(a)∩τ(b)∩τ(y),
then {a, x} ⊂ τ(y) ∩ τ(b) but from the 3-connectivity, the intersection of any two faces
must be empty, a single vertex or a single edge, thus (ax) is an edge, otherwise {a, x} is
a 2-cutting set. Analogously, (bx) is an edge. In the same way, (ya) and (yb) are edges.
It follows that the induced graph on these four vertices is K4. In addition, we have the
faces τ(a), τ(b), τ(x) and τ(y) are triangles. Suppose there exist additional vertices. Take
any vertex v ∈ V \ {a, b, x, y} such that v is connected to some vertex in {a, b, x, y} by
an edge. Assume, without loss of generality, that (av) is an edge. This is a contradiction
because in that case face τ(a) should form a cycle with at least four edges.
Lemma 3.2. If (ab) is a diameter and (xy) is not, then {a, b, x} and {a, b, y} are 3-cutting
sets of P .
Proof. From the hypotheses we can deduce that (τ(a)∪τ(b))\(xy) and (τ(x)∪τ(y))\(ab)
are cycles whose intersection is the set {a, b}, then we can observe that (τ(a) ∪ τ(b)) \
(xy)) ∪ (ab) is the union of two cycles γ1, γ2 whose intersection is the edge (ab) and thus
P \ γ1 consists of two connected pieces R1, R2 and also P \ γ2 consists of two connected
pieces S1, S2. Since τ(x)∩τ(y) = (ab) = γ1∩γ2, we may assume τ(x)\ (ab) ⊂ R1∩S1
and τ(y) \ (ab) ⊂ R2 ∩ S2. Let be w ∈ (τ(y) \ (ab)) \ γ1 ⊂ R2 ∩ S2. It exists because
otherwise τ(y) = γ1, and therefore x ∈ τ(y), a contradiction since (xy) is not a diameter.
Analogoulsy, let be u ∈ (τ(x) \ (ab)) \ γ2 ⊂ S1 ∩R1. Then in the graphs P\{a, b, y} and
P \ {a, b, x}, the vertices u and w are disconnected.
Theorem 3.3. If P is not a wheel, then there exists an edge e satisfying the three following
conditions:
(1) e is not on a triangular face,
(2) e is not in a 3-cutting set and
(3) e is not a diameter.
Proof. Since P is not a wheel then, by Theorem 2.1, there is a not essential edge, say e
that can be either deleted or contracted. In fact we ensure, since P is self-dual, there is an
edge that can be contracted, otherwise we can take an edge e that can be deleted and the
corresponding dual edge e∗ can be contracted in P∗ which is isomorphic to P . Without
loss of generality we may assume e can be contracted in P . We may now check that e
verifies the three desired conditions:
(1) e is not in a triangle. Otherwise, if e were contracted then P/e would have parallel
edges (which is not possible since P/e is simple).
(2) e is not in any 3-cutting set. Otherwise, if e were contracted then P/e would have a
2-cutting set (which is not possible since P/e is 3-connected).
(3) e is not a diameter. Indeed, if e were a diameter then we would have that edge τ(e)
cannot be a diameter (otherwise, by Lemma 3.1, P must be a tetrahedron, that is, a
3-wheel, which is not the case) and thus, by Lemma 3.2, e would be in a 3-cutting
set, which is not possible.
J. Bracho et al.: Strongly involutive self-dual polyhedra 147
Theorem 3.4. Let e = (ab) be an edge which is neither on a triangular face nor in a
3-cutting set nor a diameter. Then, the graph [P/(ab)]\τ(ab), denoted by P⋄ = P⋄ab, is a
strongly involutive self-dual polyhedron.
Proof. Since (ab) satisfies the three properties of last theorem, then P/(ab) is a polyhe-
dron, and therefore its dual P\τ(ab) is also a polyhedron. We will show that P⋄ is a
polyhedron. Indeed, it is simple and planar. We need it to be 3-connected. If it were not,
then it would have a 2-cutting set {m,n}. Since τ(a) and τ(b) are the faces such that
τ(a)∩ τ(b) = τ(ab) we may observe that one of the elements in {m,n} is in τ(a) and the
other is in τ(b). Let’s supose m ∈ τ(a) and n ∈ τ(b). Furthermore the vertex a = b, de-
noted by ab must be one of the elements in {m,n}, otherwise {m,n} would be a 2-cutting
set of P\τ(ab), a contradiction. This implies that in P , a ∈ τ(b) (and therefore b ∈ τ(a)),
so (ab) would be a diameter, which is not by hypothesis. Finally, by definition, P⋄ is self-
dual and it is strongly involutive with isomorphism τ⋄(u) = τ(u) for every u /∈ {a, b}
and with τ⋄(a = b) the face obtained by the union of τ(a) and τ(b) when edge (xy) is
deleted.
By the above theorem, we can define the remove-contract operation in any strongly
involutive polyhedron which is not a wheel: there is at least one edge (ab) that we can
contract and at the same time remove the edge τ(ab) in order to obtain a new strongly
involutive polyhedron. We can apply this operation repeatedly in order to finish with a
strongly involutive wheel (with odd number of vertices in the main cycle). Conversely, we
can start with such a wheel and then diagonalizing faces and splitting their corresponding
vertices carefully in order to expand a strongly involutive polyhedron. By diagonalizing
we mean that given a face that is not a triangle, we add a new edge within the face joining
two non-consecutive vertices.
In the above terms, Theorem 3.4 gives the following.
Corollary 3.5. Every strongly involutive self-dual polyhedra is either a wheel or it can be
obtained from an odd wheel by a finite sequence of operations consisting in diagonalizing
faces of the polyhedron and its dual’s simultaneously.
4 Topological interpretation
In this section we are going to consider topological embeddings of a given graph G on the
surface S2. By Whitney’s Theorem we know that if G is simple, planar and 3-connected,
then any two such embeddings are equivalent in the sense that the set of faces (and their
adjacencies) is fully determined only by the graph (they are independent of the embedding).
It is an interesting fact that with these conditions we can choose one of these embeddings
in such a way that any automorphism of the graph of P acts as an isometry of S2. We will
write this important fact as follows.
Lemma 4.1 (Isometric embedding lemma [11, Lemma 1]). There exists an embedding
i : G → S2 such that for every σ ∈ Aut(G) there exists an isometry σ̃ of S2 satisfying
i ◦ σ = σ̃ ◦ i.
Our goal for now is to interpret geometrically the strong involutions. In the rest of the
section G is the underlying graph (simple, planar and 3-connected) of a strongly involutive
self-dual polyhedron P .
148 Ars Math. Contemp. 20 (2021) 143–149
Let us define G□ the graph of squares of G as follows:
V (G□) = V (G) ∪ F (G) ∪ E(G) and
E(G□) = {(ve) : v ∈ V (G), e ∈ E(G), v ∈ e} ∪
{(ec) : e ∈ E(G), f ∈ F (G), e ∈ f}.
It is easy to observe that G□ is a 3-connected simple planar graph and therefore it can
be drawn on the sphere in such a way that any automorphism of G□ is an isometry. We can
suppose G□ is embedded in that way and we will abuse of notation making no distintion
between G□ and its image under the embedding. By definition, the faces of G□ are all
quadrilaterals of the form (vafb), where v ∈ V (G), a, b ∈ E(G) and f ∈ F (G).
Theorem 4.2. Let τ be a strong involution of P . Then τ̃ is the antipodal mapping α : S2 →
S2, α(x) = −x.
Proof. First we can observe that τ is an automorphism of G□ and condition (1) of strong
involution implies τ2 = id. Therefore, τ̃ (given in Lemma 4.1) must be an involution as
isometry. There are three possible involutive isometries of the sphere: a reflection through
a line (a spherical line), a rotation by π2 and the antipodal mapping (a good reference is [3]).
Only the antipodal mapping has no fixed points, so we will show that τ̃ cannot have fixed
points. We will proceed by contradiction, supposing τ̃ has a fixed point and then we will
conclude there exists a vertex v such that v ∈ τ(v).
If τ is a reflection through a plane H , let us consider v ∈ V (G), a, b ∈ E(G) and
f ∈ F (G) such that H intersects the quadrilateral Q = (vafb) in its interior. The only
points of the edges of quadrilateral Q can intersect H are a and b, so H ∩ S2 = l where l
is the spherical line through a and b, thus we must have τ(v) = f that means v ∈ τ(v).
If τ is a rotation in a line PP ′ (P, P ′ antipodal points on the sphere), let Q = (vafb)
be a quadrilateral containing P . If P is the center (the barycenter) of the quadrilateral, then
since τ is a duality, it must send v into f , but then τ(v) = f , which means v ∈ τ(v). If P
is a or b, say P = a, then the edge (va) is sent to an edge (af ′) where f ′ is a face of G,
distinct from f and containing v, but then the quadrilateral Q′ corresponding to v and f ′
we have τ(v) = f ′, which means v ∈ τ(v). This concludes the proof.
As a consequence of Theorem 4.2 we obtain the following.
Corollary 4.3. For a strongly involutive self-dual polyhedron there is only one duality
which is a strong involution.
References
[1] D. W. Barnette and B. Grünbaum, On Steinitz’s theorem concerning convex 3-polytopes, in:
G. Chartrand and S. F. Kapoor (eds.), The Many Facets of Graph Theory, Springer, Berlin,
volume 110 of Lecture Notes in Mathematics, 1969 pp. 27–40, doi:10.1007/bfb0060102, Pro-
ceedings of the Conference held at Western Michigan University, Kalamazoo, Mich., October
31 - November 2, 1968.
[2] K. Bezdek, Z. Lángi, M. Naszódi and P. Papez, Ball-polyhedra, Discrete Comput. Geom. 38
(2007), 201–230, doi:10.1007/s00454-007-1334-7.
[3] D. A. Brannan, M. F. Esplen and J. J. Gray, Geometry, Cambridge University Press, 2nd edition,
2012.
J. Bracho et al.: Strongly involutive self-dual polyhedra 149
[4] J. L. Gross and T. W. Tucker, Topological Graph Theory, Wiley-Interscience Series in Discrete
Mathematics and Optimization, John Wiley & Sons, New York, 1987.
[5] Y. S. Kupitz, H. Martini and M. A. Perles, Ball polytopes and the Vázsonyi problem, Acta
Math. Hungar. 126 (2010), 99–163, doi:10.1007/s10474-009-9030-0.
[6] L. Lovász, Self-dual polytopes and the chromatic number of distance graphs on the sphere, Acta
Sci. Math. (Szeged) 45 (1983), 317–323, http://acta.bibl.u-szeged.hu/14897/.
[7] H. Martini, L. Montejano and D. Oliveros, Bodies of Constant Width: An Introduction
to Convex Geometry with Applications, Birkhäuser/Springer, Cham, 2019, doi:10.1007/
978-3-030-03868-7.
[8] L. Montejano, E. Pauli, M. Raggi and E. Roldán-Pensado, The graphs behind Reuleaux poly-
hedra, Discrete Comput. Geom. 64 (2020), 1013–1022, doi:10.1007/s00454-020-00220-0.
[9] L. Montejano and E. Roldán-Pensado, Meissner polyhedra, Acta Math. Hungar. 151 (2017),
482–494, doi:10.1007/s10474-017-0697-3.
[10] E. Pauli, Poliedros autoduales fuertemente involutivos, Ph.D. thesis, Universidad Nacional
Autónoma de México, 2020.
[11] B. Servatius and H. Servatius, The 24 symmetry pairings of self-dual maps on the sphere,
Discrete Math. 140 (1995), 167–183, doi:10.1016/0012-365x(94)00293-r.
[12] E. Steinitz, Polyeder und Raumeinteilungen, in: W. F. Meyer (ed.), Encyclopedia of Mathe-
matical Sciences Including Their Applications (in German), Volume 3: Geometry, 1922 pp.
1–139.
[13] W. T. Tutte, A theory of 3-connected graphs, Nederl. Akad. Wetensch. Proc. Ser. 64 (1961),
441–455, doi:10.1016/s1385-7258(61)50045-5.
[14] H. Whitney, Congruent graphs and the connectivity of graphs, Amer. J. Math. 54 (1932), 150–
168, doi:10.2307/2371086.