{'fraction_non_alphanumeric': 0.07087596705764912, 'fraction_numerical': 0.021743199401048165, 'mean_word_length': 3.1959424083769634, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 21, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Revisiting a Nice Cycle Lemma and its Consequences

We correct some errors and omissions primarily in a paper [Albertson&Hutchinson2004], discovered by R.B. Richter, and also some in a proof of [Thomassen1993] and of [Yu1997]. We give a short proof of Thomassen's theorem that every triangulation of a surface with all noncontractible cycles sufficiently long can be 5-colored; part of the shortness is due to the use of the Four Color Theorem, which is not used in Thomassen's original proof.


Introduction
In this paper let G, a simple graph, always have a 2-cell triangulation embedding Π of a nonplanar surface Σ, and suppose the embedding has width w (G, Π ), the length of the shortest noncontractible cycle in G, to be determined when and as needed. Such an embedded graph is called locally planar when the width is sufficiently large (for the problem at hand.) We prove Thomassen's theorem that locally planar graphs are 5-colorable; it is also known that locally planar graphs are 5-choosable by a much more complex proof [DKM08]. Our proof is shorter than that of [T93] due to the introduction of the idea of nice cycles in embedded graphs and the use of the Four Color Theorem [ApHa76,RSST97].

Planarizing cycles, background and new definitions
In this paper let the length of a path (or cycle) of a graph G be the number of edges. For P a path, we denote its length by &(P) and set P = V(P) .
If U ⊂ V (G), set N 0 (U) = U, and let N 1 (U) = N(U) denote the set of vertices that are not in U but are adjacent to at least one vertex in U. Inductively for i ≥ 1 N i (U) denotes the set of vertices that are in neither N i*1 (U) nor (when i ≥ 2) in N i*2 (U), but are adjacent to at least one vertex of N i*1 (U). Thus N i (U) consists of those vertices of G whose distance from U is exactly i.
Given a traversal of C, a 2-sided (or orientation preserving) cycle within G with triangulation embedding Π, we define R (C) and L (C), respectively, the (not necessarily disjoint) right and left neighbors of C. R (C) (resp., L (C)) is the set of vertices of N (C) that are adjacent to C along an edge emanating from the right (resp., left) side of C. We may also say that the edges joining a vertex of C with one of R(C) (resp., L(C)) lie on the right (resp., left) of C. All separating cycles of G are 2-sided as are all noncontractible cycles when Σ is orientable. For i ≥ 1 we define R i (C) to be the vertices of N i (C) that can be reached by a shortest path starting in C with an edge to a vertex of R(C); we define L i (C) in an analogous way.
A nonorientable surface may also contain 1-sided (or orientation reversing) noncontractible, necessarily nonseparating, cycles. When C is 1-sided, we define R and L locally along M, a subpath of m ≥ 1 edges of C when C has length k ≥ 2 m. On a traversal of M ⊂ C there are (not necessarily disjoint) right neighbors R (M) and left neighbors L (M), both subsets of N (C). Formally R (M) = {y ∈ N(C) : there is a vertex x ∈ M and an edge xy lying on the right side of M in the traversal}. We may say that locally edge A nonorientable surface may also contain 1-sided (or orientation reversing) noncontractible, necessarily nonseparating, cycles. When C is 1-sided, we define R and L locally along M, a subpath of m ≥ 1 edges of C when C has length k ≥ 2 m. On a traversal of M ⊂ C there are (not necessarily disjoint) right neighbors R (M) and left neighbors L (M), both subsets of N (C). Formally R (M) = {y ∈ N(C) : there is a vertex x ∈ M and an edge xy lying on the right side of M in the traversal}. We may say that locally edge xy lies on the right of C. L (M) is defined in the same manner.
(Since in the following we consider only chordless noncontractible cycles, we need not be concerned whether cycle-chords lie to the left or to the right of a noncontractible cycle.) For M a subpath of chordless cycle C (when C is 1-or 2-sided) and for a vertex x ∈ M, we define R (x) to be its right neighbors with respect to a traversal of M, and deg R (x) = R(x) is called the right degree of x. We make the analogous definition for the left degree.
By cutting along a chordless, noncontractible cycle C, we mean the following transformation of G and its 2-cell embedding Π on a surface Σ of Euler genus g > 0. If C is 2-sided, we retain two copies of C, called C' and C. Given an orientation of the original C, we connect every vertex of C' to vertices of R (C) by edges lying on the right side of C, and we connect every vertex of C to L (C) by edges lying on the left side C. When C = {x 1 , ..., x k } is 1-sided, we replace C by C' a cycle of 2 k vertices {x 1 , ..., x k , x' 1 , ..., x' k }, with each vertex x i replaced by two copies, x i and x' i , so that, for i = 1, ... k, x i is adjacent to each vertex of L(x i ), with L locally defined, and each x' i is adjacent to each vertex of R(x i ), locally defined. Since (as assumed) Π is a triangulation of Σ, we think of sewing in a disk (or two) to span C' (and C), we add a vertex x' adjacent to every vertex of C' and (when C is 2-sided) add a vertex x adjacent to every vertex of C. This graph is denoted G' with a 2-cell triangulation embedding Π', embeded on a surface (or the union of two surfaces) Σ'. When C is 1-sided, then the genus of Σ' is g * 1. When C is 2-sided and nonseparating, then the genus of Σ' is g * 2. Otherwise when C is 2-sided and separating, Σ' is the union of two surfaces with genus defined to be the maximum of the two genera, which sum to g. Similarly w (G', Π') is defined to be the minimum of the width of the graph on the two surfaces. (See [T93,MT01].) Lemma 1 [T93, Y97]. Suppose G, Π is a triangulation embedding on Σ of Euler genus g > 0. If C is a shortest noncontractible cycle, then C is chordless. In addition if cutting along C gives triangulation G', Π' on Σ', then w(G', Π') ≥ w(G, Π)/2. The next distance parameter for 2-sided cycles is alluded to in [T93].
Definition. If C is a 2-sided, chordless, noncontractible cycle in an embedded graph G, let ctdist G (C) (or ctdist(C) when the graph context is clear) denote the length of a shortest path (or cycle) beginning with an edge to a vertex on one side of C and ending with an edge on the other side of C. If there is no such path, declare ctdist(C) to be infinite.
Note that if C is a 2-sided, chordless, noncontractible cycle in G, Π, and P is a path that defines ctdist G (C), then when P is a cycle, it is necessarily noncontractible. When P begins at x ∈ C and ends at y ∈ C, x ≠ y, then both P ⋃ C x,y and P ⋃ C y,x are necessarily noncontractible where we define C x,y to be the shorter subpath of C joining x and y and C y,x the longer such subpath; see [T93]. We could define ctdist(C) for C 1-sided also, but then the latter property need not hold. Instead we focus on a variation of this distance parameter.
Definition. Let C be a chordless, noncontractible cycle in G, Π. Let ncdist G (C) (or ncdist (C) when the graph context is clear) denote the length of a shortest path P that begins at x ∈ C and ends at y ∈ C such that when x ≠ y P ⋃ C x,y and P ⋃ C y,x are both noncontractible or when x = y P is noncontractible. If there is no such path, declare ncdist (C) to be infinite.
Note that for C 2-sided, ncdist (C) ≤ ctdist (C). When G is embedded on the torus, ncdist = ctdist. For other surfaces a path P that gives ncdist may begin and end on the same side of C so that possibly ncdist < ctdist.
Note that for C 2-sided, ncdist (C) ≤ ctdist (C). When G is embedded on the torus, ncdist = ctdist. For other surfaces a path P that gives ncdist may begin and end on the same side of C so that possibly ncdist < ctdist. Proposition 1. Suppose C is a shortest noncontractible cycle in an embedded graph G, Π of width w (G, Π). Then ncdist(C) ≥ w (G, Π)/2.
Proof. By Lemma 1, C is chordless. Let P be a path (or cycle) defining ncdist(C). If P begins and ends at the same vertex, then the cycle P is noncontractible, and &(P) ≥ w(G, Π). Otherwise if P begins at x ∈ C and ends at y ∈ C, y ≠ x, let C x,y denote the shorter subpath of C from x to y. Since &(C x,y ) ≤ w(G, Π)/2, and the noncontractible cycle P ⋃ C x,y has length at least w(G, Π), we have &(P) ≥ w(G, Π)/2. QED When C is a contractible cycle in G, Π, we denote by Int(C) the subgraph contained within its interior together with C.
Lemma 2 [M92, T93, Y97]. For k ≥ 1, let Π be a triangulation embedding of G on Σ of Euler genus g ≥ 1 with w(G, Π) ≥ 2 k + 2. Let x 5 V(G). Then G has a unique chordless Π-contractible cycle D with x in its interior such that every vertex of D has distance k from x, and for each z 5 D there is a path in Int (D) of length k from x to z.
denote the induced subgraph on the vertices of X. Then the cycle D of Lemma 2, called the k-th canonical cycle of x in G, is a subgraph of GN k (x).
Corollary 1. For k ≥ 1, let Π be a triangulation embedding of G on Σ of Euler genus g ≥ 1 with w(G, Π) ≥ 2 k + 2. After cutting along a 2-sided, chordless, noncontractible cycle C, let the resulting triangulation be G' with triangulation Π' on Σ' with added vertices x' and x. Then if D' is the k-th canonical cycle of x' in G' and D the k-th canonical cycle of x in G', then Int (D') and Int (D) are disjoint and D' and D are joined by no edge. In particular R k (C) ⋂ L k (C) = ∅ and no edge joins R k (C) with L k (C).
Proposition 2. For k ≥ 1, let Π be a triangulation embedding of G on Σ of Euler genus g ≥ 1 with w(G, Π) ≥ 2 k + 4. Let C be a 1-sided, chordless, noncontractible cycle C, and let M be a subpath of C with at most m ≤ C /2 edges. If P is a path starting from a vertex x ∈ M on an edge to R (M) and ending at y ∈ M on an edge from L (M), then &(P) ≥ C /2. In particular R k/2 (M) ⋂ L k/2 (M) = ∅ and no edge joins R k/2 (M) with L k/2 (M).
Proof. Let C x,y denote the shorter subpath of C between x and y and C y,x the longer. At least one of P ⋃ C x,y and P ⋃ C y,x is noncontractible, and C x,y ⊆ M. If P ⋃ C x,y is noncontractible, then as argued in the proof of Prop. 1, &(P) ≥ C /2. Then since &(P) ≥ k + 2, R k/2 (M) and L k/2 (M) are disjoint and joined by no edge. Otherwise P ⋃ C x,y is contractible so that P begins and ends with two edges on the same side of C x,y , a contradiction. QED is the length of a shortest path joining these two cycles.
We (the second two authors) reprove the following theorem to encorporate part (iii) (and to correct some errors and omissions in earlier proofs.) Theorem 1 (See also [T93, Y97, MT01, AH04]). For d ≥ 1, let Π be a 2-cell triangulation embedding of a simple graph G on a surface Σ of Euler genus g ≥ 1. Suppose w (G, Π) ≥ 8 (d + 1) 2 g/2 * 1 when Σ is orientable and w (G, Π) ≥ 8 (d + 1) (2 g * 1) otherwise. Then G contains a planarizing set of cycles S 1 , S 2 , ..., S k with k = g/2 when Σ is orientable and with g/2 ≤ k ≤ g otherwise, such that In [Yu97] the bound on k is not given in the nonorientable case, but from the proof one can easily derive g/2 ≤ k ≤ 2 g * 1. A modification as in [T93] and the proof below gives g/2 ≤ k ≤ g. The related theorem in [Y97, Thm. 4.3] claims to prove more; instead we derive (iii) from Prop. 1, correcting a small flaw in the proofs of [T93, Y97].
In [Yu97] the bound on k is not given in the nonorientable case, but from the proof one can easily derive g/2 ≤ k ≤ 2 g * 1. A modification as in [T93] and the proof below gives g/2 ≤ k ≤ g. The related theorem in [Y97,Thm. 4.3] claims to prove more; instead we derive (iii) from Prop. 1, correcting a small flaw in the proofs of [T93, Y97].
Proof. The goal is to find a set of planarizing cycles {C 1 , ..., C k } with k = g/2 when Σ is orientable and with g/2 ≤ k ≤ g when Σ is nonorientable, with the properties stated in this theorem. We have for Σ orientable and g ≥ 2, w (G, Π) ≥ 8 (d + 1) 2 g/2 * 1 ≥ 8 (d + 1), and for Σ' nonorientable and g ≥ 1, In all cases, let C be a shortest noncontractible cycle in the embedded graph G; C is necessarily chordless by Lemma 1. By Prop. 1, ncdist (C) ≥ 4 (d + 1) in all cases.
We cut along C, as chosen above, to create G' with triangulation Π' on Σ'. By Lemma 1, we have The proof is by induction on the Euler genus g ≥ 1, and the inductive hypothesis will be applied to the graph G 0 with embedding Π 0 on Σ', defined below.
First suppose that C is 2-sided and Σ' is the sphere. Then g = 2, Σ is either the torus or the Klein bottle, and we set C 1 = C. We have in both cases a planarizing set of one cycle C 1 = C (k = g/2) for which ncdist(C 1 ) ≥ 4 (d + 1).
Next suppose that C is 1-sided and Σ' is the sphere so that g = 1, Σ is the projective plane, and we set C 1 = C. Again we have a planarizing set of one cycle C 1 (k = g) for which ncdist(C 1 ) ≥ 4 (d + 1).
Thus we assume that after cutting along C in G on Σ, we obtain G' on Σ' which is not the sphere so that either Σ is the Klein bottle with g = 2 and cutting along C leaves either one or two projective planes, or else g ≥ 3. With the bounds in (*), we have w(G', Π') ≥ 12 (d + 1) in all these cases. Then we consider the canonical cycles at when C is 2-sided, the cycles D' and D are disjoint and are joined by no edge. When C is 1 * sided, by Prop. 2 D' is chordless. We delete the interior of D' that contains x' in G' (and the interior of D that contains x in G') and add a vertex y' adjacent to all vertices of D' (and add vertex y adjacent to all vertices of D) to form G 0 with triangulation Π 0 on Σ'. Now the proof will proceed by induction on the Euler genus g ≥ 2. Since as shown in [T93, Y97] and using the inequalities in (*), When C is nonseparating, we set C 1 = C, we look for a planarizing set for G 0 on Σ', and we add C 1 to that set; when C is separating, we don't use C in the final planarizing set. Specifically, if C is 2sided and nonseparating, Σ' has Euler genus g * 2, and by induction we get a planarizing set {C 2 , ..., C k } for G 0 on Σ' with (g * 2)/2 ≤ k * 1 ≤ g * 2 so that {C 1 , ..., C k } satisfies g/2 ≤ k ≤ g * 1 < g. And when Σ and thus Σ' are orientable, we get k = g/2. Similarly when C is 1-sided (so necessarily nonseparating and Σ is nonorientable), Σ' has Euler genus g * 1. By induction we get a planarizing set {C 2 , ..., C k } for G 0 on Σ' with (g * 1)/2 ≤ k * 1 ≤ g * 1 so that {C 1 , ..., C k } satisfies g/2 < (g + 1)/2 ≤ k ≤ g. In both cases when C is nonseparating we have that the cycles {C 1 , ..., C k } are all chordless. By induc- When C is separating and necessarily 2-sided, we have G 0 = G 1 ⋃ G 2 , G i on surface Σ i of Euler genus g i ≤ g * 1, i = 1, 2, with g 1 + g 2 = g; also w(G i , Σ') ≥ w(G 0 , Σ') ≥ 8 (d + 1), i = 1, 2. By induction we get a planarizing set {C 1 , ..., C m } for G 1 , g 1 /2 ≤ m ≤ g 1 with m = g 1 /2 when Σ 1 is orientable, and a planarizing set {C m+1 , ..., C k } for G 2 , g 2 /2 ≤ k * m ≤ g 2 with k * m = g 2 /2 when Σ 2 is orientable. Thus the planarizing set for G {C 1 , ..., C k } has size bounded by g/2 ≤ k ≤ g, and since Σ is orientable if and only if Σ 1 and Σ 2 are, then k = g/2. These cycles are all chordless and satisfy dist G1 When C is separating and necessarily 2-sided, we have G 0 = G 1 ⋃ G 2 , G i on surface Σ i of Euler genus g i ≤ g * 1, i = 1, 2, with g 1 + g 2 = g; also w(G i , Σ') ≥ w(G 0 , Σ') ≥ 8 (d + 1), i = 1, 2. By induction we get a planarizing set {C 1 , ..., C m } for G 1 , g 1 /2 ≤ m ≤ g 1 with m = g 1 /2 when Σ 1 is orientable, and a planarizing set {C m+1 , ..., C k } for G 2 , g 2 /2 ≤ k * m ≤ g 2 with k * m = g 2 /2 when Σ 2 is orientable. Thus the planarizing set for G {C 1 , ..., C k } has size bounded by g/2 ≤ k ≤ g, and since Σ is orientable if and only if Σ 1 and Σ 2 are, then k = g/2. These cycles are all chordless and satisfy dist G1 In all cases we must still check that the distances in G satisfy (ii) and (iii).
We show that the desired planarizing set is {C 1 , ..., C k }, g/2 ≤ k ≤ g, when no C i contains y or y'. On the other hand when, say, C i' contains y', we modify C i' , as follows [T93, Y97]. Namely, if C i' contains the subpath uy' v in G 0 with u, v ∈ D', then we replace this subpath with a shortest path in G of the form u, y 1 , ..., y r , v with y 1 , ..., y r a subpath of E ', all vertices at distance one from D'. We do the same when C j' contains y (possibly j' = i'). With these choices the cycles C i' and C j' remain chordless (since E ', E, C i' , and C j' are chordless and the subpath is chosen to be shortest). The distance between cycles C j and C j ? , 1 ≤ j < j ? ≤ k, given by induction on G i , i = 0, 1, 2, remains at least d on G except possibly when a shortest path joining them passes through y or y'. It is a routine check to see that the length of such a shortest path cannot decrease in G. Due to the construction of G 0 (when C is nonseparating), Due to the construction of G 1 and G 2 (when C is separating), the distance between a cycle on G 1 and one on G 2 is at least 2 d. Thus (ii) holds. As noted above when C is nonseparating, ncdist G (C 1 ) ≥ 4 (d + 1). Also for 1 ≤ j ≤ k if P is a path giving ncdist Gi (C j ) by induction for i = 0, 1, 2, then the minimum length given by &(P) is not affected unless P passes through y' or y. Again in G a longer alternate path must be found or else the ncdist-defining path itself does not decrease in length when modified or replaced to become an ncdist-defining path in G. Thus (iii) also holds. QED

The nice cycle lemma
The driving force behind our results and many of their predecessors is the nice cycle lemma. This says that if C is a noncontractible cycle in an "orderly" triangulation (defined below), then there is a chordless cycle C' that is near to C, homotopic to C, and particularly nice from the point of view of 5coloring. A chordless noncontractible cycle C in an embedded graph is said to be nice if it either has even length or contains a vertex of degree at most 4. The first published version of a nice cycle lemma appeared in [AS82]. There the cycle C had to be a minimum length noncontractible cycle in an orderly triangulation of the torus, and the cycle C' was found in the first neighborhood of C. Stromquist established a nice cycle lemma for an arbitrary surface where C' was found in the "filled first neighborhood" of C [S77], but this was never published. The filled first neighborhood might contain vertices arbitrarily far from C. Thomassen constructed a nice cycle in [T93]; however, to obtain his version of C' he used the notion of weak geodesic, requiring a considerable detour away from C. Using local modifications he found his nice cycle on one side of C, but, as we now know, finding a nice cycle requires zigzagging to both sides of C. We sketch the argument at the end of this section. Finally we need a nice cycle lemma for both nonorientable and orientable surfaces; a subtle flaw was found by the third author in the proof of [AH04].
As in [AH04] we introduce "optimal k-shortcuts" and use this idea to give a proof of the lemma. Our result also has the advantage that all vertices of C' are within distance four of the original C.

If G, Π is a triangulation of the surface Σ and U ⊂ V(G), G[U] is said to be orderly if every contractible 3-cycle in G[U] bounds a face of G and if every contractible 4-cycle in G[U]
is either the boundary of two triangles of G that share an edge or the first neighbor circuit of a vertex of degree 4 in G.
Orderly graphs have been helpful in inductive proofs of 5-coloring theorems for embedded graphs [AS82,H84].
Suppose C = u 1 , u 2 , ..., u t , t > 6, is a chordless, noncontractible cycle in a graph embedded on a surface Σ of Euler genus g > 0. A path of length 6, say v 1 , v 2 , ..., v 7 , is said to be an optimal 6-shortcut for C if v 1 = u i for some i, v 7 = u j for some j, the resulting noncontractible cycle .., u t is homotopic to C, and C' is as short as possible. (Note that by renumbering, if the shortcut goes the "other" way and includes u 1 in its bypass, by relabeling we can assume the shortcut is as above.) Equivalent to the first condition, the cycle u i , u i+1 , ..., u j , v 6 , v 5 , ..., v 2 , u i is contractible. By Thomassen's 3-path-property [T93, Prop. 4.3.1], one Suppose C = u 1 , u 2 , ..., u t , t > 6, is a chordless, noncontractible cycle in a graph embedded on a surface Σ of Euler genus g > 0. A path of length 6, say v 1 , v 2 , ..., v 7 , is said to be an optimal 6-shortcut for C if v 1 = u i for some i, v 7 = u j for some j, the resulting noncontractible cycle C' = u 1 , ..., {u i = v 1 }, v 2 , ..., v 6 , {v 7 = u j }, u j+1 , ..., u t is homotopic to C, and C' is as short as possible. (Note that by renumbering, if the shortcut goes the "other" way and includes u 1 in its bypass, by relabeling we can assume the shortcut is as above.) Equivalent to the first condition, the cycle u i , u i+1 , ..., u j , v 6 , v 5 , ..., v 2 , u i is contractible. By Thomassen's 3-path-property [T93,Prop. 4.3.1], one subpath of C between u i and u j together with the 6-shortcut is a noncontractible cycle; without loss of generality that cycle is C'. Note that v 2 ...., v 6 may be vertices of C, that possibly C' = C, and that when C' ≠ C, C' might not be chordless.
Let C be a noncontractible cycle in an embedded graph and K a chord of C. We say K is a contractible chord if K together with one subpath of C between the endpoints of K is contractible; otherwise K is called a noncontractible chord. We prove a variation on the nice cycle lemma of [AH04], correcting an error in the proof there.
We claim that C' has no chord also when C' ≠ C. Suppose K were a chord of C'. Since C is chordless, at least one endpoint of K is not in C and therefore is in M. If K is contractible, then M is not an optimal shortcut, as C' can be shortened; therefore we may assume K is noncontractible.
Using M to join the endpoints of K to C by disjoint paths, we get a path P of length at most 7 joining two vertices of C. Since K is noncontractible for C', none of the cycles in C ⋃ P is contractible, showing that ncdist(C) ≤ 7, contradicting the fact that ncdist(C) ≥ 12.
We also claim that ncdist(C') ≥ 4 d when C' ≠ C. Let P be a path defining ncdist(C'); if it is a cycle then ncdist(C') ≥ w(G, Π) ≥ 8 (d + 1). If P joins two vertices of C'\M, then &(P) ≥ 4 (d + 1). Otherwise P joins two vertices of M or a vertex of M with one in C'\M, and P together with each subpath of C' is noncontractible. Then P plus at most 4 edges is either a noncontractible cycle or forms two noncontractible cycles with subpaths of C, and we conclude that &(P) + 4 ≥ ncdist(C) ≥ 4 (d + 1) so that &(P) ≥ 4 d.
Since w(G, Π) ≥ 8 (d + 1) (2 g * 1) ≥ 24, R 4 (M) ⋂ L 4 (M) = ∅ by Cor. 1 and Prop. 2, and no edge joins R 4 (M) with L 4 (M). We may assume that both C and C' have odd length and contain no vertex of degree at most 4. Thus both t ( = C ) and i * 1 + 7 + t * j ( = C' ) are odd. If D denotes the subpath of C' from u j+1 to u i*1 inclusive, then D = i * 1 + t * j contains an even number of vertices.
Case (i): Suppose deg R (v 3 ) ≥ 2 and deg R (v 4 ) ≥ 2. Let x denote the vertex that is in a triangle to the right of the edge joining v 3 with v 4 . Suppose v 1 , A, x is a shortest path from v 1 to x among the vertices in N(v 3 ) (with A not including either endpoint). Normally A includes v 2 but that is not necessary. Next let x, B, v 6 be a shortest path from x to v 6 among the neighbors of v 4 (with B not including either endpoint.) Normally B includes v 5 but that is not necessary. Note that v 4 or x might be at distance 3 from C and perhaps a neighbor of v 4 is at distance 4 from C. Otherwise all vertices are at distance 3 or less from C. Case (i): Suppose deg R (v 3 ) ≥ 2 and deg R (v 4 ) ≥ 2. Let x denote the vertex that is in a triangle to the right of the edge joining v 3 with v 4 . Suppose v 1 , A, x is a shortest path from v 1 to x among the vertices in N(v 3 ) (with A not including either endpoint). Normally A includes v 2 but that is not necessary. Next let x, B, v 6 be a shortest path from x to v 6 among the neighbors of v 4 (with B not including either endpoint.) Normally B includes v 5 but that is not necessary. Note that v 4 or x might be at distance 3 from C and perhaps a neighbor of v 4 is at distance 4 from C. Otherwise all vertices are at distance 3 or less from C.
Let's examine the possible chords for C (2) . From the latter inequality we see that a noncontractible chord, with one end in A or at x plus at most two edges, joins two vertices of C', a contradiction. And if there were a contractible chord from D to a vertex in the subpath A, x, v 4 , v 5 , v 6 , then we didn't select our optimal 6-shortcut correctly. This is also the case if there were a contractible chord from A to either v 6 or v 7 . If there were a contractible chord from A to v 4 , then G C,4 contains a contractible 3-cycle that is not a face boundary. If there were a contractible chord from A to v 5 , then we have a contractible 4-cycle, say a, v 3 , v 4 , v 5 , with x in its interior for some a ∈ A. If x is adjacent to v 5 and deg (x) = 4, then D, v 1 , v 2 , v 3 , x, v 5 , v 6 , v 7 is nice. If x is not adjacent to v 5 or deg (x) ≠ 4, then G C,4 contains a forbidden contractible 4-cycle. Thus either the number of vertices in A, A , is odd or we are done since C (2) would be nice.
Next consider the cycle C (3) = D, v 1 , v 2 , v 3 , x, B, v 6 , v 7 with all vertices at distance at most 4 from C and at distance at most 1 from C'. As in the preceding paragraph either B is odd or we are done since C (3) would be nice. Finally, look at C (4) = D, v 1 , A, x, B, v 6 , v 7 . C (4) is homotopic to C' and C (4) is even. The only chord we have not considered is an edge from A to B. If there were a noncontractible chord joining A and B, then the chord plus two edges gives ncdist(C') ≤ 3, a contradiction. If there were a contractible chord joining A and B, then it produces a forbidden contractible 4-cycle. In addition we have, for i = 3, 4, ncdistC (i)  ≥ 4 d * 2 since if P is a defining path for ncdistC (i) , then either &(P) ≥ 4 d or Case (iii). Suppose on C' we have deg R (v 3 ) ≥ 2, and deg R (v 4 ) < 2. As in Case (ii) we may assume deg R (v 4 ) = 1. If deg R (v 5 ) ≤ 1, then v 1 , ..., v 7 is not an optimal 6-shortcut so that we have deg R (v 5 ) ≥ 2. Now deg L (v 4 ) ≥ 2 since otherwise C' is not an optimal 6-shortcut or else it has a vertex of degree 4 and is nice. Similarly and by Case (i) we must have deg L (v 3 ) = deg L (v 5 ) = 1. Then by reversing the direction of the 6-shortcut we are in Case (ii) again.
Thus in each case we find the nice cycle C' within G C,4 with ncdist(C') ≥ 4 d * 2. Each nice cycle is no more than four edges away from its original planarizing cycle. Thus for X outside of G C,4 dist (X, C') ≥ dist (X, C) * 4. QED A closer reading of the proof shows that the results hold with d ≥ 2 when g = 1 and d ≥ 1 otherwise. Also we note that when Σ is orientable, the Nice Cycle Lemma holds when w (G, Π) ≥ 8 (d + 1) 2 g/2 * 1 and d ≥ 2, but for simplicity we assume uniform bounds.
We digress a moment to describe how to construct a noncontractible cycle C in a graph embedded in a nonorientable surface with the property that a nearby nice cycle must use both sides of C. Let C consist of vertices whose right degrees are alternately 1 and 3. It is easy to build such a cycle in a 6regular triangulation of a Klein bottle, and from there it can be on any nonorientable surface. For such a cycle, there is no nice replacement cycle lying locally on one side of C. Thus when C has odd length and is 1-sided, the nice cycle must be found using detours locally to both sides of C. AHRrevision4.10.16.nb We digress a moment to describe how to construct a noncontractible cycle C in a graph embedded in a nonorientable surface with the property that a nearby nice cycle must use both sides of C. Let C consist of vertices whose right degrees are alternately 1 and 3. It is easy to build such a cycle in a 6regular triangulation of a Klein bottle, and from there it can be on any nonorientable surface. For such a cycle, there is no nice replacement cycle lying locally on one side of C. Thus when C has odd length and is 1-sided, the nice cycle must be found using detours locally to both sides of C.

A 5-color theorem for locally planar graphs
A version of the next theorem for orientable surfaces appeared in [AH01]. There are several good reasons to have another look. First, the proof given below works for both orientable and nonorientable surfaces. Second, the particular nice cycle lemma needed in the earlier proof never appeared in print. Third the constants are better.
Proof. We apply Theorem 1 with d = 14 to get a planarizing set of cycles C 1 , C 2 , ..., C s , g/2 ≤ s ≤ g, with lower bounds on the distance between pairs of these cycles and on ncdist( First, for each i ≤ s we make the subgraph G Ci,4 (see Lemma 3). For i ≤ s these subgraphs are disjoint and joined by no edge by Cor. 1, Prop. 2, and Thm. 1 since d = 14. For each G Ci,4 we delete vertices of G interior to every contractible 3-cycle of G Ci,4 and, if there is more than one, all vertices interior to every contractible 4-cycle of G Ci,4 . In the latter case we add a vertex adjacent to all four boundary vertices. Call this intermediate graph G 1 . Then for 1 ≤ i ≤ s we apply Lemma 3 with C = C i and let C' i denote the resulting nice cycle, homotopic to C i , lying within G Ci,4 . This gives a new planarizing set {C' 1 , ..., C' s }.
By Lemma 3 we have dist(C' i , C' j ) ≥ d * 8 ≥ 6 for i ≠ j and ncdist(C' i ) ≥ 4 d * 2 ≥ 54 for 1 ≤ i ≤ s. With this planarizing set for G 1 we form a planar triangulation as follows (in a manner slightly different than "cutting" along these cycles). For each C' i that is 2-sided, 1 ≤ i ≤ s, we remove C' i and replace it with two vertices x i and y i . Then x i is made adjacent to each vertex of L(C' i ) and y i is adjacent to each vertex of R(C' i ). For C' i that is 1-sided, we remove C' i and replace it with x i adjacent all vertices in N(C' i ). (It does not matter that some multiple edges might be introduced.) The resulting graph G 0 is a plane triangulation with the distance between every pair of vertices from {x i , y i , x j , y j } at least d * 8 ≥ 6 for 1 ≤ i ≤ j ≤ s (and the same distance bounds hold when some y i or y j does not exist due to a 1-sided cycle.) Suppose c is a 4-coloring of G 0 using colors {1,2,3,4} [ApHa76,RSST97]. For each i ≤ s such that c(x i ) ≠ c(y i ), we recolor each vertex in N 2 (y i ) that is colored c(y i ) with color 5 and then at y i we perform a (c(x i ), c(y i ))-Kempe change so that y i gets the same color as x i . Since the distance between the pairs of {x i , x j , y i , y j }, i ≤ j, is at least 6, this recoloring is valid. Next we transfer this coloring back to G 1 . For each i for which C' i has even length, we 2-color C' i with {c(x i ), 5}, and for each C' i with a vertex v i of degree 4, we 2-color C' i with {c(x i ), 5} except for v i which is colored last with whatever color is available. Call this coloring of G 1 c 1 .
Then we add back and color the vertices deleted within contractible 3-and 4-cycles lying within G Ci,4 for each i ≤ s. Let C be a contractible 3-cycle in G Ci,4 with nonempty interior in G. Let H be the plane graph Int (C) . We can easily 4-color H so that it agrees with the coloring of C from G 1 .
Suppose C = u, v, x, y is a contractible 4-cycle within G Ci,4 that within G contains more than one interior vertex so that some interior vertices were deleted to form G 1 . Let H be the plane graph Int (C). We may assume that in the coloring of G 1 , c 1 (u) = 1 and c 1 (v) = 2.
Case (i). Suppose c 1 (x) = 1. We transform the plane graph H by identifying the vertices u and x within the outer face of H. If c 1 (y) = 2 (resp., 3), then we 4-color H using colors {1,3,4,5} (resp., {1,2,4,5}) making sure that u and x (resp., u, v, and x) are correctly colored.Then we assign color 2 to both v and y (resp., color 3 to y) for a coloring of H that agrees on the boundary with that of C in G 1 .