ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 20 (2021) 195–197
https://doi.org/10.26493/1855-3974.2334.331
(Also available at http://amc-journal.eu)
A simple and elementary proof of Whitney’s
unique embedding theorem
Gunnar Brinkmann *
Applied Mathematics, Computer Science and Statistics, Ghent University, Belgium
Received 13 May 2020, accepted 12 February 2021, published online 27 October 2021
Abstract
In this note we give a short and elementary proof of a more general version of Whit-
ney’s theorem that 3-connected planar graphs have a unique embedding in the plane. A
consequence of the theorem is also that cubic plane graphs cannot be embedded in a higher
genus with a simple dual. The aim of this paper is to promote a simple and elementary
proof, which is especially well suited for lectures presenting Whitney’s theorem.
Keywords: Polyhedra, graph, embedding.
Math. Subj. Class. (2020): 05C10, 57M60, 57M15
1 Introduction
Whitney’s famous unique embedding theorem has been formulated in various equivalent
forms. One form is that the facial cycles of 3-connected graphs embedded in the plane are
well determined, so that for any two embeddings there is a graph isomorphism between
the duals. Another is (implied by the Jordan-Schönflies Theorem) that any two topological
embeddings of a graph on the sphere can be mapped onto each other by a homeomorphism
of the sphere that maps the two images of a vertex onto each other.
We will formulate the theorem and describe the proof in the language of combinatorial
embeddings in oriented closed surfaces. For the translation to the language of topological
2-cell embeddings, methods from standard books like [1] or [3] can be used.
We interpret each edge {u, v} of an undirected embedded graph G as two directed
edges: e = (u, v) and its inverse e−1 = (v, u). An embedded graph in an oriented closed
surface is a graph where for every vertex u there is a cyclic order of all edges (u, .) (usually
called a rotation). The cyclic ordering defines the orientation around the vertex. We write
*I would like to thank Bojan Mohar for pointing me to the earlier uses of the crossing Jordan curves argument!
E-mail address: gunnar.brinkmann@ugent.be (Gunnar Brinkmann)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
196 Ars Math. Contemp. 20 (2021) 195–197
nx(e) for the next edge in the order around the starting point of a directed edge e. The
inverse graph or mirror image is the graph G−1 with all cyclic orders reversed.
A face in an embedded graph G is a directed cyclic walk e0, . . . , en−1, so that for
0 ≤ i < n we have that nx(e−1i ) = e(i+1) (mod n). We say that the set {e,nx(e)} forms an
angle of G and G−1 if one of them has a face containing e−1,nx(e) as a subsequence. In
this case the other has a face containing nx(e)−1, e. If a face is a simple cyclic walk, we call
the corresponding undirected cycle also a (simple) facial cycle. We consider an embedded
graph G and its mirror image G−1 as equivalent, as the faces have the same sequences of
underlying undirected edges – only in reversed order. The genus of an embedded graph can
be computed by the Euler formula using the number v of vertices, e of (undirected) edges,
and f of faces as γ(G) = 2−(v−e+f)2 . We refer to a (not necessarily embedded) graph that
can be embedded with genus 0 as planar and to an embedded graph with genus 0 as plane.
With this notation and concept of equivalence Whitney’s famous theorem [5] can be
shortly stated as:
A 3-connected planar graph has an – up to equivalence – unique embedding
in the plane.
We will prove a stronger theorem using the concept of polyhedral embedding that re-
quires some important properties of polyhedra – that is plane 3-connected graphs – but
allows higher genera. It is an easy consequence of the Jordan Curve Theorem that polyhe-
dra are polyhedral embeddings.
Definition 1.1. A polyhedral embedding of a graph G = (V,E) in an oriented closed
surface is an embedding so that each facial walk is a simple cycle and the intersection of
any two faces is either empty, a single vertex or a single edge.
For cubic embedded graphs this is equivalent to the dual graph being simple.
The argument of crossing Jordan curves that we will use in the proof was first published
by Thomassen in [4], but also known to Robertson and later used by Mohar and Robertson
in [2]. See also Theorem 5.7.1 in [3]. In fact, in [4] the argument was used to prove that
3-connected planar graphs embedded with genus g > 0 have facewidth at most 2. Together
with Whitney’s theorem, this implies Theorem 1.2. We will give every detail of the proof in
order to make it well suited for lectures presenting Whitney’s theorem, but the arguments
are exactly the same arguments of crossing Jordan curves that Thomassen used – only that
here the planar case, that is: Whitney’s theorem – is included too.
Theorem 1.2. A 3-connected planar graph has an – up to equivalence – unique polyhedral
embedding.
Proof. Let G be a plane embedding of a 3-connected planar graph with mirror image G−1
and let G′ be an embedding different from these two. We say that a vertex of G′ has type 1
if the order is the same as in G, type −1 if it is the same as in G−1 and type 2 otherwise.
As G′ is neither G nor G−1, G′ has a vertex of type 2 or an edge with one vertex of type 1
and one vertex of type −1.
Assume first that there is a vertex v of type 2. Let e0, . . . , ed−1 be the order of edges
around v in G′. If {e0, e1} is not an angle of G, we take this set of edges. Otherwise
assume w.l.o.g. that e1 = nx(e0) in G and let j be minimal so that in G we have nx(ej) ̸=
e(j+1) (mod d). As in G−1 we have nx(ej) = ej−1, the edge e(j+1) (mod d) follows ej
neither in G nor in G′, so {ej , e(j+1) (mod d)} is not an angle in G. W.l.o.g. assume j = 0.
G. Brinkmann: A simple and elementary proof of Whitney’s unique embedding theorem 197
So the order around v in G is e0, ei1 , . . . , eij , e1, eij+1 , . . . , eid−2 with 1 ≤ j < d − 2
and assume w.l.o.g. that ed−1 ∈ {eij+1 , . . . , eid−2}. Let y = max{i1, . . . , ij}, so y < d−1
and (y+1) ∈ {ij+1, . . . , id−2}, which implies that {ey, ey+1} is an angle of G′ with ey ∈
{ei1 , . . . , eij} and ey+1 ∈ {eij+1 , . . . , eid−2}. Let F be the facial cycle in G′ containing
the angle {e0, e1} and F ′ be the facial cycle containing {ey, ey+1}. We have F ̸= F ′ as
otherwise the faces would not be simple cycles. In G these cycles are not facial cycles, but
two Jordan curves crossing each other in v. Due to the Jordan curve theorem, there must be
a second crossing, so F, F ′ are two facial cycles that have at least two vertices in common
that are not endpoints of a common edge – a contradiction to G′ being polyhedral.
Assume now that all vertices are of type 1 or type −1. Then there is an edge e0 with
one vertex of type 1 and one of type −1. Assume that in G the orientation around the type
1 vertex of e0 is e0, e1, . . . , ed and around the type −1 vertex it is e−10 , e′1, . . . , e′d′ , so in G′
it is e0, e1, . . . , ed resp. e′d′ , e
′
d′−1, . . . , e
−1
0 . In G
′ there is a face F containing e−1d , e0, e
′
d′
and another face F ′ containing e′1
−1
, e−10 , e1. In G the corresponding cycles are again no
facial cycles but Jordan curves crossing each other (with one common edge), so like in
the first case we get a contradiction from the fact that there must be a second intersection
between F and F ′.
As plane embeddings of 3-connected graphs are all polyhedral, this also implies Whit-
ney’s theorem, but there are also other consequences that are worth mentioning. They
follow already from Theorem 8.1 in [4]. Note that for graphs with 1- or 2-cut there are no
polyhedral embeddings in any closed orientable surface.
Corollary 1.3.
• There are no polyhedral embeddings of planar graphs in any orientable surface but
the plane.
• There are no embeddings of cubic planar graphs with a simple dual in any orientable
surface but the plane.
ORCID iD
Gunnar Brinkmann https://orcid.org/0000-0003-4168-0877
References
[1] J. L. Gross and T. W. Tucker, Topological Graph Theory, Wiley-Interscience Series in Discrete
Mathematics and Optimization, John Wiley & Sons, New York, 1987.
[2] B. Mohar and N. Robertson, Planar graphs on nonplanar surfaces, J. Comb. Theory Ser. B 68
(1996), 87–111, doi:10.1006/jctb.1996.0058.
[3] B. Mohar and C. Thomassen, Graphs on Surfaces, Johns Hopkins Studies in the Mathematical
Sciences, Johns Hopkins University Press, Baltimore, Maryland, 2001.
[4] C. Thomassen, Embeddings of graphs with no short noncontractible cycles, J. Comb. Theory Ser.
B 48 (1990), 155–177, doi:10.1016/0095-8956(90)90115-g.
[5] H. Whitney, 2-isomorphic graphs, Amer. J. Math. 55 (1933), 245–254, doi:10.2307/2371127.