Plane maps

Written by Claude Opus 5.5 (Anthropic), October 2026. Self-checked by the writing AI. Public domain (CC0).

A van Kampen diagram records a relation in a group by a plane graph whose edges carry generators and whose faces read relators. This course develops such diagrams combinatorially and proves van Kampen's lemma: a word represents the identity exactly when it is the boundary word of a diagram, and the least number of faces of such a diagram is the least number of relators needed to produce the word. This first lesson fixes the plane maps underlying diagrams and proves the operations on them that the later lessons use: faces and Euler's formula, deleting and contracting edges, adding pendant edges, chords and loops, and cutting along a loop. It rests on the lesson Sphere maps of the course on Barnette's conjecture, which develops maps by counting and by linear algebra over the field with two elements; its definitions and notation are used throughout. The second lesson, Words, free groups and Cayley graphs, treats free groups, presentations, walks and Cayley graphs, and the third, Van Kampen's lemma, defines diagrams and proves the lemma.

1. Plane maps and their faces

A map \(M\) consists of a finite set \(\Delta\) of darts, a fixed-point-free involution \(\theta\) and a permutation \(\sigma\), the rotation, such that the group generated by \(\sigma\) and \(\theta\) acts transitively on \(\Delta\); its faces are the orbits of \(\varphi=\sigma\theta\) (Definition 1.1 of Sphere maps). A dart \(d\) leaves its tail and enters its head, the tail of \(\theta d\); a sphere map is a map with \(\chi=V-E+F=2\); the trivial map has one vertex, no darts and one face.

A walk is a finite sequence of darts \((d_1,\ldots,d_n)\) such that each \(d_{i+1}\) leaves the head of \(d_i\). It runs from the tail of \(d_1\) to the head of \(d_n\), and it is closed if these two vertices agree; at every vertex there is the empty closed walk. The reverse of the walk is \((\theta d_n,\ldots,\theta d_1)\). For a dart \(d\) of a face \(f\) of length \(k\), the boundary walk of \(f\) read from \(d\) is \[ (d,\varphi(d),\ldots,\varphi^{k-1}(d)), \] a closed walk by Lemma 1.2 of Sphere maps; reading from another dart of \(f\) rotates it cyclically. A corner of \(f\) is a pair \((\alpha,\beta)\) of consecutive darts of \(f\), that is, \(\beta=\varphi(\alpha)=\sigma(\theta\alpha)\): in the rotation at the head of \(\alpha\), the dart \(\beta\) follows \(\theta\alpha\).

Definition 1.1. A plane map is a sphere map with one distinguished face, its outer face, also called the unbounded face; the other faces are bounded. The trivial map, with its one face as outer face, is a plane map.

The names recall a drawing in the plane, in which the outer face is the unbounded region of the complement. By the embedding theorem, Theorem 5.1 of Sphere maps, a drawing of a connected graph in the sphere gives a sphere map; that theorem is an open obligation of the programme, and it is not used in this course: all statements here concern the combinatorial structure.

