{'fraction_non_alphanumeric': 0.05102855388394228, 'fraction_numerical': 0.03150138163954559, 'mean_word_length': 3.3118877415938575, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Short proofs of coloring theorems on planar graphs

A recent lower bound on the number of edges in a k-critical n-vertex graph by Kostochka and Yancey yields a half-page proof of the celebrated Gr\"otzsch Theorem that every planar triangle-free graph is 3-colorable. In this paper we use the same bound to give short proofs of other known theorems on 3-coloring of planar graphs, among whose is the Gr\"unbaum-Aksenov Theorem that every planar with at most three triangles is 3-colorable. We also prove the new result that every graph obtained from a triangle-free planar graph by adding a vertex of degree at most four is 3-colorable.


Introduction
Graphs considered in this paper are simple, i.e., without loops or parallel edges. For a graph G, the set of its vertices is denoted by V (G) and the set of its edges by E(G).
An embedding σ of a graph G = (V, E) in a surface Σ is an injective mapping of V to a point set P in Σ and E to non-self-intersecting curves in Σ such that (a) for all v ∈ V and e ∈ E, σ(v) is never an interior point of σ(e), and σ(v) is an endpoint of σ(e) if and only if v is a vertex of e, and (b) for all e, h ∈ E, σ(h) and σ(e) can intersect only in vertices of P . A graph is planar if it has an embedding in the plane. A graph with its embedding in the (projective) plane is a (projective) plane graph. A cycle in a graph embedded in Σ is contractible if it splits Σ into two surfaces where one of them is homeomorphic to a disk.
A (proper) coloring ϕ of a graph G is a mapping from V (G) to a set of colors C such that ϕ(u) = ϕ(v) whenever uv ∈ E(G). A graph G is kcolorable if there exists a coloring of G using at most k colors. A graph G is k-critical if G is not (k − 1)-colorable but every proper subgraph of G is (k − 1)-colorable. By definition, if a graph G is not (k − 1)-colorable then it contains a k-critical subgraph.
Dirac [12] asked to determine the minimum number of edges in a kcritical graph. Ore conjectured [22] that an upper bound obtained from Hajós' construction is tight. More details about Ore's conjecture can be found in [18][ Problem 5.3] and in [20]. Recently, Kostochka and Yancey [20] confirmed Ore's conjecture for k = 4 and showed that the conjecture is tight in infinitely many cases for every k ≥ 5. In [19] they gave a 2.5-page proof of the case k = 4: Theorem 1 yields a half-page proof [19] of the celebrated Grötzsch Theorem [14] that every planar triangle-free graph is 3-colorable. This paper presents short proofs of some other theorems on 3-coloring of graphs close to planar. Most of these results are generalizations of Grötzsch Theorem.
Examples of such generalizations are results of Aksenov [2] and Jensen and Thomassen [17].
Theorem 2 ( [2,17]). Let G be a triangle-free planar graph and H be a graph such that G = H − h for some edge h of H. Then H is 3-colorable.
Theorem 3 ( [17]). Let G be a triangle-free planar graph and H be a graph such that G = H − v for some vertex v of degree 3. Then H is 3-colorable.
We show an alternative proof of Theorem 2 and give a strengthening of Theorem 3.
Theorem 4. Let G be a triangle-free planar graph and H be a graph such that G = H − v for some vertex v of degree 4. Then H is 3-colorable.
Theorems 2 and 4 yield a short proof of the following extension theorem that was used by Grötzsch [14].
Theorem 5. Let G be a triangle-free planar graph and F be a face of G of length at most 5. Then each 3-coloring of F can be extended to a 3-coloring of G.
An alternative statement of Theorem 2 is that each coloring of two vertices of a triangle-free planar graph G by two different colors can be extended to a 3-coloring of G. Aksenov et al. [3] extended Theorem 2 by showing that each proper coloring of each induced subgraph on two vertices of G extends to a 3-coloring of G. Theorem 6 ([3]). Let G be a triangle-free planar graph. Then each coloring of two non-adjacent vertices can be extended to a 3-coloring of G.
We show a short proof of Theorem 6. Another possibility to strengthen Grötzsch's Theorem is to allow at most three triangles. Theorem 7 ([1,4,15]). Let G be a planar graph containing at most three triangles. Then G is 3-colorable.
The original proof by Grünbaum [15] was incorrect and a correct proof was provided by Aksenov [1]. A simpler proof was given by Borodin [4], but our proof is significantly simpler.
Youngs [30] constructed triangle-free graphs in the projective plane that are not 3-colorable. Thomassen [25] showed that if G is embedded in the projective plane without contractible cycles of length at most 4 then G is 3-colorable. We slightly strengthen the result by allowing two contractible 4-cycles or one contractible 3-cycle.
Theorem 8. Let G be a graph embedded in the projective plane such that the embedding has at most two contractible cycles of length 4 or one contractible cycle of length three such that all other cycles of length at most 4 are noncontractible. Then G is 3-colorable.
It turned out that restricting the number of triangles is not necessary. Havel conjectured [16] that there exists a constant c such that if every pair of triangles in a planar graph G is at distance at least c then G is 3-colorable. The conjecture was proven true by Dvořák, Král' and Thomas [13].
Without restriction on triangles, Steinberg conjectured [23] that every planar graph without 4-and 5-cycles is 3-colorable. Erdős suggested to relax the conjecture and asked for the smallest k such that every planar graphs without cycles of length 4 to k is 3-colorable. The best known bound for k is 7 [9]. A cycle C is triangular if it is adjacent to a triangle other than C. In [6], it is proved that every planar graph without triangular cycles of length from 4 to 7 is 3-colorable, which implies all results in [7,8,9,10,11,21,26,27,28,29].
We present the following result in the direction towards Steinberg's conjecture with a Havel-type constraint on triangles. As a free bonus, the graph can be in the projective plane instead of the plane.
Theorem 9. Let G be a 4-chromatic projective planar graph where every vertex is in at most one triangle. Then G contains a cycle of length 4,5 or 6.
There are numerous other results on the Three Color Problem in the plane. See a recent survey [5] or a webpage maintained by Montassier http: //janela.lirmm.fr/~montassier/index.php?n=Site.ThreeColorProblem.
The next section contains proofs of the presented theorems and Section 3 contains constructions showing that some of the theorems are best possible.

Proofs
Identification of non-adjacent vertices u and v in a graph G results in a graph G obtained from G − {u, v} by adding a new vertex x adjacent to every vertex that is adjacent to at least one of u and v.
The following lemma is a well-known tool to reduce the number of 4-faces. We show its proof for the completeness.
If the number of triangles increases in both G 0 and G 1 then there exists a triangle v i v i+1 z for some z ∈ V (G) and i ∈ {0, 1, 2, 3}. Moreover, G contains vertices x and y not in F such that v i+1 zxv i−1 and v i zyv i+2 are paths in G. Indices are modulo 4. See Figure 1.
Proof. Let G, F, G 0 and G 1 be as in the statement of the lemma. Since the number of triangles increases in G 0 there must be a path v 0 zyv 2 in G where z, y ∈ F . Similarly, a new triangle in G 1 implies a path v 1 wxv 3 in G where w, x ∈ F . By the planarity of G, {z, y} and {w, x} are not disjoint. Without loss of generality assume z = w. This results in triangle v 0 v 1 z and paths v 1 zxv 3 and v 0 zyv 2 . Note that x and y do not have to be distinct. See Figure 1 Proof of Theorem 2. Let H be a smallest counterexample and G be a plane triangle-free graph such that G = H − h for some edge h = uv. Let H have n vertices and e edges and G have f faces. Note that G has n vertices and e − 1 edges. By the minimality of H, H is 4-critical. So Theorem 1 implies e ≥ 5n−2 3 . CASE 1: G has at most one 4-face. Then 5f − 1 ≤ 2(e − 1) and hence f ≤ (2e − 1)/5. By this and Euler's Formula n − (e − 1) + f = 2 applied on G we have 5n − 3e + 1 ≥ 5, i.e., e ≤ 5n−4 3 . This contradicts Theorem 1.
CASE 2: Every 4-face of G contains both u and v and there are at least two such 4-faces F x = ux 1 vx 2 and F y = uy 1 vy 2 . If there exists z ∈ {x 1 , x 2 } ∩ {y 1 , y 2 } then z has degree two in G which contradicts the 4-criticality of G.
Let G be obtained from G by identification of x 1 and x 2 into a new vertex x. If G is not triangle-free then there is a path P = x 1 q 1 q 2 x 2 in G where q 1 , q 2 ∈ F x . Since P must cross uy 1 v and uy 2 v, we may assume that y 1 = q 1 and y 2 = q 2 . However, y 1 y 2 ∈ E(G). This contradicts the existence of P . Hence G is triangle-free. Let H = G + h. By the minimality of H, there exists a 3-coloring ϕ of H . This contradicts that H is not 4-colorable since ϕ can be extended to H by letting ϕ( 3 . This contradicts Theorem 1. CASE 2: G has a 4-face F with vertices v 0 v 1 v 2 v 3 in the cyclic order. Since G is triangle-free, neither v 0 v 2 nor v 1 v 3 are edges of G and Lemma 10 applies. Without loss of generality assume that G 0 obtained from G by identification of v 0 and v 2 is triangle-free.
By the minimality of H, the graph obtained from H by identification of v 0 and v 2 satisfies the assumptions of the theorem and hence has a 3-coloring. Then H also has a 3-coloring, a contradiction.
Proof of Theorem 5. Let the 3-coloring of F be ϕ. By symmetry, the other subcase is the following. CASE 1.2: ϕ(v 0 ) = ϕ(v 2 ) and ϕ(v 1 ) = ϕ(v 3 ). Let G be obtained from G by adding the edge v 1 v 3 . Since G satisfies the assumptions of Theorem 2, there exists a 3-coloring of G . In any such 3-coloring, (v 1 ) = (v 3 ) and hence (v 0 ) = (v 2 ). By renaming the colors in we obtain an extension of ϕ to a 3-coloring of G. CASE 2: F is a 5-face where v 0 v 1 v 2 v 3 v 4 are its vertices in cyclic order. Observe that up to symmetry there is just one coloring of F . So without loss of generality assume that ϕ(v 0 ) = ϕ(v 2 ) and ϕ(v 1 ) = ϕ(v 3 ).
Let G be obtained from G by adding a vertex v adjacent to v 0 , v 1 , v 2 and v 3 . Since G satisfies the assumptions of Theorem 4, there exists a 3-coloring of G . Note that in any such 3-coloring (v 0 ) = (v 2 ) and (v 1 ) = (v 3 ). Hence by renaming the colors in we can extend ϕ to a 3-coloring of G.
Proof of Theorem 6. Let G be a smallest counterexample and let u, v ∈ V (G) be the two non-adjacent vertices colored by ϕ. If ϕ(u) = ϕ(v) then the result follows from Theorem 2 by considering graph obtained from G by adding the edge uv. Hence assume that ϕ(u) = ϕ(v). CASE 1: G has at most two 4-faces. Let H be a graph obtained from G by identification of u and v. Any 3-coloring of H yields a 3-coloring of G where u and v are colored the same. By this and the minimality of G we conclude that H is 4-critical. Let G have e edges, n + 1 vertices and f faces.
Without loss of generality let G 0 from Lemma 10 be triangle-free. By the minimality of G, G 0 has a 3-coloring ϕ where ϕ(u) = ϕ(v) unless uv ∈ E(G 0 ). Since uv ∈ E(G), without loss of generality v 0 = u and v 2 v ∈ E(G). Moreover, the same cannot happen to G 1 from Lemma 10, hence G 1 contains a triangle. Thus G contains a path v 1 q 1 q 2 v 3 where q 1 , q 2 ∈ F , and G also Figure 2: Configuration from Theorem 6. contains a 5-cycle C = uv 1 q 1 q 2 v 3 (see Figure 2). By Theorem 5, C is a 5-face.
Hence v is a 2-vertex incident with only one 4-face.
By symmetric argument, u is also a 2-vertex incident with one 4-face and 5-face. However, G has at least one more 4-face where identification of vertices does not result in the edge uv, a contradiction to the minimality of G.
Borodin used in his proof of Theorem 7 a technique called portionwise coloring. We avoid it and build the proof on the previous results arising from Theorem 1.
Proof of Theorem 7. Let G be a smallest counterexample. By minimality, G is 4-critical and every triangle is a face. By Theorem 5 for every separating 4-cycle and 5-cycle C, both the interior and exterior of C contain triangles. CASE 1: G has no 4-faces. Then 5f − 6 ≤ 2e and by Euler's Formula 3e + 6 + 5n − 5e ≥ 10, i.e., e ≤ 5n−4 3 . This contradicts Theorem 1. CASE 3.1: G contains a 3-prism with one of its 4-cycles being a 4-face. We may assume that this face is our F and x = y, see Figure 1(b). Theorem 5 implies that one of zv 0 v 3 x, zv 1 v 2 x is a 4-face. Without loss of generality assume that zv 1 v 2 x is a 4-face. Let G 0 be obtained from G by identification of v 0 and v 2 to a new vertex v. Since G 0 is not 3-colorable, it contains a 4-critical subgraph G 0 . Note that G 0 contains triangle xvz that is not in G but v 0 v 1 z is not in G 0 since d(v 1 ) = 2 in G 0 . By the minimality of G, there exists another triangle T that is in G 0 but not in G. By planarity, x ∈ T . Hence there is a vertex w 1 = v 3 such that v 0 and x are neighbors of w 1 .
By considering identification of v 1 and v 3 and by symmetry, we may assume that there is a vertex w 2 = v 0 such that v 3 and z are neighbors of w 2 . By planarity we conclude that w 1 = w 2 . This contradicts the fact that G has at most three triangles. Therefore G is 3-prism-free. CASE 3.2: G contains no 3-prism with one of its 4-cycles being a 4-face. Then x = y, see Figure 1(a). If v 0 x ∈ E(G) then G − v 0 is triangle-free and Theorem 3 gives a 3-coloring of G, a contradiction. Similarly, v 1 y ∈ E(G).
Suppose that zv 0 v 3 x if a 4-face. Let G be obtained from G−v 0 by adding edge xv 1 . If the number of triangles in G is at most three, then G has a 3-coloring ϕ by the minimality of G. Let be a 3-coloring of G such that . Since the neighbors of v 0 in G are neighbors of x in G , is a 3-coloring, a contradiction. Therefore G has at least four triangles and hence G contains a vertex t = z adjacent to v 1 and x. Since v 1 y ∈ E(G), the only possibility is t = v 2 . Having edge xv 2 results in a 3-prism being a subgraph of G which is already excluded. Hence zv 0 v 3 x is not a face and by symmetry zv 1 v 2 y is not a face either.
Since neither zv 0 v 3 x nor zv 1 v 2 y is a face, each of them contains a triangle in its interior. Since we know the location of all three triangles, Theorem 5 implies that zyv 2 v 3 x is a 5-face. It also implies that the common neighbors of z and v 3 are exactly v 0 and x, and the common neighbors of z and v 2 are exactly v 1 and y. Without loss of generality, let zyv 2 v 3 x be the outer face of G.
Let H 1 be obtained from the 4-cycle zv 0 v 3 x and its interior by adding edge zv 3 . The edge zv 3 is in only two triangles, and there is only one triangle in the interior of the 4-cycle. Hence by the minimality of G, there exists a 3-coloring ϕ 1 of H 1 .
Let H 2 be obtained from the 4-cycle zv 1 v 2 y and its interior by adding edge zv 2 . By the same argument as for H 1 , there is a 3-coloring of ϕ 2 of H 2 .
Proof of Theorem 9. Let G be a 4-chromatic projective plane graph where Figure 3: First three 4-critical graphs from the family described by Thomas and Walls [24]. every vertex is in at most one triangle and let G be 4-,5-and 6-cycle free. Then G contains a 4-critical subgraph G . Let G have e edges, n vertices and f faces. Since G is also 4-,5-and 6-cycle-free and every vertex is in at most one triangle, we get f ≤ n 3 + 2e−n 7 . By Eulers formula, 7n+6e−3n+21n−21e ≥ 21. Hence e ≤ 5n/3 − 21/15, a contradiction to Theorem 1.
Theorem 2 is best possible because there exists an infinite family [24] of 4-critical graphs that become triangle-free and planar after removal of just two edges. See Figure 3. Moreover, the same family shows also the tightness of Theorem 7, since the construction has exactly four triangles.
Aksenov [1] showed that every plane graph with one 6-face F and all other faces being 4-faces has no 3-coloring in which the colors of vertices of F form the sequence (1, 2, 3, 1, 2, 3). This implies that Theorem 5 is best possible. It also implies that Theorems 4 and 6 are best possible. See Figure 4 for constructions where coloring of three vertices or an extra vertex of degree 5 force a coloring (1, 2, 3, 1, 2, 3) of a 6-cycle.
Theorem 8 is best possible because there exist embeddings of K 4 in the projective plane with three 4-faces or with two 3-faces and one 6-face.