Proposition 1.2 (faces and Euler's formula). Let \(D\) be a plane map with \(V\) vertices, \(E\) edges and \(F\) bounded faces.

  1. Every dart lies in exactly one face, and the boundary walk of a face runs once through each of its darts. The lengths of all boundary walks, the outer one included, add up to \(2E\).
  2. In a boundary walk, a dart \(d\) is followed by \(\theta d\) exactly when the head of \(d\) has degree one.
  3. \(V-E+F=1\).

Proof. (1) The faces are the orbits of \(\varphi\), so they partition the \(2E\) darts. (2) The dart after \(d\) is \(\varphi(d)=\sigma(\theta d)\), and \(\sigma(\theta d)=\theta d\) says that \(\theta d\) is the only dart leaving its tail, the head of \(d\). (3) \(D\) is a sphere map with \(F+1\) faces. \(\square\)

Proposition 1.3 (trees). The underlying graph of a plane map without bounded faces is a tree or a single vertex. Conversely, a map whose underlying graph is a tree with at least one edge has exactly one face, and it is a sphere map.

Proof. If \(F=0\), Proposition 1.2(3) gives \(E=V-1\). The cycle space of a connected graph has dimension \(E-V+1\) (Lemma 3.1(a) of Sphere maps), here \(0\), and the edge set of a cycle is a nonzero element of it, so the graph has no cycles. Conversely, a map whose underlying graph is a tree with at least one edge has exactly one face by Lemma 1.5 there, so \(\chi=V-(V-1)+1=2\). \(\square\)

2. Deleting and contracting edges

Proposition 2.1 (deleting an edge between two faces). Let \(e=\{d,\theta d\}\) be an edge of a plane map \(D\) whose darts lie in different faces, written in the order of \(\varphi\) as \[ \begin{gathered} f=(d,a_1,\ldots,a_p),\\ f'=(\theta d,b_1,\ldots,b_q). \end{gathered} \] Then \(D-e\) is a plane map. Its faces are the faces of \(D\) other than \(f\) and \(f'\), together with the face \((a_1,\ldots,a_p,b_1,\ldots,b_q)\), which is the one face of the trivial map if \(p=q=0\). This merged face is the outer face of \(D-e\) if \(f\) or \(f'\) is the outer face of \(D\); otherwise the outer face of \(D\) is the outer face of \(D-e\).

Proof. The two darts of a bridge lie in one face (Proposition 1.6(b) of Sphere maps), so \(e\) is not a bridge. By Proposition 1.6(c) there, \(D-e\) is a sphere map whose faces are as in Lemma 1.4(a) there, which is the stated description. \(\square\)

Proposition 2.2 (deleting an edge with one face). Let both darts of an edge \(e\) lie in one face \(f\) of a plane map \(D\), written \[ f=(d,a_1,\ldots,a_p,\theta d,b_1,\ldots,b_q). \] Then \(e\) is a bridge, and \(D-e\) has two components, \(D_2\) containing the head of \(d\) and \(D_1\) containing its tail; each is a sphere map or a single vertex. The walk \((a_1,\ldots,a_p)\) lies in \(D_2\), the walk \((b_1,\ldots,b_q)\) in \(D_1\), and every other face of \(D\) lies in one of the two. The faces of \(D_1\) are the faces of \(D\) lying in it together with \((b_1,\ldots,b_q)\), the one face of a single vertex if \(q=0\); likewise for \(D_2\) with \((a_1,\ldots,a_p)\).

The dart \(d\) of \(e\) can be chosen so that, if \(f\) is bounded, the outer face of \(D\) lies in \(D_1\). With this choice \(D_1\) is a plane map whose outer face is the outer face of \(D\) if \(f\) is bounded, and \((b_1,\ldots,b_q)\) if \(f\) is the outer face. Its bounded faces are the bounded faces of \(D\) lying in \(D_1\), together with \((b_1,\ldots,b_q)\) when \(f\) is bounded.

Proof. In a sphere map the darts of an edge that is not a bridge lie in different faces (Proposition 1.6(c) of Sphere maps), so \(e\) is a bridge, and by Proposition 1.6(d) there both components of \(D-e\) are sphere maps (an isolated vertex being a trivial map). Lemma 1.4(b) there shows that the faces of \(D-e\) are the faces of \(D\) other than \(f\), together with \((a_1,\ldots,a_p)\) and \((b_1,\ldots,b_q)\), each if it is nonempty; an empty piece belongs to an isolated vertex, which carries one face. The dart \(a_1=\varphi(d)\) leaves the head of \(d\) (Lemma 1.2 there), and \((a_1,\ldots,a_p)\) is a walk avoiding \(e\), so it stays in the component of the head of \(d\); likewise \((b_1,\ldots,b_q)\) starts at the head of \(\theta d\), the tail of \(d\), and stays in its component. Every other face is a closed walk avoiding \(e\), so it lies in one component.

Exchanging the names of \(d\) and \(\theta d\) writes \(f\) as \((\theta d,b_1,\ldots,b_q,d,a_1,\ldots,a_p)\) and exchanges the two components. If \(f\) is bounded, the outer face of \(D\) is a face other than \(f\), so it lies in one component, and we name \(d\) so that this is \(D_1\). The description of \(D_1\) follows. \(\square\)

Contraction. Let \(e=\{d,\theta d\}\) be an edge of a map \(D\) that is not a loop, from \(u\) to \(v\), and let the rotations at its ends be \[ (d,x_1,\ldots,x_k),\qquad(\theta d,y_1,\ldots,y_l). \] The contraction \(D/e\) has the darts other than \(d\) and \(\theta d\), the restriction of \(\theta\), and the rotation that agrees with \(\sigma\) except that \(u\) and \(v\) are replaced by the single vertex with rotation \((x_1,\ldots,x_k,y_1,\ldots,y_l)\). If \(k=l=0\), the map is a single edge and \(D/e\) is the trivial map.

Proposition 2.3 (contracting an edge). If \(e\) is an edge of a plane map \(D\) that is not a loop, then \(D/e\) is a plane map. Its faces are the faces of \(D\) with \(d\) and \(\theta d\) removed from their boundary walks, the order of the remaining darts being kept, and its outer face is the outer face of \(D\), shortened in this way.

Proof. The dual \(D^*=(\Delta,\theta,\sigma\theta)\) is a sphere map whose faces, the orbits of \((\sigma\theta)\theta=\sigma\), are the vertices of \(D\) (Lemma 2.1 of Sphere maps). As \(e\) is not a loop, \(d\) and \(\theta d\) lie in the two different faces \((d,x_1,\ldots,x_k)\) and \((\theta d,y_1,\ldots,y_l)\) of \(D^*\). By Proposition 2.1, applied to \(D^*\) with either face as outer face, \(D^*-e\) is a sphere map whose faces are the vertices of \(D\) other than \(u,v\), together with \((x_1,\ldots,x_k,y_1,\ldots,y_l)\).

Let \(\rho\) be the rotation of \(D^*-e\): it is \(\sigma\theta\) with \(d\) and \(\theta d\) skipped. For a remaining dart \(x\), \(\rho(\theta x)=\sigma(x)\) unless \(\sigma(x)\in\{d,\theta d\}\). If \(\sigma(x)=d\), then \(k\ge1\) and \(x=x_k\), and skipping gives \(\rho(\theta x_k)=y_1\), or \(x_1\) if \(l=0\). If \(\sigma(x)=\theta d\), then \(l\ge1\) and \(x=y_l\), and \(\rho(\theta y_l)=x_1\), or \(y_1\) if \(k=0\). So the rotation \(\rho\theta\) of the dual \((D^*-e)^*\) is the rotation of \(D/e\), and \(D/e=(D^*-e)^*\) is a sphere map. Its faces are the orbits of \((\rho\theta)\theta=\rho\), that is, the vertices of \(D^*-e\): the faces of \(D\) with \(d,\theta d\) skipped, in their order. The outer face of \(D\) contains a dart other than \(d,\theta d\) unless \(D\) is a single edge, and its shortened walk is declared outer. \(\square\)

3. Pendant edges, chords and loops

Proposition 3.1 (pendant edges). Let \((\alpha,\beta)\) be a corner of a face \(f\) of a plane map \(D\). Add an edge \(\{p,q\}\), where \(p\) leaves the head of \(\alpha\) and is placed after \(\theta\alpha\) in its rotation, and \(q\) leaves a new vertex of degree one: \[ \sigma'(\theta\alpha)=p,\quad\sigma'(p)=\beta,\quad\sigma'(q)=q . \] The result is a plane map whose faces are those of \(D\), except that the boundary walk of \(f\) becomes \((\ldots,\alpha,p,q,\beta,\ldots)\); the outer face stays outer. If \(D\) is trivial, the result is a single edge with the one face \((p,q)\).

Proof. \(\varphi'(\alpha)=\sigma'(\theta\alpha)=p\), \(\varphi'(p)=\sigma'(q)=q\) and \(\varphi'(q)=\sigma'(p)=\beta\); every other dart \(x\) has \(\theta x\notin\{\theta\alpha,p,q\}\), so \(\varphi'(x)=\varphi(x)\). The map is connected, and \(V\) and \(E\) both grow by one while the number of faces is unchanged, so \(\chi=2\). For the trivial map, \(\sigma'\) fixes \(p\) and \(q\) and \(\varphi'\) exchanges them (Example 1.3(a) of Sphere maps). \(\square\)

Proposition 3.2 (chords). Let \(\alpha_1\ne\alpha_2\) be darts of one face \(f\) of a plane map \(D\), with \(\beta_i=\varphi(\alpha_i)\), so that \[ f=(\beta_1,\ldots,\alpha_2,\beta_2,\ldots,\alpha_1). \] Add an edge \(\{g_1,g_2\}\), where \(g_i\) leaves the head of \(\alpha_i\) and is placed after \(\theta\alpha_i\): \(\sigma'(\theta\alpha_i)=g_i\) and \(\sigma'(g_i)=\beta_i\). The result is a plane map in which \(f\) is replaced by the two faces \[ (g_1,\beta_2,\ldots,\alpha_1),\qquad(g_2,\beta_1,\ldots,\alpha_2), \] each continuing along \(f\); the other faces are unchanged. If \(f\) is the outer face, either new face may be declared outer. The new edge is a loop when \(\alpha_1\) and \(\alpha_2\) enter the same vertex.

Proof. \(\varphi'(\alpha_i)=\sigma'(\theta\alpha_i)=g_i\), \(\varphi'(g_1)=\sigma'(g_2)=\beta_2\) and \(\varphi'(g_2)=\sigma'(g_1)=\beta_1\); all other values of \(\varphi\) are unchanged. Following \(\varphi'\) from \(g_1\) runs along \(f\) from \(\beta_2\) to \(\alpha_1\) and returns to \(g_1\); from \(g_2\) it runs from \(\beta_1\) to \(\alpha_2\). The vertices are unchanged, \(E\) and \(F\) both grow by one, and the map is connected, so \(\chi=2\). \(\square\)

Proposition 3.3 (loops in a corner). Let \((\alpha,\beta)\) be a corner of a face \(f\) of a plane map \(D\). Add a loop \(\{g_1,g_2\}\) at the head of \(\alpha\) with \[ \sigma'(\theta\alpha)=g_1,\quad\sigma'(g_1)=g_2,\quad\sigma'(g_2)=\beta . \] The result is a plane map in which the boundary walk of \(f\) becomes \((\ldots,\alpha,g_1,\beta,\ldots)\) and \((g_2)\) is a new face of length one; the other faces are unchanged, and the outer face stays outer. If \(D\) is trivial, the result is a single loop with the faces \((g_1)\) and \((g_2)\).

Proof. \(\varphi'(\alpha)=g_1\), \(\varphi'(g_1)=\sigma'(g_2)=\beta\) and \(\varphi'(g_2)=\sigma'(g_1)=g_2\). The vertices are unchanged and \(E\) and \(F\) grow by one. The trivial case is Example 1.3(b) of Sphere maps. \(\square\)

4. Cutting along a loop

A loop is a cycle of length one, so it has two sides (Theorem 3.2 of Sphere maps): the faces split into two nonempty classes such that an edge is the loop exactly when its darts lie on different sides.

Proposition 4.1 (cutting along a loop). Let \(g\) be a loop of a plane map \(D\) at the vertex \(x\), with the dart \(g\) in the outer face \(O\) and \(\theta g\) in another face. Let \(\mathcal A\) be the side of the loop containing \(O\), and \(K\) the set of edges both of whose darts lie in faces of \(\mathcal A\). Then \(K\) together with \(x\) is connected, and with the rotations restricted to its darts it is a plane map \(D_g\), the trivial map at \(x\) if \(K\) is empty. The outer face of \(D_g\) is the boundary walk of \(O\) with \(g\) removed, the order of the other darts being kept, and the bounded faces of \(D_g\) are the faces of \(D\) in \(\mathcal A\) other than \(O\), with the same boundary walks.

Proof. Write \(\mathcal A'\) for the other side; it contains the face of \(\theta g\). An edge other than the loop has both darts on one side. Every dart \(t\ne g\) of \(O\) therefore lies on an edge of \(K\); in particular \(K\) is empty exactly when \(O=(g)\), and then \(D_g\) is the trivial map at \(x\), whose empty face is \(O\) without \(g\).

Connectedness. A vertex \(v\ne x\) at which an edge of \(K\) ends is not on the loop, so it is strictly inside one side (Lemma 3.4(a) of Sphere maps), and that side is \(\mathcal A\) because a dart of \(K\) leaving \(v\) has its face in \(\mathcal A\). A shortest path in \(D\) from \(v\) to \(x\) uses, before it reaches \(x\), only vertices strictly inside \(\mathcal A\) and edges with both darts in faces of \(\mathcal A\) (Lemma 3.4(b) there, as in the proof of Proposition 3.5 there). So \(K\) together with \(x\) is connected, and if \(K\) is not empty it is a sphere map with the restricted rotations (Section 4 of Sphere maps).

Regions. The edges outside \(K\) are the loop, whose darts lie in \(O\) and in a face of \(\mathcal A'\), and the edges with both darts in faces of \(\mathcal A'\). So a face of \(\mathcal A\) other than \(O\) is adjacent across an edge outside \(K\) to no face, and forms a region of \(K\) by itself. By Proposition 4.1 of Sphere maps, every region contains the face of a dart of \(K\), which lies in \(\mathcal A\); so every face of \(\mathcal A'\) is in the region of \(O\). The regions of \(K\) are therefore \(\{f\}\) for the faces \(f\ne O\) of \(\mathcal A\), and \(R_0=\{O\}\cup\mathcal A'\).

The faces of \(D_g\). By the same proposition, the face of \(K\) belonging to a region \(R\) consists of the darts of \(K\) whose face in \(D\) lies in \(R\), and the face permutation \(\varphi_K\) of \(K\) sends a dart \(t\) to the first dart of \(K\) among \(\sigma(\theta t),\sigma^2(\theta t),\ldots\). For a face \(f\ne O\) of \(\mathcal A\), all darts of \(f\) belong to \(K\), and \(\varphi(t)=\sigma(\theta t)\in f\) is already a dart of \(K\), so \(\varphi_K=\varphi\) on \(f\): the boundary walk is unchanged.

The face of \(R_0\) consists of the darts of \(O\) other than \(g\). For such a dart \(t\), if \(\varphi(t)\ne g\), then \(\varphi(t)\) is a dart of \(K\) and \(\varphi_K(t)=\varphi(t)\). Let \(t\) be the dart of \(O\) before \(g\), so that \(\sigma(\theta t)=g\). The rotation at \(x\) continues after \(g\) with \(\sigma(g),\sigma^2(g),\ldots\), up to \(\theta g\), and then \(\sigma(\theta g)=\varphi(g)\). The face of \(\sigma(g)=\varphi(\theta g)\) is the face of \(\theta g\), in \(\mathcal A'\). If \(y\ne\theta g\) is one of these darts with its face in \(\mathcal A'\), then its edge is not the loop, so the face of \(\theta y\) is in \(\mathcal A'\) too, and so is the face of \(\sigma(y)=\varphi(\theta y)\). Hence all the darts from \(\sigma(g)\) to \(\theta g\) have their faces in \(\mathcal A'\) and are not in \(K\); in particular \(\theta t\), whose face lies in \(\mathcal A\) because the edge of \(t\) is not the loop, is not among them, and \(\varphi_K(t)=\sigma(\theta g)=\varphi(g)\), the dart of \(O\) after \(g\). So the face of \(R_0\) is the boundary walk of \(O\) with \(g\) removed; it is the outer face of \(D_g\). \(\square\)

5. Exercises

5.1. Show that adding a chord (Proposition 3.2) and then deleting it (Proposition 2.1) gives back the original map.

5.2. Let \(D\) be a plane map whose bounded faces all have length at least three and whose outer face has length \(m\). Show that \(E\le3V-3-m\).

5.3. Let \(D\) be the cycle of length \(n\ge2\) with the rotations \((\theta d_{i-1},d_i)\) at its vertices, where \(d_i\) runs from the \(i\)-th vertex to the next, indices modulo \(n\). Find its two faces, and the faces of \(D/e\) for an edge \(e\) of the cycle.

5.4. In Proposition 4.1, express the number of vertices of \(D_g\) through the number of vertices of \(D\) strictly inside \(\mathcal A\), and check \(\chi(D_g)=2\) with Proposition 3.5 of Sphere maps.

6. Solutions

5.1. The chord \(\{g_1,g_2\}\) has its darts in the two different faces \((g_1,\beta_2,\ldots,\alpha_1)\) and \((g_2,\beta_1,\ldots,\alpha_2)\). Deleting it skips \(g_1\) and \(g_2\) in the rotation, which restores \(\sigma(\theta\alpha_i)=\beta_i\), and by Proposition 2.1 the two faces merge into \((\beta_2,\ldots,\alpha_1,\beta_1,\ldots,\alpha_2)\), which is \(f\) read from \(\beta_2\).

5.2. The lengths of all boundary walks add up to \(2E\) (Proposition 1.2(1)), so \(2E\ge m+3F\). With \(F=1-V+E\) from Proposition 1.2(3) this gives \(2E\ge m+3-3V+3E\), that is, \(E\le3V-3-m\).

5.3. \(\varphi(d_i)=\sigma(\theta d_i)=d_{i+1}\), so \((d_1,\ldots,d_n)\) is one face, and \(\varphi(\theta d_i)=\sigma(d_i)=\theta d_{i-1}\), so \((\theta d_n,\ldots,\theta d_1)\) is the other; \(\chi=n-n+2=2\). Contracting \(e=\{d_n,\theta d_n\}\) merges its two ends and leaves the faces \((d_1,\ldots,d_{n-1})\) and \((\theta d_{n-1},\ldots,\theta d_1)\): the cycle of length \(n-1\), or for \(n=2\) a single loop.

5.4. By Lemma 3.4 of Sphere maps, the vertices of \(D_g\) other than \(x\) are the \(I\) vertices strictly inside \(\mathcal A\), and the edges of \(D_g\) are the \(E_{\mathcal A}\) edges with both darts in faces of \(\mathcal A\). The faces of \(D_g\) correspond to \(\mathcal A\). So \(\chi(D_g)=(I+1)-E_{\mathcal A}+|\mathcal A|\), which equals \(2\) because \(I-E_{\mathcal A}+|\mathcal A|=1\) by Proposition 3.5 there, applied to the cycle formed by the loop.

References