Victor Campos

Frédéric Havet
email: frederic.havet@inria.fr

Rudini Sampaio
email: rudini@lia.ufc.br

Ana Silva
email: anasilva@mat.ufc.br

Backbone colouring: tree backbones with small diameter in planar graphs

Keywords: Backbone colouring, planar graphs, Broerma's conjecture

Given a graph G and a spanning subgraph T of G, a backbone k-colouring for (G, T ) is a mapping c : V (G) → {1, . . . , k} such that |c(u) -c(v)| ≥ 2 for every edge uv ∈ E(T ) and |c(u) -c(v)| ≥ 1 for every edge uv ∈ E(G) \ E(T ). The backbone chromatic number BBC(G, T ) is the smallest integer k such that there exists a backbone k-colouring of (G, T ). In 2007, Broersma et al. [2] conjectured that BBC(G, T ) ≤ 6 for every planar graph G and every spanning tree T of G. In this paper, we prove this conjecture when T has diameter at most four.

Introduction

All the graphs considered in this paper are simple. Let G = (V, E) be a graph, and let H = (V, E(H)) be a spanning subgraph of G. A k-colouring of G is a mapping f : V → {1, 2, . . . , k}. Let f be a k-colouring of G. It is a proper colouring if |f (u) -f (v)| ≥ 1. It is a backbone colouring for (G, H) if f is a proper colouring of G and |f (u) -f (v)| ≥ 2 for all edges uv ∈ E(H). The chromatic number χ(G) is the smallest integer k for which there exists a proper k-colouring of G. The backbone colouring number BBC(G, H) is the smallest integer k for which there exists a backbone k-colouring of (G, H).

If f is a proper k-colouring of G, then g defined by g(v) = 2f (v)-1 is a backbone (2k -1)colouring of (G, H) for any spanning subgraph H of G. Hence, BBC(G, H) ≤ 2χ(G) -1. In [START_REF] Broersma | Backbone colourings for networks[END_REF][START_REF] Broersma | Backbone colourings for graphs: tree and path backbones[END_REF], Broersma et al. showed that for any integer k there is a graph G with a spanning tree T such that BBC(G, T ) = 2k -1.

The above inequality and the Four Colour Theorem implies that for any planar graph G and spanning subgraph H then BBC(G, H) ≤ 7. However Broersma et al. [START_REF] Broersma | Backbone colourings for graphs: tree and path backbones[END_REF] conjectured that this is not best possible if T is a tree.

Conjecture 1 If G is a planar graph and T a spanning tree of G, then BBC(G, T ) ≤ 6.

If true this conjecture would be best possible. Broersma et al. [START_REF] Broersma | Backbone colourings for graphs: tree and path backbones[END_REF] gave an example of a graph G * with a spanning tree T * such that BBC(G, T ) = 6. See Figure 1.

Figure 1: A planar graph G * with a spanning tree T * (bold edges) such that BBC(G * , T * ) = 6.

Bu and Zhang [START_REF] Bu | Backbone coloring for C 4 -free planar graphs[END_REF] proved that, if G is a connected non-bipartite C 4 -free planar graph, then there exists a spanning tree T of G such that BBC(G, T ) = 4. On the other hand, Bu and Li [START_REF] Bu | Backbone coloring of planar graphs without special circles[END_REF] proved that, if G is a connected planar graph that is C 6 -free or C 7 -free and without adjacent triangles, then there exists a spanning tree T of G such that BBC(G, T ) ≤ 4. In [START_REF] Wang | On backbone coloring of graphs[END_REF], Wang et al. investigated backbone colouring for special graph classes such as Halin graphs, complete graphs, wheels, graphs with small maximum average degree and graphs with maximum degree 3.

The diameter of a graph is the maximum distance between two vertices in this graph. If T has diameter 2, then it is a star, that is a tree in which a vertex v, called the center, is adjacent to every other. If a planar graph G has a spanning star T , with center v, then G -v is an outerplanar graph which can be properly 3-coloured with {1, 2, 3}. Thus assigning the colour 5 to v, we obtain a backbone 5-colouring of (G, T ). This result may be extended if G has a spanning tree with diameter at most 3.

Proposition 2 Let G be a planar graph with a spanning tree T . If T has diameter at most three, then BBC(G, T ) ≤ 5.

Proof. Free to add some edges, we may assume that G is triangulated. If T has diameter at most 3, then there exists two adjacent vertices x and y such that all edges of T are incident to x or y. Let z 1 , . . . , z p be the common neighbours of x and y, ordered in clockwise order around x (and so in anti-clockwise order around y). We consider an embedding of G with outer face xyz 1 .

For 1 ≤ i ≤ p -1, let G i be the graph induced by the vertices in the cycle xz i yz i+1 x and inside, and let H i = G i \ {x, y}. Since G is triangulated, all the vertices are in at least one G i . Furthermore, every H i is outerplanar, and every vertex in V (H i ) \ {z i , z i+1 } is adjacent to exactly one of x, y.

We shall now define a backbone 5-colouring c of (G, T ). First, we set c(x) = 1, c(y) = 5 and c(z 1 ) = 3. Next, we extend this colouring to the H i one after another. Since H i is outerplanar, it is 3-colourable. Let c i be a proper 3-colouring of H i in {2, 3, 4} such that c i (z i ) = c(z i ) and c i (z i+1 ) ∈ {3, 4} if z i+1 x ∈ E(T ) and c i (z i+1 ) ∈ {2, 3} if z i+1 y ∈ E(T ). We set c(z i+1 ) = c i (z i+1 ), and for every vertex v of V (H i ) \ {z i , z i+1 }, we define

• c(v) = c i (v), if c i (v) = 3
, or c i (v) = 2 and vy ∈ E(T ), or c i (v) = 4 and vx ∈ E(T );

• c(v) = 5, if c i (v) = 2 and vx ∈ E(T );

• c(v) = 1, if c i (v) = 4 and vy ∈ E(T ).

It is easy to check that c is a backbone 5-colouring of (G, T ).

Remark 3 Notice that the proof of Proposition 2 contains a explicit polynomial time algorithm to obtain a backbone 5-colouring of (G, T ) when G is planar and T has diameter at most 3, since 3-colourings of outerplanar graphs can be obtained in polynomial time [START_REF] Proskurowski | Efficient vertex and edge-coloring of outerplanar graphs[END_REF]. Proposition 2 is best possible, because when G is a complete graph on four vertices and T a spanning star of G, BBC(G, T ) = 5.

In this paper, we settle Conjecture 1 for tree with diameter at most 4.

Theorem 4 Let G be a planar graph with a spanning tree T . If T has diameter at most 4, then BBC(G, T ) ≤ 6.

Note that this result is best possible as the tree T * in the above example has diameter 4.

In the next section, we outline the proof of Theorem 4 whose details are postponed to Section 3.

The proof

We denote by Z 6 the set {1, 2, 3, 4, 5, 6} and, for any integer a ∈ Z 6 , we denote by [a] the set {a -1, a, a + 1} ∩ Z 6 .

Let G = (V, E) be a planar graph and T a spanning tree of G with diameter at most 4. T has a vertex r such that every vertex is at distance two from it in T . We call such a vertex the root of T . A vertex of V \ {r}, is a twig if it is adjacent to r in T and a leaf otherwise.

We shall prove a slightly stronger result than the one of Theorem 4.

Theorem 5 (G, T ) admits a backbone colouring in Z 6 such that the root is assigned 1.

Proof. In the remaining, by (G, T )-colouring, one should understand a backbone 6-colouring of (G, T ) such that r is assigned 1. We will prove it by considering a minimum counterexample (G, T ) with respect to its number of vertices. An edge of E \ E(T ) is said to be thin. Free to add some more thin edges, we may assume that G is triangulated.

If T has a unique twig, then it has diameter 2, and we have the result by the proof of Proposition 2. (The root corresponds to x 1 and the twig to x 2 .) Hence T has at least two twigs. We consider an embedding of G in the plane such that the outer face contains r and a minimum number of thin edges.

The interior (resp. exterior) of a cycle C, denoted C int (resp. C ext ) is the subgraph of G induced by C and the vertices inside C (resp. outside C).

Let e be a thin edge. The graph T ∪ {e} has a unique cycle C e (which contains e). The edge e is overstepping if there is a vertex inside C e . In other words, V (C int e ) = V (C e ). Let O be the set of overstepping edges. There is a partial order ≤ on O defined as follows: e 1 ≤ e 2 if e 1 = e 2 or e 1 is inside C e 2 (Lemma 6 proves that ≤ is a partial order). Observe that the Hasse diagram of such a partial order is a set of at most two disjoint trees, each one rooted at an overstepping thin edge in the outer face. Indeed, it is easy to see that every overstepping edge e that is not maximal has a unique successor for ≤ (i.e. overstepping edge f such that if e ≤ e ≤ f then e ∈ {e, f }). This successor is one of the two edges of the face containing e contained in C ext e . Furthermore, every edge e has at most two predecessors for ≤: the two other edges of the face containing e contained in C int e . The idea of the proof is to find a "good" overstepping edge e, such that a backbone 6colouring of the graph induced by V (C ext e ) (which exists by minimality of (G, T )) can be extended to V (C int e ) to obtain a (G, T )-colouring. This will be a contradiction. Natural candidates for such a good edge are overstepping edges e which are minimal for ≤ (i.e. such that e ≤ e implies e = e) or their sucessors. However we will need to consider a more precise partial ordering. If there are two overstepping edges e 3 = rv 1 and e 4 = v 1 v 2 such that v 1 and v 2 are leaves and e 4 ≤ e 3 , (i.e. e 4 is not inside e 3 ), then we would like to have e 3 smaller than e 4 in the ordering.

This leads to the following binary relation between overstepping edges: e 1 e 2 if e 1 ≤ e 2 or there exist two edges e 3 = rv 1 and e 4 = v 1 v 2 such that v 1 and v 2 are leaves, e 4 ≤ e 3 , e 1 ≤ e 3 and e 4 ≤ e 2 . In Lemma 6, we prove that is a partial order.

In the remainder of the paper, we will only consider the partial order . Hence the terms minimal, predecessor, successor, and so on refer to .

We first show some properties of minimal overstepping edges and deduce in Lemma 14 that if e is a minimal overstepping edge, then C int e is isomorphic to one of the graphs A 1 , A 2 or A 3 , depicted in Figure 2. In addition, if C int e = A 1 , then rv 1 ∈ E(G).

t 1 A 2 A 1 r r u v 1 v 2 v 1 v 2 v 1 v 2 t 2 t 2 t 2 t 1 t 1 r A 3 u u Figure 2: Configurations A 1 , A 2 and A 3
As any ordering, may be decomposed into levels. The first level L 1 the maximal edges for (i.e. such that e e implies e = e). This level contains at most two edges, depending on the number of thin overstepping edges in the outer face. Then, for every j ≥ 1, the level L j+1 is the set of predecessors of elements of L j . The depth of , denoted D, is the maximum j such that L j is not empty. An overstepping edge of L D is said to be ultimate. An edge of L D-1 having at least one (ultimate) predecessor is said to be penultimate. An edge of L D-2 having at least one penultimate predecessor is said to be antepenultimate.

If f is a penultimate edge, then it has one or two predecessors. Furthermore each of this predecessors e is ultimate and so minimal. Thus C int e is isomorphic to A 1 , A 2 or A 3 . Analyzing all possible cases, we show (Corollary 17) that, if f is a penultimate edge, then C int f is isomorphic to B 1 or B 2 , and that moreover rv Now if g is an antepenultimate edge, then it has one or two predecessors. Furthermore at least one of its predecessors f is penultimate (and so C int f is isomorphic to B 1 or B 2 ), and the other predecessor f (if it exists) is either penultimate (so

1 ∈ E(G) and, if C int f = B 2 , rv 3 / ∈ E(G). v 3 r t 1 u v 1 v 2 t 2 v 3 B 1 u v 1 v 2 t 2 t 1 r B 2
C int f is isomorphic to B 1 or B 2 ) or ultimate (so C int f is isomorphic to A 1 , A 2 or A 3
). Analyzing all the possibles cases again, we show that there are no antepenultimate edges (Corollary 24). Now, suppose that G contains at least one overstepping edge. If e is a minimal edge, then C int e is isomorphic to some configuration A i . In any of these cases, there is at least one face containing the root and only one thin edge. Therefore, the partial order considered contains a unique maximal overstepping edge e 0 . Furthermore, since e 0 is not antepenultimate, C int e 0 must be isomorphic to one of the A i or B j configurations. We get a contradiction as the outer face contains r and the endpoints of e 0 and e 0 is the unique thin edge in this configuration and T would not be a tree.

We proved that G contains no overstepping edge. If the outer face of G contains only one thin edge, then G contains three vertices and the diameter of G is 2. If the outer face contains two thin edges e 1 and e 2 , then one thin edge (say e 1 ) is adjacent to r, since r is on the outer face, and the other (say e 2 ) is adjacent to a twig t while both are incident to a vertex v in the outer face. Now, both r and v have a twig v as a common neighbour through edges of T as T is a spanning tree. Since neither e 1 nor e 2 are overstepping, then V (G) = {r, t, v, v } and G has diameter 3. Both of these cases are solved using Proposition 2 and both can give colour 1 to the root, a contradiction.

The details

Lemma 6

The binary relation is a partial order.

Proof. Let e 0 , e 1 , e 2 be overstepping edges. At first, we prove that ≤ is a partial order. By the definition, it is clearly reflexive. Now suppose that e 1 ≤ e 2 and e 2 ≤ e 1 . Then, by the Proof. Suppose for a contradiction that d T (x) = 1 and d G (x) ≤ 3. By minimality of (G, T ), there is a (G -x, T -x)-colouring c. At x, at most 3 colours are forbidden by its neighbour in T and at most 2 colours are forbidden by its two other neighbours. So one colour of Z 6 is still available to colour the vertex x. Hence one can extend c to (G, T ), a contradiction.

Minimal overstepping edges

Lemma 8 Let e = uv be a minimal overstepping edge. Then there are at most two vertices inside C e . Moreover if there are two, then they are adjacent in T and one of them is a twig and the other is a leaf.

Proof. Since G is triangulated, uv is incident to two triangular faces, one of which, say F , is included in C int e . Let w be the third vertex incident to F . Let P be the path joining u to v in T and Q be the path joining w to P in T . Since T has diameter 4 and r is on the outer face, then Q has length at most 2.

Then C int e is divided into at most three regions: F , C int uw and C int vw (the region C int uw or C int vw may not exist if uw ∈ E(T ) or vw ∈ E(T ) respectively). As F is a face, its interior is empty, and there are no vertices inside C int uw and C int vw because uw and vw are not overstepping since e is minimal. Hence the only possible vertices inside C e are those of Q. Therefore there are at most two vertices inside C e as Q has length at most 2.

Furthermore, if there are two vertices inside C e , they must be adjacent as they are in Q. In addition, since r is on the outer face, none of these vertices is the root and thus one of them is a twig and the other is a leaf.

Lemma 9 No minimal overstepping edge joins two leaves adjacent to a same twig.

Proof. Suppose for a contradiction that an edge e = uv joins two leaves adjacent to a same twig t. Then C e = tuvt. The root r is not in C int e as it is on the outer face. So by Lemma 8 and because G is triangulated, C int e is a K 4 and there is a unique vertex x inside C e . Hence, x contradicts Lemma 7.

Lemma 10 No minimal overstepping edge joins two twigs.

Proof. Suppose for a contradiction that two twigs s and t are joined by a minimal edge e.

Then C e = rstr. If there is a unique vertex u inside C int e , then u contradicts Lemma 7. So by Lemma 8, we may assume that the interior of C e contains two adjacent vertices u 1 and u 2 and that u 1 is a twig and u 2 a leaf. By minimality of (G, T ), there is a (G -{u 1 , u 2 }, T -{u 1 , u 2 })colouring c. Set c(u 2 ) = 2 and choose c(u 1 ) in Z 6 \ {1, 2, 3, c(s), c(t)}. This yields a (G, T )colouring, a contradiction.

Lemma 11 No minimal overstepping edge joins the root and a leaf.

Proof. Suppose for a contradiction that a minimal edge e joins the root r and a leaf v. Let t be the twig adjacent to v.

Suppose there is a unique vertex u inside C e . Then this vertex has only 3 neighbours, and d T (u) = 1. This contradicts Lemma 7. Hence by Lemma 8, we may assume that there are two adjacent vertices u 1 and u 2 inside C e . Without loss of generality, u 2 is a leaf and u 1 is a twig. By Lemma 7,

d G (u 2 ) ≥ 4, so N G (u 2 ) = {u 1 , r, v, t}. By minimality of G, there is a (G -{u 1 , u 2 }, T -{u 1 , u 2 })-colouring c. Let c(u 2 ) be a colour in {2, 3} \ {c(v), c(t)}. (Such a colour exists because |c(v) -c(t)| ≥ 2.
) Now by planarity, u 1 has at most one neighbour x in {v, t} as ru 2 is an edge. The set of forbidden colours in u

1 is I = [1] ∪ [c(u 2 )] ∪ {c(x)}
which has cardinality at most 5 by the choice of c(u 2 ). Hence assigning to u 1 a colour c(u 1 ) in Z 6 \ I, we obtain a (G, T )-colouring, a contradiction.

Lemma 12

No minimal overstepping edge joins a leaf and a twig.

Proof. Suppose for a contradiction that a minimal overstepping edge e = sv joins a twig s and a leaf v. Then C e = svtrs. By Lemma 8 there are at most two vertices inside C e .

Suppose that there is a unique vertex u inside C e . As d T (u) = 1, by Lemma 7, d G (u) ≥ 4. So N G (u) = {r, s, t, v}. Note that rv or st is not an edge, by planarity. Then, removing u and contracting rv or st, we find by the minimality of G a (G -u, T -u)-colouring c such that c(v) = 1 or c(s) = c(t). Since the set of forbidden colours for u has at most 5 colours, one can extend c into a (G, T )-colouring, a contradiction.

Hence by Lemma 8, inside C e there are a twig u 1 and leaf u 2 which are adjacent in T . As

d T (u 2 ) = 1, d G (u 2 ) ≥ 4 by Lemma 7.
• Suppose first that r is not adjacent to u 2 . By Lemma 7,

d G (u 2 ) ≥ 4. So N G (u 2 ) = {u 1 , s, t, v}.
Hence u 1 is not adjacent to v by planarity. By minimality of (G, T ), there is a (G -

{u 1 , u 2 }, T -{u 1 , u 2 })-colouring c. Assign to u 2 a colour c(u 2 ) in {1, 2} \ c(v).
Observe that it is valid since s and t are not coloured in {1, 2}. Then the set of forbidden colours in u 1 is included in {1, 2, 3, c(s), c(t)} and so has cardinality at most 5. Hence one can extend c into a (G, T )-colouring a contradiction.

• Suppose now that r is adjacent to u 2 .

By planarity, u 1 is adjacent to at most one vertex w in {s, t}. By minimality of (G, T ), there is a

(G -{u 1 , u 2 }, T -{u 1 , u 2 })-colouring c. If c(v) = 2, then set c(u 2 ) = 2.
This it is valid since s and t are not coloured 2. Then the set of forbidden colours in u 1 is included in {1, 2, 3, c(v), c(w)} and so has cardinality at most 5. Hence one can extend c into a (G, T )-colouring a contradiction. Hence we may assume that c(v) = 2.

If no neighbour of u 2 is coloured 6, then set c(u 2 ) = 6. The set of forbidden colours in u 1 is then {1, 2, 5, 6, c(w)} and so one can extend c into a (G, T )-colouring a contradiction. Hence we may assume that a neighbour y of u 2 is coloured 6.

If no neighbour of u 2 is coloured 3, then set c(u 2 ) = 3. The set of forbidden colours in u 1 is then {1, 2, 3, 4, c(w)} and so one can extend c into a (G, T )-colouring a contradiction. Hence we may assume that a neighbour y of u 2 is coloured 3. But this neighbour cannot be t since c(v) = 2. Thus c(s) = 3 and c(t) = 6.

If w = s, that is if u 1 is not adjacent to t, then setting c(u 1 ) = 6 and c(u 2 ) = 4 yields a (G, T )-colouring, a contradiction.

If w = t, then setting c(u 1 ) = 3 and c(u 2 ) = 5 yields a (G, T )-colouring, a contradiction.

Lemma 13 If e is a minimal overstepping edge joining two leaves, then there is one vertex inside C e .

Proof. Let e = v 1 v 2 and for i = 1, 2, let t i be the twig adjacent to v i . By Lemma 9, t 1 = t 2 . Since e is minimal and G is triangulated,

u 2 v 1 , u 2 v 1 ∈ E(G).
Suppose for a contradiction that more than one vertex is inside C e . Then, by Lemma 8, inside C e , there are a twig u 1 and a leaf u 2 which are adjacent in T . Moreover, by Lemma 7,

d G (u 2 ) ≥ 4 and so d G (u 1 ) ≤ 5.
Let us first suppose that ru 2 is not an edge. By symmetry, we may assume that u

1 v 1 is not an edge. Set G = (G -{u 1 , u 2 }) ∪ {rv 1 , rv 2 }. By minimality of (G, T ), there is a (G , T -{u 1 , u 2 })-colouring, which is a (G -{u 1 , u 2 }, T -{u 1 , u 2 })-colouring c such that c(v 1 ) = 1 and c(v 2 ) = 1.
Then setting c(u 2 ) = 1 and colouring u 1 with a colour in Z 6 \ {1, 2, c(t 1 ), c(t 2 ), c(v 2 )}, we obtain a (G, T )-colouring, a contradiction. Hence we may assume that ru 2 ∈ E(G). Then, since e is minimal, u 1 v 1 is not an edge. By symmetry, we may assume that ru 2 is inside the cycle rt

1 v 1 u 2 u 1 r. Thus N (u 1 ) ⊂ {r, t 2 , v 2 , u 2 }.
Assume now that rv 1 is not an edge. Let (G , T ) be the graph pair obtained from (G -

{u 1 , u 2 }, T -{u 1 , u 2 }) by identifying r and v 1 . By minimality of (G, T ), there is a (G , T )- colouring which is a (G -{u 1 , u 2 }, T -{u 1 , u 2 })-colouring c such that c(v 1 ) = c(r) = 1. If c(v 2 ) = 2, then setting c(u 2 ) = 2 and colouring u 1 with a colour in Z 6 \ {1, 2, 3, c(t 2 ), c(v 2 )}, we obtain a (G, T )-colouring, a contradiction. If c(v 2 ) = 2, then c(t 2 ) ≥ 4. If c(t 1 ) = 3,
then colour u 2 with 3 and u 1 with some colour in {5, 6}\{c(t 2 )}; otherwise, colour u 1 with 3 and u 2 with a colour in {5, 6} \ {c(t 2 )}. In both cases, we obtain a (G, T )-colouring, a contradiction. Hence we may assume that rv 1 ∈ E(G).

Assume that rv 2 is not an edge. Let (G , T ) be the graph pair obtained from (G -

{u 1 , u 2 }, T -{u 1 , u 2 }) by identifying r and v 2 . By minimality of (G, T ), there is a (G , T )- colouring which is a (G -{u 1 , u 2 }, T -{u 1 , u 2 })-colouring c such that c(v 2 ) = c(r) = 1.
If there is a colour α ∈ {2, 3, 6} which does not appear on the neighbourhood of u 2 , then setting c(u 2 ) = α and colouring u 1 with a colour in

Z 6 \ ({1, 2, c(t 2 )}) ∪ [α],
we obtain a (G, T )colouring, a contradiction. So all the colours of {2, 3, 6} appear on the neighbourhood of u 2 . Necessarily, in this case, u 2 is adjacent to v 1 , t 1 and t 2 and c(v 1 ) = 2, c(t 1 ) = 6 and c(t 2 ) = 3. Then setting c(u 2 ) = 4 and c(u 1 ) = 6, we obtain a (G, T )-colouring, a contradiction. Hence we may assume that rv 2 ∈ E(G).

We now distinguish several cases depending on the position of rv 1 and rv 2 regarding C e .

1. Assume first that rv 1 and rv 2 are in C ext e . Then t 1 t 2 is not an edge by planarity. Let (G , T ) be the graph pair obtained from (G-{u 1 , u 2 }, T -{u 1 , u 2 }) by identifying t 1 and t 2 . By minimality of (G, T ), there is a (G , T )-colouring which is a

(G-{u 1 , u 2 }, T - {u 1 , u 2 })-colouring c such that c(t 1 ) = c(t 2 ) = α. If 2 / ∈ {c(v 1 ), c(v 2 )}, then setting c(u 2 ) = 2 and colouring u 1 with a colour in Z 6 \ {1, 2, 3, α, c(v 2 )}, we obtain a (G, T )- colouring, a contradiction. Hence 2 ∈ {c(v 1 ), c(v 2 )}, so α ≥ 4. If {c(v 1 ), c(v 2 )} = {2, 3}, then setting c(u 2 ) = 3 and colouring u 1 with a colour in {5, 6} \ {α, c(v 2 )}, we obtain a (G, T )-colouring, a contradiction. Hence {c(v 1 ), c(v 2 )} = {2, 3}, so α ≥ 5. If c(v 2 ) = 3 or u 1 v 2 /
∈ E(G), then setting c(u 1 ) = 3 and and colouring u 2 with a colour in {5, 6} \ {α}, we obtain a (G, T )-colouring, a contradiction. Hence c(v 2 ) = 3 and u 1 v 2 ∈ E(G). By planarity, this implies that u 2 t 2 is not an edge.

Observe that at least one of the two edges rv 1 and rv 2 is not overstepping otherwise one of them would be smaller than e in the order .

If rv 1 is not overstepping, then the interior of rt 1 v 1 is empty. Hence N G (t 1 ) = {r, v 1 , u 2 }. Setting c(u 1 ) = 4, c(u 2 ) = 6 and recolouring t 1 with 5, we obtain a (G, T )-colouring, a contradiction.

If rv 2 is not overstepping, then the interior of rt 2 v 2 is empty. Hence N G (t 2 ) = {r, u 1 , v 2 }.
Setting c(u 1 ) = 6, c(u 2 ) = 4 and recolouring t 2 with 5, we obtain a (G, T )-colouring, a contradiction.

Assume that

rv 1 and rv 2 are in C int e . Then N G (u 1 ) = {r, u 2 , v 2 }. By minimality of (G, T ), there is a (G -{u 1 , u 2 }, T -{u 1 , u 2 })-colouring c. Colour u 2 with a colour c(u 2 ) in {2, 3, 6}\{c(v 1 ), c(v 2 )}. Then the set of forbidden colours in u 1 is {1, 2, c(v 2 )}∪[c(u 2 )]
which has cardinality at most 5 because {1, 2} ∪ [c(u 2 )] has cardinality at most 4. Hence one can extend c into a (G, T )-colouring, a contradiction.

Assume that rv

1 is in C int e and rv 2 is in C ext e . Assume that d G (u 2 ) = 5, so N G (u 2 ) = {r, u 1 , v 1 , v 2 , t 2 } and N G (u 1 ) = {r, t 2 , u 2 }. By minimality of (G, T ), there is a (G-{u 1 , u 2 }, T -{u 1 , u 2 })-colouring c. If one can colour u 2 with a colour in {2, 3, 6}, then {1, 2} ∪ [c(u 2 )
] has cardinality at most 4 and so at most 5 colours are forbidden for u 1 . Hence one can extend c into a (G, T )-colouring, a contradiction. So we may assume {c(t 2 ), c(v 1 ), c(v 2 )} = {2, 3, 6}. If c(t 2 ) = 6, then setting c(u 1 ) = 3 and c(u 2 ) = 5, we obtain a (G, T )-colouring, a contradiction. If c(t 2 ) = 6, then setting c(u 1 ) = 6 and c(u 2 ) = 4, we obtain a (G, T )-colouring, a contradiction.

Henceforth we may assume that d

G (u 2 ) = 4, so N G (u 2 ) = {r, u 1 , v 1 , v 2 } and N G (u 1 ) = {r, t 2 , v 2 , u 2 }. If {c(v 1 ), c(v 2 )} = {2, 3}, then one can colour u 2 with a colour in {2, 3} and u 1 with a colour in {5, 6} \ {c(t 2 ), c(v 2 )} to obtain a (G, T )-colouring, a contradiction.
If {c(v 1 ), c(v 2 )} = {2, 3}, then colouring u 1 with a colour c(u 1 ) in {4, 6} \ {c(t 2 )} and u 2 with the colour in {4, 6} \ {c(u 1 )}, we obtain a (G, T )-colouring, a contradiction.

Assume rv

2 is in C int e and rv 1 is in C ext e . Then N G (u 1 ) = {r, u 2 , v 2 } and N G (u 2 ) = {r, u 1 , t 1 , v 1 , v 2 }. By minimality of (G, T ), there exists a (G -{u 1 , u 2 }, T -{u 1 , u 2 })- colouring c. If c(v 2 ) = 2, then colouring u 2 with a colour c(u 2 ) in Z 6 \ {1, 2, c(t 1 ), c(v 1 )} and u 1 with a colour in {3, 4, 5, 6} \ [c(u 2 )],
we obtain a (G, T )-colouring, a contradiction. So we may assume that c(v 2 ) = 2.

If one can colour u 2 with a colour in {2, 3, 6}, then {1, 2} ∪ [c(u 2 )] has cardinality at most 4 and so at most 5 colours are forbidden in u 1 . Hence one can extend c into a (G, T )-colouring, a contradiction.

So we may assume {c

(t 1 ), c(v 1 ), c(v 2 )} = {2, 3, 6}. Necessarily, c(v 1 ) = 2, c(v 2 ) = 3
and c(t 1 ) = 6. Setting c(u 1 ) = 6 and c(u 2 ) = 4, we obtain a (G, T )-colouring, a contradiction.

Lemma 14 If e is a minimal overstepping edge, then C int e is one of the graphs depicted in Figure 2. In addition, if

C int e = A 1 , then rv 1 ∈ E(G).
Proof. Let e be a minimal edge. According to the previous lemmas, it has to join two leaves v 1 and v 2 and there is a unique vertex u inside C e . For i = 1, 2, let t i be the twig adjacent to v i . By Lemma 9, t 1 = t 2 .

• Assume first that u is a twig.

If d G (u) ≤ 4, then consider a (G -u, T -u)-colouring c, which exists by minimality of (G, T ). In u, there are at most 5 colours forbidden as r is coloured 1, and thus forbids only two colours. Hence, one can extend c into a (G, T )-colouring, a contradiction.

So we may assume that d G (u) ≥ 5, and thus

N G (u) = {r, t 1 , t 2 , v 1 , v 2 }.
If rv 1 is not an edge, then let (G , T ) be the pair obtained from (G -u, T -u) by identifying r and v 1 . By minimality of (G, T ), there is a (G , T )-colouring, which is a

(G -u, T -u)-colouring such that c(v 1 ) = c(r) = 1. Then the set of forbidden colours in u is included in {1, 2, c(t 1 ), c(t 2 ), c(v 2 )
} and so has cardinality at most 5. Hence one can extend c into a (G, T )-colouring, a contradiction.

Hence we may assume that rv 1 is an edge. This edge must be in C ext e by planarity of G. Thus t 1 t 2 is not an edge of G. Let (G , T ) be the pair obtained from (G -u, T -u) by identifying t 1 and t 2 . By minimality of (G, T ), there is a (G , T )-colouring c which is a (G -u, T -u)-colouring such that c(t 1 ) = c(t 2 ). Then the set of forbidden colours in u is included in {1, 2, c(t 1 ), c(v 1 ), c(v 2 )} and so has cardinality at most 5. Hence one can extend c into a (G, T )-colouring, a contradiction.

• Assume now that u is a leaf. By symmetry, we may assume that u is adjacent to t 1 . By Lemma 7 and since G is triangulated, C int e is one of the graphs A 1 , A 2 or A 3 .

Assume now that C int e = A 1 and rv 1 / ∈ E(G). Let (G , T ) be the pair obtained from (G -u, T -u) by identifying r and v 1 . By minimality of (G, T ), there is a (G , T )-colouring which is a (G -u, T -u)-colouring c such that c(v 1 ) = c(r) = 1. Then the set of forbidden colours in u is included in {1, c(v 2 )} ∪ [c(t 1 )] and so has cardinality at most 5. Hence one can extend c into a (G, T )-colouring, a contradiction.

Penultimate edges

Lemma 15 Let f be an edge which is the successor of a minimal edge e. If e is the unique predecessor of f , then C int f is one of the graphs depicted in Figure 3, and

rv 1 ∈ E(G). Morever, if C int f = B 2 , rv 3 / ∈ E(G).
Proof. Let e be the third edge of the triangle bounded by f and e in C int f . Suppose, by way of contradiction, that e is the unique predecessor of f . Then e is not overstepping. So all the vertices inside C f are in C int e . By Lemma 14, C int e is one of the graphs A 1 , A 2 or A 3 . One of the endvertices of f must be v 1 and v 2 (as defined for A i ). We now distinguish many cases depending on C int e and the possible endvertices of f .

1. Assume that C int e is A 1 . 1.1. Assume f = rv 1 . Then the 4-cycle rt 2 v 2 v 1 has no chord, because rv 2 is in C int e
and v 1 t 2 is not an edge since f is the succesor of e. This contradicts the fact that G is triangulated.

1.2 Observe that f = t 1 v 2 is impossible since rv 1 is an edge. Assume that f = t 2 v 1 . Let G = (G -{u, v 2 }) ∪ t 1 t 2 . By minimality of (G, T ), there exists a (G , T -{u, v 2 })-colouring which is a (G-{u, v 2 }, T -{u, v 2 })-colouring c such that c(t 1 ) = c(t 2 ). If c(t 1 ) = 6,
(u), c(v 1 ), c(t 3 } = {2, 3, 6}. If c(t 3 ) = 3, set c(v 2 ) = 4 and c(t 2 ) = 6. If c(t 3 ) = 6, set c(v 2 ) = 5 and c(t 2 ) = 3.
In both cases, we obtain a (G, T )-colouring, a contradiction.

1.4. Assume that f = v 2 t 3 with t 3 a twig distinct from t 1 . By minimality of (G, T ), there exists a (G -{u,

t 1 , v 1 }, T -{u, t 1 , v 1 })-colouring c. Setting c(t 1 ) = 6 and choosing c(v 1 ) in Z 6 \ {1, 5, 6, c(t 3 ), c(v 2 )} and c(u) in Z 6 \ {1, 5, 6, c(v 1 ), c(v 2 )}, we get a (G, T )- colouring, a contradiction. 1.5. f cannot be v 2 v 3 with v 3 a leaf adjacent to t 1 because rv 1 is an edge. 1.6 Assume that f = v 1 v 3 with v 3 a leaf adjacent to t 2 . Then C int e = B 1 . By Lemma 14, rv 1 ∈ E(G). 1.7. Assume f = v 2 v 3 with v 3 a leaf adjacent in T to a twig t 3 not in {t 1 , t 2 }. Then v 1 v 3 ∈ E(G) and either rv 3 ∈ E(G) or t 3 v 1 ∈ E(G).
Since rv 1 is an edge, we have that N (t 1 ) = {r, u, v 1 }. By minimality of G, there exists a (G -{u,

t 1 , v 1 }, T -{u, t 1 , v 1 })- colouring c.
If {c(t 3 ), c(v 3 ), c(v 2 )} = {2, 3, 4}, then setting c(t 1 ) = 6 and choosing c(v 1 ) in {2, 3, 4} \ {c(t 3 ), c(v 3 ), c(v 2 )} and c(u) in {2, 3, 4} \ {c(v 1 ), c(v 2 )}, we obtain a (G, T )-colouring, a contradiction. Hence {c(t 3 ), c(v 3 ), c(v 2 )} = {2, 3, 4}, and so c(t 3 ) = 4, c(v 3 ) = 2 and c(v 2 ) = 3. Then setting c(t 1 ) = 3, c(u) = 5 and c(v 1 ) = 6 yields a (G, T )-colouring, a contradiction.

1.8. Assume f = v 1 v 3 with v 3 a leaf adjacent in T to a twig t 3 not in {t 1 , t 2 }. Since rv 1 ∈ E(G), then t 1 t 3 / ∈ E(G).
Assume first that rv 3 ∈ C int f . By minimality of (G, T ), there exists a (G

-{t 2 , v 2 }, T - {t 2 , v 2 })-colouring c. One can choose a colour c(v 2 ) in Z 6 \ {1, c(u), c(v 1 ), c(v 3 )} such that I = [c(v 2 )] ∪ {1, 2, c(v 3 )} = Z 6 . Then choosing c(t 2 ) ∈ Z 6 \ I, we obtain a (G, T )- colouring, a contradiction.
Hence we may assume that rv 3 is not in C int f . Let (G , T ) be the graph obtained from (G -{u, t 2 , v 2 }, T -{u, t 2 , v 2 }) by identifying t 1 and t 3 . By minimality of (G, T ), there exists a (G , T )-colouring which is a (G-{u,

t 2 , v 2 }, T -{u, t 2 , v 2 })-colouring c such that c(t 1 ) = c(t 3 ). If c(t 1 ) = 6, then one can choose a colour c(v 2 ) ∈ {c(t 1 ) -1, c(t 1 ) + 1} such that I = [c(v 2 )] ∪ {1, 2, c(v 3 )} = Z 6 . Then choosing c(t 2 ) ∈ Z 6 \ I and c(u) in Z 6 \ ([c(t 1 )] ∪ {1, c(v 1 )},
. Set G = (G - {u, t 2 , v 2 }) ∪ rv 1 . By minimality of (G, T ), there is a (G , T -{u, t 2 , v 2 })-colouring c which is a (G -{u, t 2 , v 2 }, T -{u, t 2 , v 2 })-colouring c such that c(v 1 ) = c(r) = 1. Set c(u) = 1.
If c(v 1 ) = 2, then setting c(v 2 ) = 2 and colouring t 2 with a colour in Z 6 \{1, 2, 3, c(t 1 ), c(t 3 )}, we obtain a (G, T )-colouring, a contradiction. So c(v 1 ) = 2 and thus c(t 1 ) ≥ 4.

If c(t 3 ) = 3, then setting c(t 2 ) = 3 and choosing c(v 2 ) in {5, 6} \ {c(t 3 )}, we obtain a (G, T )-colouring, a contradiction. So c(t 3 ) = 3.

Choosing c(t 2 ) in {4, 6}\{c(t 1 )} and c(v 2 ) in {4, 6}\{c(t 2 )}, we obtain a (G, T )-colouring, a contradiction.

2.5. Assume that f = v 2 t 3 with t 3 a twig distinct from t 1 . Then either rv 1 is an edge or

t 1 t 3 is an edge. Set G = (G -{u, t 1 , v 1 }) ∪ rv 2 . By minimality of (G, T ), there exists a (G , T -{u, t 1 , v 1 })-colouring which is a (G -{u, t 1 , v 1 }, T -{u, t 1 , v 1 })-colouring c such that c(v 2 ) = c(r) = 1. Set c(u) = 1.
If c(v 2 ) = 2, then setting c(v 1 ) = 2 and colouring t 1 with a colour in Z 6 \{1, 2, 3, c(t 2 ), c(t 3 )}, we obtain a (G, T )-colouring, a contradiction. So c(v 2 ) = 2 and thus c(t 2 ) ≥ 4.

If c(t 3 ) = 3, then setting c(t 1 ) = 3 and choosing c(v 1 ) in {5, 6} \ {c(t 3 )}, we obtain a (G, T )-colouring, a contradiction. So c(t 3 ) = 3.

Choosing c(t 1 ) in {4, 6}\{c(t 2 )} and c(v 1 ) in {4, 6}\{c(t 1 )}, we obtain a (G, T )-colouring, a contradiction.

2.6. Assume that f = v 2 v 3 with v 3 a leaf adjacent to t 1 . Since f is the successor of e, then t 1 v 2 is not inside

v 3 t 1 v 1 v 2 and so v 1 v 3 ∈ E(G). Set G = (G-{u, v 1 })∪t 2 v 3 . By minimality of (G, T ), there is a (G , T -{u, v 1 })-colouring which is (G -{u, v 1 }, T -{u, v 1 })-colouring c such that c(t 2 ) = c(v 3 ). Setting c(u) = c(v 3 ) and colouring v 1 with a colour in Z 6 \ ({c(u), c(v 2 )} ∪ [c(t 1 )])
, we obtain a (G, T )-colouring, a contradiction.

Assume that

f = v 1 v 3 with v 3 a leaf adjacent to t 2 . Since f is the successor of e, then t 2 v 1 is not inside v 2 t 2 v 3 v 1 and so v 2 v 3 ∈ E(G). Set G = (G-{u, v 2 })∪t 1 v 3 . By minimality of (G, T ), there is a (G , T -{u, v 2 })-colouring, which is a (G-{u, v 2 }, T -{u, v 2 })-colouring c such that c(t 1 ) = c(v 3 ). If c(t 2 ) ∈ [c(t 1
)], then one can also extend c greedily to v 2 and then u to obtain a (G, T )-colouring, a contradiction. Hence |c(t 1 ) -c(t 2 )| ≥ 2. Thus one can colour v 2 with c(t 1 ) and then colour u with a colour in

Z 6 \ ([c(t 1 )] ∪ {c(t 2 ), c(v 1 )}).
This yields a (G, T )-colouring, a contradiction.

2.8. Assume f = v 2 v 3 with v 3 a leaf adjacent in T to a twig t 3 not in {t 1 , t 2 }.
Suppose first that rv 1 / ∈ E(G). By minimality of (G, T ), there is a (G -{u,

t 1 , v 1 } ∪ {rv 3 , rv 2 }, T -{u, t 1 , v 1 })-colouring which is a (G-{u, t 1 , v 1 }, T -{u, t 1 , v 1 })-colouring c such that c(v 2 ) = 1 and c(v 3 ) = 1. Colour v 1 with 1 and let L(t 1 ) ⊇ Z 6 \{1, 2, c(v 3 ), c(t 3 ), c(t 2 )} and L(u) = Z 6 \ {1, c(t 2 ), c(v 2 )
} be the list of colours available for t 1 and u, respectively. Note that there is at most one colour α in Z 6 such that L(u) \ [α] = ∅. Thus, if there exists β in L(t 1 ) \ {α} if such α exists, or in L(t 1 ) otherwise, then we can colour t 1 with β and u with a colour in L(u) \ [β] to obtain a (G, T )-colouring, a contradiction. So we may assume that no such β exists, that is L(t 1 ) = {α} and L(u)

\ [α] = ∅. Since |c(v 2 ) -c(t 2 )| ≥ 2, necessarily α = 4, L(t 1 ) = {4}, c(t 2 ) = 6, c(v 2 ) = 2, {c(v 3 ), c(t 3 )} = {3, 5} and v 3 , t 3 ∈ N (t 1 )
. Then, recolouring v 1 with 6 and colouring t 1 with 4 and u with 1 yields a (G, T )-colouring, a contradiction. Suppose now that rv 1 ∈ E(G). Then there is no vertex inside rt 1 v 1 r. By minimality of (G, T ), there is (G -u, T -u)-colouring c. If c(v 2 ) = 1, then we can colour u with 1; so, suppose otherwise. If there is no colour available for u to extend c, then

F c = {1, c(t 2 ), c(v 1 )} ∪ [c(t 1 )
] is equal to Z 6 ; thus, c(t 1 ) ∈ {3, 4, 5}. If c(t 1 ) = 3, then {c(v 1 ), c(t 2 )} = {5, 6}. If c(t 1 ) = 4, then {c(v 1 ), c(t 2 )} = {2, 6}. If c(t 1 ) = 5, then {c(v 1 ), c(t 2 )} = {2, 3}. If the colour of t 1 can be changed, we obtain a (G -u, Tu)-colouring c such that F c = Z 6 which can be extended in a (G, T )-colouring, a contradiction. Hence, c(t 1 ) = i is the sole colour in Z 6 \ ({1, 2, c(t 2 )} ∪ [c(v 1 )]). Thus, c(v 1 ) = 2 and (c(v 1 ), c(t 2 )) = [START_REF] Proskurowski | Efficient vertex and edge-coloring of outerplanar graphs[END_REF][START_REF] Bu | Backbone coloring for C 4 -free planar graphs[END_REF]. Then, necessarily (*) c(v 1 ) = 5, c(t 1 ) = 3 and c(t 2 ) = 6. If c(t 3 ), c(v 3 ) = 3, then recolour t 1 with 5 and v 1 with 3. Otherwise, if c(t 3 ), c(v 3 ) = 6, then recolour v 1 with 6. Otherwise (i.e., {c(t 3 ), c(v 3 )} = {3, 6}), recolour v 1 with 2. In any case, the resulting colouring c 1 does not satisfy (*). Hence, either F c 1 = Z 6 or t 1 can be recoloured to get a colouring c 1 such that F c 1 = Z 6 . Hence one of c 1 , c 1 can be extended in a (G, T )-colouring, a contradiction.

Assume

f = v 1 v 3 with v 3 a leaf adjacent in T to a twig t 3 not in {t 1 , t 2 }. Suppose first that rv 2 ∈ E(G). Set G = (G-{u, t 2 , v 2 })∪{t 1 t 3 , t 1 v 3 }. By minimality of (G, T ), there is a (G , T -{u, t 2 , v 2 })-colouring, which is a (G-{u, t 2 , v 2 }, T -{u, t 2 , v 2 })- colouring c such that c(t 1 ) = c(t 3 ) and c(t 1 ) = c(v 3 ). Set c(v 2 ) = c(t 1 ). Then choosing c(t 2 ) in {3, 4, 5, 6} \ [c(t 1 )] and c(u) in Z 6 \ ([c(t 1 )] ∪ {c(t 2 ), c(v 1 )}), we obtain a (G, T )- colouring, a contradiction. Hence rv 2 / ∈ E(G).
Suppose now that rv 3 / ∈ E(G). Let (G , T ) be the graph pair obtained from (G -{u, t 2 , v 2 }, T -{u, t 2 , v 2 }) by identifying v 3 and r. By minimality of (G, T ), there is a (G , T )-colouring, which is a (G -{u, t 2 , v 2 }, T -{u, t 2 , v 2 })-colouring c such that c(v 3 ) = 1. Set c(u) = 1. For t 2 , there at least two possible colours, namely the ones not in {1, 2, c(t 1 ), c(t 3 )}. One of them, say α, is such that

I = [α] ∪ {1, c(v 1 ), c(t 3 )}
is not equal to Z 6 . Thus, setting c(t 2 ) = α and choosing c(v 2 ) in Z 6 \ I, we obtain a (G, T )-colouring, a contradiction. Hence rv 3 ∈ E(G).

Assume that rv 3 is inside C f . Then t 2 t 3 / ∈ E(G). By minimality of (G, T ), there is a (G -{u, t 2 , v 2 } ∪ rv 1 , T {u, t 2 , v 2 })-colouring, which is a (G -{u, t 2 , v 2 }, T -{u, t 2 , v 2 })colouring c such that c(v 1 ) = 1. Thus, setting c(v 2 ) = 1 and colouring u with a colour in Z 6 \ ({1, c(v 1 } ∪ [c(t 1 )]) and t 1 with a colour in Z 6 \ {1, 2, c(t 1 ), c(u), c(v 3 )}, we obtain a (G, T )-colouring, a contradiction. Hence we may assume that rv 3 is outside C f . So, by planarity, t 1 t 3 / ∈ E(G). Let (G , T ) be the graph pair obtained from (G -{u, t 2 , v 2 }, T -{u, t 2 , v 2 }) by identifying t 1 and t 3 . By minimality of (G, T ), there is a (G , T )-colouring, which is a (G -{u,

t 2 , v 2 }, T -{u, t 2 , v 2 })-colouring c such that c(t 1 ) = c(t 3 ). Set c(u) = c(v 3 ). Let α be a colour of Z 6 \ {1, 2, c(t 1 ), c(v 3 )} such that I = [α] ∪ {c(v 1 ), c(v 3 ), c(t 3 )} is not Z 6 .
Then setting c(t 2 ) = α and choosing c(v 2 ) in Z 6 \ I, we obtain a (G, T )-colouring, a contradiction.

Assume that

C int e is A 3 . 3.1. Assume f = rv 1 . Then rv 2 is an edge. By minimality of G, there exists a (G - {u, t 2 , v 2 }, T -{u, t 2 , v 2 })-colouring c. Colour u with a colour c(u) in Z 6 \ ({1, c(v 1 )} ∪ [c(t 1 )]). Set c(t 2 ) = 6 if c(u) = 6
and c(t 2 ) = 5 otherwise. In both cases, at most five colours are forbidden for v 2 , and one can extend greedily the colouring into a (G, T )colouring, a contradiction.

3.2.

Assume that f = rv 2 . Then rv 1 is an edge. By minimality of G, there exists a (G -{u, t 1 , v 1 }, T -{u, t 1 , v 1 })-colouring c. Set c(t 1 ) = 6, then colour u with any colour in Z 6 \ {1, 5, 6, c(t 2 ), c(v 2 )} and v 1 with any colour in Z 6 \ {1, 5, 6, c(v 2 ), c(u)}. This yields a (G, T )-colouring, a contradiction.

Assume that

f = t 1 v 2 .
Since f is the sucessor of e, then the cycle t 1 v 1 v 2 is empty, and so v 1 contradicts Lemma 7. Similarly, if f = t 2 v 1 , then v 2 contradicts Lemma 7.

Assume that

f = v 1 t 3 with t 3 a twig distinct from t 2 .
Assume first that

t 2 t 3 ∈ E(G). Then rv 2 is not an edge. Set G = (G -{u, t 2 , v 2 }) ∪ rv 1 . By minimality of (G, T ), there is a (G , T -{u, t 2 , v 2 })-colouring which is a (G - {u, t 2 , v 2 }, T -{u, t 2 , v 2 })-colouring c such that c(v 1 ) = c(r) = 1. Setting c(v 2 ) = 1 and choosing c(u) in Z 6 \ ({1, c(v 1 )} ∪ [c(t 1 )]) and c(t 2 ) in Z 6 \ {1, 2, c(u), c(t 3 )}, we get a (G, T )-colouring, a contradiction. So t 2 t 3 / ∈ E(G) and thus rv 2 ∈ E(G).
By minimality of G, there exists a (G -{u, Colouring u with 6, v 2 with c(v 2 ) ∈ {3, 5} \ {c(t 3 )} and t 2 with c(t

t 2 , v 2 }, T -{u, t 2 , v 2 })-colouring c.
2 ) in {3, 5} \ [c(v 2 )],
we get a (G, T )-colouring, a contradiction.

3.5. Assume that f = v 2 t 3 with t 3 a twig distinct from t 1 .

Assume first that t 1 t 3 is an edge. Set G = (G -{u, t 1 , v 1 }) ∪ rv 2 . By minimality of (G, T ), there is a (G , T -{u,

t 1 , v 1 })-colouring which is a (G-{u, t 1 , v 1 }, T -{u, t 1 , v 1 })- colouring c such that c(v 2 ) = c(r) = 1. Set c(v 1 ) = 1. If c(v 2 ) = 2, then setting c(u) = 2
and assigning to t 1 a colour in Z 6 \ {1, 2, 3, c(t 3 )}, we obtain a (G, T )-colouring, a contradiction. So c(v 2 ) = 2 and c(t 2 ) ≥ 4. Setting c(u) = 3 and assigning to t 1 a colour in Z 6 \ {1, 2, 3, 4, c(t 3 )}, we obtain a (G, T )-colouring, a contradiction. Hence t 1 t 3 is not an edge.

So rv 1 is an edge. Since e is minimal, then rv 1 is not overstepping and C int rv 1 is empty. Let G be the graph from G -{u, t 1 , v 1 } by adding the edge t 2 t 3 if it does not exist. By minimality of (G, T ), there is a (G , T -{u,

t 1 , v 1 })-colouring which is a (G -{u, t 1 , v 1 }, T -{u, t 1 , v 1 })-colouring c such that c(t 2 ) = c(t 3 ). Set c(t 1 ) = 6. If c(t 2 ) / ∈ {5, 6}, then set c(v 1 ) = c(t 2 ) (this is possible because c(t 3 ) = c(t 2 )
), otherwise colour v 1 with any colour in Z 6 \ {1, 5, 6, c(t 3 ), c(v 2 )}. Then colouring u with a colour in Z 6 \ {1, 5, 6, c(v 1 ), c(v 2 )}, we get a (G, T )-colouring, a contradiction.

Assume that

f = v 2 v 3 with v 3 a leaf adjacent to t 1 . Set G = (G -{u, v 1 } ∪ {t 2 v 3 , rv 3 }. By minimality of (G, T ), there is a (G , T -{u, v 1 })-colouring which is a (G-{u, v 1 }, T - {u, v 1 })-colouring c such that c(v 3 ) / ∈ {c(r), c(t 2 ). Setting c(u) = c(v 3 ) and colouring v 1 with a colour in Z 6 \({c(u), c(v 2 )}∪[c(t 1 )])
, we obtain a (G, T )-colouring, a contradiction.

Assume that

f = v 1 v 3 with v 3 a leaf adjacent to t 2 . Then C int f = B 2 . Assume first that rv 3 ∈ E(G). Then t 1 t 2 /
∈ E(G). Let (G , T ) be the graph pair obtained from (G -u, T -u) by identifying t 1 and t 2 . By minimality of (G, T ), there is a (G , T )-colouring, which yields a (G-u, T -u)-colouring such that c(t 1 ) = c(t 2 ). Then setting c(u) = c(v 3 ), we obtain a (G, T )-colouring, a contradiction. Hence rv 3 / ∈ E(G).

Now assume that rv 1 / ∈ E(G). Let (G , T ) be the graph pair obtained from (G-u, T -u) by identifying v 1 and r. By minimality of (G, T ), there is a (G , T )-colouring, which yields a

(G -u, T -u)-colouring such that c(v 1 ) = 1. If c(t 1 ) = c(t 2 ), then, setting c(u) = c(v 3 ), we obtain a (G, T )-colouring, a contradiction. If c(t 1 ) = 6 or c(t 2 ) ∈ [c(t 1 )] or c(v 2 ) ∈ [c(t 1 )], then colouring u with a colour in Z 6 \ ({1, c(t 2 ), c(v 2 )} ∪ [c(t 1 ]), we obtain a (G, T )-colouring, a contradiction. So, assume that c(t 1 ) = 6 and c(t 2 ) / ∈ [c(t 1 )] and c(v 2 ) / ∈ [c(t 1 )]. If c(t 1 ) = 3, then c(t 2 ), c(v 2 ) ∈ {5, 6}, a contradiction. If c(t 1 ) = 5, then c(t 2 ), c(v 2 ) ∈ {2, 3}, a contradiction. Then, c(t 1 ) = 4, c(t 2 ) = 6 and c(v 2 ) = 2.
Recolouring v 2 with a colour in {3, 4} \ {c(v 3 )} and setting c(u) = 2, we obtain a (G, T )-colouring, a contradiction. Hence rv 1 ∈ E(G).

Assume

f = v 2 v 3 with v 3 a leaf adjacent in T to a twig t 3 not in {t 1 , t 2 }.
Assume first that rv 1 is not an edge. By minimality of (G, T ), there is a (G-{u,

t 1 , v 1 }∪ {rv 2 , rv 3 }, T -{u, t 1 , v 1 })-colouring which is a (G -{u, t 1 , v 1 }, T -{u, t 1 , v 1 })-colouring c such that c(v 2 ) = 1 and c(v 3 ) = 1. Colour v 1 with 1. Colour t 1 with a colour α in A = Z 6 \ {1, 2, c(t 3 ), c(v 3 )} such that [α] = Z 6 \ {1, c(t 2 ), c(v 2 )}. This is possible since |A| ≥ 2. Then colouring u with a colour in Z 6 \ ({1, c(t 2 ), c(v 2 )} ∪ [α]
), we obtain a (G, T )-colouring, a contradiction. Suppose now that rv 1 is an edge. Then t 1 t 3 and t 1 v 3 are not edges. By minimality of (G, T ), there is a (G -{u,

t 1 , v 1 } ∪ {t 2 t 3 , t 2 v 3 }, T -{u, t 1 , v 1 })-colouring which is a (G -{u, t 1 , v 1 }, T -{u, t 1 , v 1 })-colouring c such that c(t 3 ) = c(t 2 ) and c(v 3 ) = c(t 2 ). Set c(t 1 ) = 6. Let L(u) = {2, 3, 4} \ {t 2 , v 2 } and let L(v 1 ) = {2, 3, 4} \ {v 2 , t 3 , v 3 }. If L(v 1
) is empty, then c(t 3 ) = 4, c(v 3 ) = 2 and c(v 2 ) = 3. In this case, recolouring t 1 with 3, colouring u with a colour in {5, 6} \ {c(t 2 )} and colouring v 1 with a colour in {5, 6} \ {c(u)}, we obtain a (G, T )-colouring, a contradiction. Hence L(v 1 ) is not empty. If |L(u)| > 1, we can colour v 1 with a colour in L(v 1 ) and colour u with a colour in L(u) \ {c(v 1 )} to obtain a (G, T )-colouring, a contradiction. Then |L(u)| = 1 and consequently c(t 2 ) = 4 and c(v 2 ) = 2. Then colouring u with 3 and colouring v 1 with 4, we obtain a (G, T )-colouring, since c(t 3 ) and c(v 3 ) are distinct from c(t 2 ) = 4, a contradiction.

Assume

f = v 1 v 3 with v 3 a leaf adjacent in T to a twig t 3 not in {t 1 , t 2 }. Suppose first that rv 2 / ∈ E(G). By minimality of (G, T ), there is a (G -{t 2 , v 2 } ∪ {rv 1 , rv 3 }, T -{t 2 , v 2 })-colouring which is a (G -{t 2 , v 2 }, T -{t 2 , v 2 })-colouring c such that c(v 1 ) = 1 and c(v 3 ) = 1. Setting c(v 2 ) = 1 and choosing c(t 2 ) in Z 6 \ {1, 2, c(u), c(t 3 ), c(v 3 )} yields a (G, T )-colouring, a contradiction. Hence rv 2 ∈ E(G). Assume that v 2 t 3 / ∈ E(G). By minimality of (G, T ), there is a (G-{t 2 , v 2 }, T -{t 2 , v 2 })- colouring. We can choose c(v 2 ) in Z 6 \ {1, c(u), c(v 1 ), c(v 3 )} such that I = [c(v 2 )] ∪ {1, 2, c(u)} = Z 6 and c(t 2 ) ∈ Z 6 \ I to obtain a (G, T )-colouring, a contradiction. Hence v 2 t 3 ∈ E(G).
Now assume that rv 3 is not an edge. Let (G , T ) be the graph pair obtained from (G -{t 2 , v 2 }, T -{t 2 , v 2 }) by identifying v 3 and r. By minimality of (G, T ), there is a (G , T )-colouring, which yields a (G -{t 2 , v 2 }, T -{t 2 , v 2 })-colouring such that c(v 3 ) = 1. Then colouring v 2 with a colour α ∈ Z 6 \ {1, c(u), c(v 1 ), c(t 3 )} such that [α] ∪ {1, 2, c(u)} = Z 6 and colouring t 2 with a colour in Z 6 \ ([α] ∪ {1, 2, c(u)}), we obtain a (G, T )-colouring, a contradiction.

Hence, rv 3 is an edge and, since v 2 t 3 is an edge, t 1 t 3 is not an edge by planarity. Let (G , T ) be the graph pair obtained from (G -{u, t 2 , v 2 }, T -{u, t 2 , v 2 }) by identifying t 1 and t 3 . By minimality of (G, T ), there is a (G , T )-colouring, which yields a (G -{u,

t 2 , v 2 }, T -{u, t 2 , v 2 })-colouring such that c(t 1 ) = c(t 3 ). Then setting c(u) = c(v 3 ), colouring v 2 with a colour α ∈ Z 6 \{1, c(v 1 ), c(t 3 ), c(v 3 )} such that [α]∪{1, 2, c(u)} = Z 6 and colouring t 2 with a colour in Z 6 \ ([α] ∪ {1, 2, c(u)}), we obtain a (G, T )-colouring, a contradiction.
f in C int f , the edge f is v 1 v 2 , v 1 v 1 , v 2 v 2 or v 2 v 1 . Iff = v 2 v 1 ,
then swapping the names of e and e , we are left with f = v 1 v 2 . Hence we may assume that f ∈ {v

1 v 2 , v 1 v 1 , v 2 v 2 }. Note that if f = v 1 v 2 , then t 2 = t 1 and v 2 = v 1 , if f = v 1 v 1 , then t 2 = t 2 and v 2 = v 2 , and if f = v 2 v 2 , then t 1 = t 1 and v 1 = v 1 .
Observe that if C int e is isomorphic to A 1 , then f cannot be v 2 v 2 because rv 1 must be an edge that would cross f . Moreover if C int e and C int e are both isomorphic to A 1 , then f cannot be v 1 v 1 since G has no multiple edges. Hence must be in one of the following cases:

• C int e and C int e are isomorphic to A 1 and f = v 1 v 2 .
By minimality of G, there is a (G -{u , t 2 , v 2 }, T -{u , t 2 , v 2 })-colouring c. Colour t 2 with 6. If {c(u), c(v 1 ), c(v 2 )} = {2, 3, 4}, then colouring v 2 with a colour in Z 6 \ {1, 5, 6, c(u), c(v 1 ), c(v 2 )} and colouring u with a colour in {2, 3, 4} \ {c(v 2 ), c(v 2 )}, we obtain a (G, T )-colouring, a contradiction. If {c(u), c(v 1 ), c(v 2 )} = {2, 3, 4}, then recolouring t 2 with 3, and setting c(v 2 ) = 5 and c(u ) = 6, we obtain a (G, T )-colouring, a contradiction.

• C int e is isomorphic to A 1 , C int e is isomorphic to A 2 and f = v 1 v i for i ∈ {1, 2}. By minimality of (G, T ), there is a (G -{t 2 , v 2 , u } ∪ rv i , T -{t 2 , v 2 , u })-colouring which is a (G-{t 2 , v 2 , u }, T -{t 2 , v 2 , u })-colouring c such that c(v i ) = 1. Colouring u with 1, colouring v 2 with a colour α ∈ Z 6 \ {1, c(u), c(v 1 ), c(v i )} such that {1, 2, c(t i )} ∪ [α] = Z 6 and colouring t 2 with a colour in Z 6 \ ({1, 2, c(t i )} ∪ [α]), we obtain a G, T )-colouring, a contradiction. • C int e is isomorphic to A 1 , C int e is isomorphic to A 3 and f = v 1 v 2 . By minimality of (G, T ), there is a (G-{t 2 , v 2 , u }∪{ut 2 , v 1 t 2 }, T -{t 2 , v 2 , u })-colouring which is a (G-{t 2 , v 2 , u }, T -{t 2 , v 2 , u })-colouring c such that c(u) = c(t 2 ) and c(v 1 ) = c(t 2 ). If {c(u), c(v 1 ), c(v 2 )} = {2, 3, 4}
, then colour t 2 with 3, colour u with a colour in {5, 6} \ {c(t 2 )} and colour v 2 with a colour in {5, 6} \ {c(u )}. If 2 ∈ {c(u), c(v 1 ), c(v 2 )}, then set c(t 2 ) = 6, c(v 2 ) = 2 and colour u with a colour in {3, 4} \ {c(t 2 ), c(v 2 )}. If 4 ∈ {c(u), c(v 1 ), c(v 2 )}, then set c(t 2 ) = 6, c(v 2 ) = 4 and colour u with a colour in {2, 3}\{c(t 2 ), c(v 2 )}. In any of these cases, we obtain a (G, T )-colouring, a contradiction. So 2, 4 ∈ {c(u), c(v 1 ), c(v 2 )} and 3 ∈ {c(u), c(v 1 ), c(v 2 )}. Colour t 2 with 6 and v 2 with 3. Notice that {c(t 2 ), c(v 2 )} = {2, 4}, since necessarily c(t 2 ) = 4 and c(v 2 ) = 2, but c(u), c(v 1 ) = c(t 2 ) = 4 contradicts the fact that 2, 4 ∈ {c(u), c(v 1 ), c(v 2 )}. Then colouring u with {2, 4} \ {c(t 2 ), c(v 2 )}, we obtain a (G, T )-colouring, a contradiction.

• C int e is isomorphic to A 1 , C int e is isomorphic to A 3 and f = v 1 v 1 . By minimality of (G, T ), there is a (G-{u, t 2 , v 2 }∪{t 1 u , t 1 v 1 }, T -{u, t 2 , v 2 })-colouring which is a (G -{u, t 2 , v 2 }, T -{u, t 2 , v 2 })-colouring c such that c(u ) = c(t 1 ) and c(v 1 ) = c(t 1 ). Colour u with a colour in Z 6 \ ({1, c(v 1 )} ∪ [c(t 1 )]). If c(v 1 ) = 1 or c(v 1 ) = 1 or |{c(u), c(u ), c(v 1 ), c(v 1 )}| < 4, then colouring v 2 with a colour α ∈ Z 6 \ {1, c(u), c(u ), c(v 1 ), c(v 1 )} such that [α] ∪ {1, c(u )} = Z 6 and colouring c(t 2 ) with a colour in Z 6 \ ([α] ∪ {1, c(u )}), we obtain a (G, T )-colouring, a contradiction.
Then {c(u), c(v 1 )} ∩ {c(u ), c(v 1 )} = ∅. This is only possible if {c(t 1 ), c(t 1 )} = {3, 5}, {c(t 1 ), c(t 1 )} = {3, 6} or {c(t 1 ), c(t 1 )} = {4, 6}. If c(t 1 ) = 3, then {c(u ), c(v 1 )} = {5, 6} and, since c(u ) = c(t 1 ) and c(v 1 ) = c(t 1 ), c(t 1 ) ∈ {5, 6}. If c(t 1 ) = 4, then {c(u ), c(v 1 )} = {2, 6} and consequently c(t 1 ) ∈ {2, 6}. If c(t 1 ) = 5, then {c(u ), c(v 1 )} = {2, 3} and consequently c(t 1 ) ∈ {2, 3}. Then the only possibilities are (c(t 1 ), c(t 1 )) = [START_REF] Broersma | λ-backbone colorings along pairwise disjoint stars and matchings[END_REF][START_REF] Proskurowski | Efficient vertex and edge-coloring of outerplanar graphs[END_REF] or (c(t 1 ), c(t 1 )) = [START_REF] Bu | Backbone coloring of planar graphs without special circles[END_REF][START_REF] Proskurowski | Efficient vertex and edge-coloring of outerplanar graphs[END_REF]. In these cases, c(u ) = 6.

If (c(t 1 ), c(t 1 )) = [START_REF] Broersma | λ-backbone colorings along pairwise disjoint stars and matchings[END_REF][START_REF] Proskurowski | Efficient vertex and edge-coloring of outerplanar graphs[END_REF], then colouring t 2 with 6 and v 2 with a colour in {2, 3, 4} \ {c(u ), c(v 1 )}, we obtain a (G, T )-colouring, a contradiction. Then (c(t 1 ), c(t 1 )) = [START_REF] Bu | Backbone coloring of planar graphs without special circles[END_REF][START_REF] Proskurowski | Efficient vertex and edge-coloring of outerplanar graphs[END_REF]. Consequently, {c(u), c(v 1 )} = {2, 6} and, since {c(u), c(v 1 )} ∩ {c(u ), c(v 1 )} = ∅, {c(u ), c(v 1 )} = {3, 4}. This is a contradiction, since c(t 1 ) = c(u ) and c(t 1 ) = c(v 1 ).

• C int e is isomorphic to A 2 or A 3 , C int e is isomorphic to A 2 or A 3 and f = v 1 v 1 .
By minimality of (G, T ), there is a

(G -{u, u , t 2 , v 2 } ∪ {rv 1 , rv 1 }, T -{u, u , t 2 , v 2 })- colouring c which is a (G-{u, u , t 2 , v 2 }, T -{u, u , t 2 , v 2 })-colouring c such that c(v 1 ), c(v 1 ) = 1. Colour u with some colour in Z 6 \ ({1, c(v 1 )} ∪ [c(t 1 )]
) and u with some colour in Z 6 \ ({1, c(v 1 )} ∪ [c(t 1 )]). Then, colour v 2 with 1. If either t 2 is adjacent to at most one in {t 1 , t 1 } or {c(t 1 ), c(u), c(t 1 ), c(u )} = {3, 4, 5, 6}, then we can assign to t 2 a colour in {3, 4, 5, 6} not assigned to any of its neighbours to get a (G, T )-colouring, a contradiction.

So t 2 t 1 and t 2 t 1 are edges and {c(t 1 ), c(u), c(t 1 ), c(u )} = {3, 4, 5, 6}. By planarity, ru and ru are not edges and we can recolour u and u with 1. Then, colouring t 2 with a colour α ∈ Z 6 \ {1, 2, c(t 1 ), c(t 1 )} such that [α] ∪ {1, c(v 1 ), c(v 1 )} = Z 6 and colouring v 2 with a colour in Z 6 \([α]∪{1, c(v 1 ), c(v 1 )}), we obtain a (G, T )-colouring, a contradiction.

• C int e is isomorphic to A 2 or A 3 , C int e is isomorphic to A 2 or A 3 and f = v 2 v 2 .
By minimality of (G, T ), there is a

(G -{u, u , t 2 , v 2 } ∪ {rv 2 , rv 2 }, T -{u, u , t 2 , v 2 })- colouring which is a (G-{u, u , t 2 , v 2 }, T -{u, u , t 2 , v 2 })-colouring c such that c(v 1 ), c(v 1 ) = 1. Choose c(u) in {2, 3}\{c(v 2 ), c(t 2 )} and c(u ) in {2, 3}\{c(v 2 ), c(t 2 )} and set c(v 1 ) = 1.
If t 1 has at most one neighbour in {t 2 , t 2 } or {c(t 2 ), c(t 2 )} = {5, 6}, then we can colour t 1 with a colour in {5, 6} not appearing on any of its neighbours to get a (G, T )-colouring, a contradiction. Hence t 1 is adjacent to t 2 and t 2 (that is C int e and C int e ) are isomorphic to A 2 and {c(t 2 ), c(t 2 )} = {5, 6}. Recolouring u with c(t 2 ) and u with c(t 2 ) and colouring t 1 with 3, we obtain a (G, T )-colouring, a contradiction.

• C int e is isomorphic to A 2 or A 3 , C int e is isomorphic to A 2 or A 3 and f = v 1 v 2 .
By minimality of (G, T ), there exists a G -{u, u , t 2 , v 2 } ∪ {rv 1 , rv 2 }, T -{u, u , t 2 , v 2 })colouring c which is a (G-{u, u , t 2 , v 2 }, T -{u, u , t 2 , v 2 })-colouring such that c(v 1 ) = 1 and c(v 2 ) = 1. Set c(v 2 ) = 1 and colour u with some colour in Z 6 \ ({1, c(v 1 )} ∪ [c(t 1 )]), u with some colour in {2, 3} \ {c(t 2 ), c(v 2 )}. Note that the set F of forbidden colours for t 2 is the union of {1, 2, c(u)} ∪ [c(u )] and the set of colours of the neighbours of t 2 in {t 1 , t 2 }. Moreover F = Z 6 for otherwise we could colour t 2 with a colour in Z 6 \ F to obtain a (G, T )-colouring, a contradiction.

If c(u ) = 2, then, since |F | = 6, t 2 t 1 and t 2 t 2 are edges and {c(u), c(t 1 ), c(t 2 )} = {4, 5, 6}. Since |c(u) -c(t 1 )| ≥ 2, necessarily {c(t 1 ), c(u)} = {4, 6} and c(t 2 ) = 5. If c(t 1 ) = 6, then recolouring u with a colour in {2, 3} \ c(v 1 ) and assigning 4 to t 2 , we obtain a (G, T )-colouring, a contradiction. Hence c(t 1 ) = 4 and c(u) = 6. So c(v 1 ) = 2, and thus c(v 2 ) = 3. Then recolouring u and u with 1 and v 2 with 4 and setting c(t 2 ) = 6, we obtain a (G, T )-colouring, a contradiction. Now, suppose that c(u ) = 3. Then, since |F | = 6, two neighbours of t 2 in {u, t 1 , t 2 } are coloured 5 and 6. Assume that c(u) / ∈ {5, 6}, then t 2 t 1 and t 2 t 2 are edges and {c(t 1 ), c(t 2 )} = {5, 6}. Note that, in this case, c(v 1 ) ≤ 4 and c(v 2 ) ≤ 4. Recolour u and u with 1, v 2 with 6 and colour t 2 with 3 to get a (G, T )-colouring, a contradiction. Hence c(u) ∈ {5, 6}. Thus c(t 1 ) ≤ 4 and so c(t 2 ) ∈ {5, 6} and c(v 2 ) ≤ 4. Thus, t 2 t 2 is an edge and c(t 2 ) ∈ ({5, 6} \ {c(u)}). Recolour u with c(u). If t 1 / ∈ N (t 2 ) or c(t 1 ) = 3, colouring t 2 with 3 yields a (G, T )-colouring, a contradiction. So t 1 ∈ N (t 2 ) and c(t 1 ) = 3. Then, recolour u and u with 3 (note that c(v 1 ) ≥ 5 and c(v 2 = 3 as u was coloured 3) and t 2 with i ∈ {5, 6} \ {c(t 2 )}. This gives a (G, T )-colouring, a contradiction.

Lemmas 15 and 16 immediately imply the following.

Corollary 17 If f is a penultimate edge, then

C int f is isomorphic to B 1 or B 2 , and rv 1 ∈ E(G). Morever, if C int f = B 2 , rv 3 / ∈ E(G).

Antepenultimate edges

We first prove that no antepenultimate edge g has two penultimate predecessors f and f .

Lemma 18 Every antepenultimate edge has a unique penultimate predecessor.

Proof. By contradiction. Suppose that an antepenultimate edge g has two penultimate predecessors f and f . According to Corollary 17, C int f and C int f are isomorphic to one of the graphs B 1 and B 2 . Let us denote the vertices of C int f by their names in Figure 3 and the vertices of C int f by their names in Figure 3 augmented with a prime.

Since g, f and f are bounding the face incindent to g in C int g , the edge

g is v 1 v 1 , v 1 v 3 , v 3 v 3 or v 3 v 1 .
Since rv 1 and rv 1 are edges, then g = v 1 v 1 , for otherwise rv 1 would cross g.

First, suppose that C int f is isomorphic to B 1 , i.e., rv 2 ∈ E. By minimality of (G, T ), there is a ((G -{v

2 , v 3 }) ∪ {v 2 u, v 2 v 1 }, T -{v 2 , v 3 })-colouring, which is a (G -{v 2 , v 3 }, T -{v 2 , v 3 })- colouring such that c(v 2 ) / ∈ {c(u), c(v 1 )}. Setting c(v 2 ) = c(v 2
) and c(v 3 ) = 1 gives a (G, T )colouring, a contradiction.

The case C int f is isomorphic to B 1 is symmetric, so we may assume that both are C int e and C int e are isomorphic to B 2 . By minimality of (G, T ), there exists a (G -{v

2 , v 2 , v 3 , t 2 }, T - {v 2 , v 2 , v 3 , t 2 })-colouring. Set c(v 2 ) = c(v 2 ) = 1. Then, one can choose c(t 2 ) in L = Z 6 \ {1, 2, c(u), c(u )} such that I = [c(t 2 )]∪{1, c(v 1 ), c(v 1 )} = Z 6 because |L| ≥ 2.
Hence colouring v 3 with a colour in Z 6 \ I, we obtain a (G, T )-colouring, a contradiction.

From Lemma 18, for every antepenultimate edge g, g has only one predecessor f (which must be penultimate), or g has two predecessors: a penultimate edge f and an ultimate edge e . From Lemmas 15 and 14, C int f is B 1 or B 2 , and C int e is A 1 , A 2 or A 3 . To deal with theses cases, we need the following two auxiliary lemmas.

Lemma 19 Suppose that (G, T ) contains a configuration isomorphic to B 1 (see Figure 3). If there is a (G -{u, v 2 }, T -{u, v 2 })-colouring c satisfying one of the following conditions : Lemma 20 Suppose that (G, T ) contains a configuration isomorphic to B 2 (see Figure 3). If there is a (G -{u, v 2 }, T -{u, v 2 })-colouring c satisfying one of the following conditions :

(a) c(t 1 ) = c(t 2 ) and c(v 3 ) = 1; (b) c(t 1 ) = c(t 2 ) and (b1) c(t 1 ) = 6; or (b2) c(v 1 ) = c(t 2 ); or (b3) c(t 2 ) ∈ [c(t 1 )]. Then G has a (G, T )-colouring. Proof. Let L(u) = Z 6 \ {1, [c(t 1 )], c(t 2 ), c(v 1 )} and L(v 2 ) = Z 6 \ {[c(t 2 )], c(v 1
), c(v 3 )} be the set of colours available for u and v 2 respectively. Clearly L(v 2 ) = ∅. Observe that the conditions (a), (b1), (b2) and (b3) also imply that L

(u) = ∅. So, if |L(u)| ≥ 2, |L(v 2 )| ≥ 2 or L(u) = L(v 2 )
, one can choose distinct colours c(u) ∈ L(u) and c(v 2 ) ∈ L(v 2 ) to obtain a (G, T )-colouring. It is a simple matter to check that in each case these conditions are satisfied. Now we prove that the case of an antepenultimate edge g with a penultimate predecessor f and an ultimate predecessor e is impossible.

Lemma 21 Every antepenultimate edge has a unique predecessor.

Proof. By contradiction. Suppose that an antepenultimate edge g has two predecessors f and f . By Lemma 18, one of those is not penultimate. So, wihtout loss of generality, f is penultimate, and f is not. Hence f is minimal.

According to Corollary 17, C int f is isomorphic to B 1 or B 2 , and according to Lemma 14, C int f is isomorphic to some of A 1 , A 2 or A 3 . Let us denote the vertices of C int f by their names in Figure 3 and the vertices of C int f by their names in Figure 2 augmented with a prime. Since g, f and f are bounding the face incindent to g in C int g , the edge g is

v 1 v 1 , v 1 v 2 , v 3 v 1 or v 3 v 2 . Moreover, since rv 1 is an edge, rv 3 is not an edge if C int f is isomorphic to B 2 ,
and rv 1 is an edge if C int f is isomorphic to A 1 , we must be in one of the following cases:

• C int f is isomorphic to B 1 , C int f is isomorphic to A 2 or A 3 and g = v 1 v 2 . By minimality of (G, T ), there is a (G -{v 2 , t 2 , u , v 3 } ∪ {v 2 r}, T -{v 2 , t 2 , u , v 3 })- colouring c which is a (G -{v 2 , t 2 , u , v 3 }, T -{v 2 , t 2 , u , v 3 })-colouring such that c(v 2 ) = 1. Set c(v 3 ) = 1. Let L(t 2 ) ⊇ Z 6 \ {1, 2, c(t 2 )}, L(v 2 ) = Z 6 \ {1, c(u), c(v 1 )} and L(u ) = Z 6 \{1, c(t 2 ), c(v 2 )}. Clearly, there exists at most one i ∈ Z 6 such that L(u ) = [i] and at most one j ∈ Z 6 such that L(v 2 ) = [j]. Thus, as |L(t 2 )| ≥ 3, there exists k ∈ L(t 2 ) such that L(u ) \ [k] = ∅ and L(v 2 ) \ [k] = ∅. Setting c(t 2 ) = k and colouring u and v 2 by colours in L(u ) \ [k] and L(v 2 ) \ [k]
, respectively, we obtain a (G, T )-colouring, a contradiction.

• C int f is isomorphic to B 2 , C int f is isomorphic to A 2 or A 3 and g = v 1 v 2 . By minimality of (G, T ), there is a ((G -{v 2 , t 2 , v 3 , u }) ∪ {t 2 u, t 2 v 1 }, T -{v 2 , t 2 , v 3 , u })- colouring c which is a (G -{v 2 , t 2 , v 3 , u }, T -{v 2 , t 2 , v 3 , u })-colouring such that c(t 2 ) ∈ {c(u), c(v 1 )}. Suppose that t 2 t 2 ∈ E(G). If we can colour t 2 with β ∈ [c(v 1 )] ∪ {6}, then we can colour u with some colour in Z 6 \ ({c(t 2 ), c(v 2 )} ∪ [β]), v 3 with some colour in Z 6 \ ({c(u ), c(v 2 ), c(v 1 )} ∪ [β]) and v 2 with some colour in Z 6 \ ({c(v 3 ), c(u), c(v 1 )} ∪ [β]), a contradiction. So, there is no available colour in [c(v 1 )] ∪ {6} for t 2 ; that is, [c(v 1 )] ∪ {6} ⊆ {1, 2, c(u), c(t 2 )}. Since c(v 1 ) / ∈ {1, c(u), c(t 2 )}, we must have c(v 1 ) = 2 and {c(u), c(t 2 )} = {3, 6}. colour u with 2 (since v 2 ∈ N (v 1 ) we know that c(v 2 ) = c(v 1 )), v 2
with 1 and v 3 with c(t 2 ). Colour t 2 with 4 if c(u) = 3 and with 5 otherwise. This gives a (G, T )-colouring, a contradiction. Now, suppose that ru ∈ E(G). If c(u) = 6, then we can colour t 2 with 6 and u , v 3 and v 2 can be greedily coloured in this order, a contradiction; thus, c(u) = 6. Let

L(u ) = Z 6 \ {1, c(t 2 ), c(v 2 )} be the colours available for u ; note that if L(u ) = [i] for some i ∈ Z 6 then c(t 2 ) = 6 and c(v 2 ) = 2, a contradiction since c(t 2 ) = c(u).
Clearly, there exists β ∈ [c(v 1 )] \ {1, 2} so we can colour t 2 with β, u with any colour in L(u ) \ [β] (recall that L(u ) = [i] for all i ∈ Z 6 ). Then colour v 3 and v 2 greedily gives a (G, T )-colouring, a contradiction.

• C int f is isomorphic to B 1 or B 2 , C int f is isomorphic to A 2 or A 3 and g = v 1 v 1 . By minimality of (G, T ), there is a ((G -{t 2 , v 2 , v 3 }) ∪ {uv 1 , ru , rv 1 }, T -{t 2 , v 2 , v 3 }- colouring, which is a (G-{t 2 , v 2 , v 3 }, T -{t 2 , v 2 , v 3 })-colouring such that c(v 1 ), c(u ) = 1 and c(v 1 ) = c(u).
Suppose that we can colour t 2 with β ∈ [c(v 1 )] ∪ {6}. We know that there is at least one colour i ∈ Z 6 \ ({1, c(u), c(v 1 )} ∪ [β]) available for v 2 and at least one colour j ∈ Z 6 \ ({c(v 1 ), c(u ), c(v 1 )} ∪ [β]) available for v 3 . Since c(v 1 ) ∈ {1, c(u)}, then i = j and we can colour v 2 with i and v 3 with j to obtain a (G, T )-colouring, a contradiction.

So, suppose that the colours of

[c(v 1 )] ∪ {6} all appear in N (t 2 ){v 2 , v 3 }; since |([c(v 1 )] ∪ {6}) \ {1, 2}| ≥ 2,
• C int f is isomorphic to B 1 , C int f is isomorphic to A 1 and g = v 1 v 1 .
Let (G , T ) be the graph pair obtained from (G -{u, v 2 , t 2 , v 3 , u }, T -{u, v 2 , t 2 , v 3 , u }) by identifying t 1 and t 1 . By minimality of (G, T ), there exists a (G , T )-colouring which is a (G -{u, v 2 , t 2 , v 3 , u }, T -{u, v 2 , t 2 , v 3 , u }) -colouring such that c(t 1 ) = c(t 1 ). Set c(t 2 ) = 6 and c(u ) = c(v 1 ). Let L = {2, 3, 4} \ {c(v 1 ), c(v 1 )}.

If c(t 1 ) = 5, then choosing c(v 3 ) ∈ L, and applying Lemma 19, we obtain a (G, T )colouring, a contradiction. Hence c(t 1 ) = c(t 1 ) = 5.

If L = {4}, then we can choose c(v 3 ) ∈ L \ {4}, and apply Lemma 19 to get a (G, T )colouring, a contradiction. Hence {c(v 1 ), c(v 1 )} = {2, 3}. Now setting c(v 3 ) = 5, c(v 2 ) = 6, c(u) = c(v 1 ) and recolouring t 2 with 3, we obtain a (G, T )-colouring, a contradiction.

• C int f is isomorphic to B 1 , C int f is isomorphic to A 1 and g = v 3 v 1 . Let (G , T ) be the graph pair obtained from (G -{v 1 , v 2 , u, t 1 , u }, T -{v 1 , v 2 , u, t 1 , u }) by identifying t 2 and t 1 . By minimality of (G, T ), there exists a (G , T )-colouring which is a (G -{v 1 , v 2 , u, t 1 , u }, T -{v 1 , v 2 , u, t 1 , u })-colouring such that c(t 2 ) = c(t 1 ). Set c(t 1 ) = 6.

If c(t 2 ) = c(t ) = 6, then set c(u) = c(v 3 ). One can then greedily extend the colouring to v 1 , v 2 and u in this order, a contradiction.

If c(t 2 ) = 6, then one can choose c(v 1 ) ∈ [c(t 2 )] \ {5, 6}. This is valid since c(v 3 ) and c(v 1 ) are not in [c(t 2 )]. On can then greedily extend the colouring to v 2 , u and u in this order, a contradiction.

• C int f is isomorphic to B 2 , C int f is isomorphic to A 1 and g = v 3 v 1 . By minimality of (G, T ), there exists a (G -{t 1 , u, v 1 , v 2 } ∪ {rv 3 }, T -{t 1 , u, v 1 , v 2 })colouring c. Set c(v 2 ) = 1 and let L(v 1 ) = Z 6 \ {1, c(v 3 ), c(u ), c(v 1 )} be the colours available for v 1 .

If L(v 1 ) = {5, 6}, then colouring t 1 with 6, v 1 with some colour in L(v 1 ) \ {5, 6} and u with some colour in Z 6 \ {1, 5, 6, c(v 1 ), c(t 2 )}, we obtain a (G, T )-colouring, a contradiction.

If L(v 1 ) = {5, 6}, then c(u ), c(v 1 ) ∈ {2, 3, 4} and consequently c(t 1 ) ∈ {5, 6}. We can suppose that c(t 1 ) = 5 and c(v 3 ) = 4 for otherwise we can recolour u with c(v 3 ) and fall in the case L(v 1 ) = {5, 6}. So, {c(u ), c(v 1 )} = {2, 3} and c(t 2 ) ≥ 6. Setting c(t 1 ) = 3, c(u) = 5 and c(v 1 ) = 6, we obtain a (G, T )-colouring, a contradiction.

The next two lemmas prove that the case of an antepenultimate edge g with only one predecessor f , which must be penultimate, is also impossible. Lemma 22 prove for C int f = B 1 and Lemma 23 prove for C int f = B 2 .

Lemma 22 There is no antepenultimate edge g with only one penultimate predecessor f such that C int f is B 1 .

Proof. One of the endvertices of g must be v 1 or v 3 (see Figure 3). We now distinguish some cases depending on the possible endvertices of g. Proof. One of the endvertices of g must be v 1 or v 3 (see Figure 3). We now distinguish some cases depending on the possible endvertices of g.

(a) Assume g = v v 3 with v a leaf with twig t . Since rv 1 ∈ E(G), by planarity, t = t 1 . By minimality of (G, T ), there is a ((G -{t 1 , v 1 , u}) ∪ {t 2 v , t 2 t }, T -{t 1 , v 1 , u})(G , T )colouring which is a (G -{t 1 , v 1 , u}, T -{t 1 , v 1 , u})-colouring such that c(v ) = c(t 2 ) and c(t ) = c(t 2 ). Hence one can colour v 1 with c(t 2 ) and colour t 1 with a colour in Z 6 \([c(t 2 )]∪{1, 2}). From Lemma 20 (b2), we obtain a (G, T )-colouring, a contradiction.

(b) Assume g = t v 3 with t a twig. We can apply an argument similar to (a).

(c) Assume g = v 1 r. Since G is triangulated, the edge v 1 t 2 must exist. This is a contradiction, since f is the sucessor of e.

(d) Assume g = v 1 t 2 . Then v 3 is a leaf of degree at most 3, a contradiction from Lemma 7.

(e) Assume g = v 1 v with v a leaf adjacent to t 2 in T . Since f is the successor of v 1 v 3 , v 1 t 2 / ∈ E(G) and so v 2 v 3 ∈ E(G) because G is triangulated. Let (G , T ) be the graph pair obtained from (G -{v 3 }, T -{v 3 }) by identifying v 2 and v . By minimality of (G, T ), there is a (G , T )-colouring which is a (G -{v 3 }, T -{v 3 })-colouring such that c(v 2 ) = c(v ). Hence one can colour v 3 with a colour from Z 6 \ {[c(t 2 )], c(v 2 ), c(v 1 )} to obtain a (G, T )-colouring, a contradiction.

(f) Assume g = v 1 t with t = t 2 a twig. Let (G , T ) be the graph pair obtained from (G -{u, t 2 , v 2 , v 3 }, T -{u, t 2 , v 2 , v 3 }) by identifying t 1 and t . This is possible since t 1 t is not an edge by planarity. By minimality of (G, T ), there is a (G , T )-colouring which is a (G -{u, t 2 , v 2 , v 3 }, T -{u, t 2 , v 2 , v 3 })-colouring such that c(t ) = c(t 1 ). Let L(t 2 ) = Z 6 \{1, 2, c(t )}. If c(t 1 ) = 6, then, colouring v 3 with 1 and t 2 with a colour from L(t 2 ) \ {6}, and using Lemma 20 (b1), we obtain a (G, T )-colouring, a contradiction. So c(t 1 ) = 6, that is c(t 1 ) ∈ {3, 4, 5}. We can colour t 2 with a colour from [c(t 1 )] \ {c(t ), c(t 1 )} ⊆ L(v 2 ). By Lemma 20 (b3), there is a (G, T )-colouring, a contradiction.

(g) Assume g = v 1 v with v a leaf with twig t = t 2 . By minimality of (G, T ), there is a ((G -{u, t 2 , v 2 , v 3 }) ∪ {v 1 t }, T -{u, t 2 , v 2 , v 3 })(G , T )-colouring which is a (G -{u, t 2 , v 2 , v 3 }, T -{u, t 2 , v 2 , v 3 })-colouring such that c(v 1 ) = c(t ). If c(v 1 ) = 2, we can colour t 2 with c(v 1 ), since c(t ), c(v ) = c(v 1 ). Then, colouring v 3 with a colour from Z 6 \ {[c(v 1 )], c(t ), c(v )}, and applying Lemma 20 (b2), we obtain a (G, T )-colouring, a contradiction. So, c(v 1 ) = 2.

Figure 3 :

 3 Figure 3: Configurations B 1 and B 2

  we obtain a (G, T )-colouring, a contradiction. Hence we may suppose that c(t 1 ) = 6. If v 2 t 3 / ∈ E(G), then setting c(v 2 ) = 6 and choosing c(t 2 ) ∈ {3, 4} \ c(v 3 ) and c(u) in Z 6 \ {1, 5, 6, c(v 1 )} yields a (G, T )-colouring, a contradiction. If v 2 t 3 ∈ E(G), then setting c(v 2 ) = 5, c(t 2 ) = 3 and choosing c(u) in Z 6 \ {1, 5, 6, c(v 1 )} yields a (G, T )-colouring, a contradiction.

Assume that c(v 1 ) = 2 .

 12 If c(t 1 ) = 3, then setting c(v 2 ) = 2 and choosing c(u) in Z 6 \ {1, 2, 3, 4, c(v 1 )} and c(t 2 ) in Z 6 \{1, 2, 3, c(u)} yields a (G, T )-colouring, a contradiction. If c(t 1 ) ≥ 4, then setting c(u) = 2 and choosing c(v 2 ) in Z 6 \ {1, 2, c(v 1 ), c(t 3 )} and c(t 2 ) in Z 6 \ ({1, 2} ∪ [c(v 2 )]), we obtain a (G, T )-colouring, a contradiction. Hence c(v 1 ) = 2.If c(t 1 ) = 4, then colouring v 2 with c(v 2 ) ∈ {4, 6}\{c(t 3 )}, t 2 with c(t 2 ) ∈ {4, 6}\{c(v 2 )} and u with c(u) in {3, 5}\[c(t 1 )], we get a (G, T )-colouring, a contradiction. So c(t 1 ) = 4.

Lemma 16

 16 Every penultimate edge has a unique predecessor. Proof. By contradiction. Suppose that a penultimate edge f has two predecessors e and e . Then e and e are ultimate and so minimal. According to Lemma 14, C int e and C int e are isomorphic to some of A 1 , A 2 or A 3 . Let us denote the vertices of C int e by their names in Figure 2 and the vertices of C int e by their names in Figure 2 augmented with a prime. Since f , e and e are bounding the face incindent to

  (a) c(t 2 ) = 6 and (c(t 1 ), c(v 3 )) = (5, 4); (b) c(v 3 ) = 1 and c(t 1 ) = c(t 2 );Then there is a (G, T )-colouring.

  Proof. Let L(u) = Z 6 \([c(t 1 )]∪{1, c(v 1 )}) and L(v 2 ) = Z 6 \([c(t 2 )]∪{1, c(v 1 ), c(v 3 )}) be the set of colours available for u and v 2 respectively. Clearly L(u) = ∅. Observe that the conditions (a) and (b) also imply thatL(v 2 ) = ∅. So, if |L(u)| ≥ 2, |L(v 2 )| ≥ 2 or L(u) = L(v 2 ), one can choose distinct colours c(u) ∈ L(u) and c(v 2 ) ∈ L(v 2) to obtain a (G, T )-colouring. It is a simple matter to check that in both cases these conditions are satisfied.

  t 2 must be adjacent to at least one of u and t 1 . Assume first t 2 t 1 ∈ E. Then recolour u with 1. If ut 2 / ∈ E or [c(v 1 )] ∪ {6} ⊆ {1, 2, c(u), c(t 1 )}, note that we can apply the same argument as before since it holds even if c(u ) = 1; so suppose otherwise. In this case we must have: either (a) c(v 1 ) = 6, c(u) = 5 and c(t 1 ) = 6; or (b) c(v 1 ) = 2 and {c(u), c(t 1 ) = {3, 6}. colour v 2 with 1. If (a) occurs, then colour t 2 with 3 and v 3 with 5; if (b) occurs and c(t 1 ) = 6, then colour t 2 with 4 and v 3 6; if (b) occurs and c(t 1 ) = 3, then colour t 2 with 5 and v 3 with 3. Hence t 2 t 1 / ∈ E, and so t 2 u ∈ E. The possible situations are: (c) c(v 1 ) = 6, c(u) = 5 and c(u ) = 6; or (d) c(v 1 ) = 2 and {c(u), c(u )} = {3, 6}. If (c) occurs, then colour v 3 with {2, 5} \ {c(v 1 )} and t 2 with {3, 4} \ [c(v 3 )]. If (d) occurs, then colour v 3 with c(u) (recall that c(v 1 ) = c(u)) and t 2 with {4, 5} \ [c(v 3 )]. In both cases we get a (G, T )-colouring, a contradiction.

that c(t 1 )

 1 = c(t ). If {c(v 1 ), c(v )} = {2, 3}, then one can choose c(v 3 ) in {2, 3} \ {c(t ), c(v ), c(v 1 )}. Then setting c(t 2 ) = 6 and applying Lemma 19 (a), we obtain a (G, T )-colouring, a contradiction. Thus {c(v 1 ), c(v )} = {2, 3}, and so c(t 1 ) ≥ 5. Setting c(u) = c(v ), c(t 2 ) = 3 and choosing c(v 3 ) in {5, 6} \ c(t ) and c(v 2 ) in {5, 6} \ c(v 3 ) yields a (G, T )-colouring, a contradiction.Lemma 23 There is no antepenultimate edge g with only one penultimate predecessor f such that C int f is B 2 .

  then one can greeedily extend c to v 2 and then u to get a (G, T )-colouring, a contradiction. If c(t 1 ) = 6, then colouring v 2 with a colour in {c(t 1 ) -1, c(t 1 ) + 1} \ [c(t 2 )] and u with a colour in Z 6 \ ({1, c(v 1 )} ∪ [c(t 1 )]) we obtain a (G, T )-colouring, a contradiction. 1.3. Assume that f = v 1 t 3 with t 3 a twig distinct from t 2 . Since rv 1 is an edge, t 1 t 3 is not an edge. Let G be the graph pair obtained from(G -{t 2 , v 2 }, T -{t 2 , v 2 }). If one can colour v 2 with a colour c(v 2 ) in {2, 3, 6}, then {1, 2} ∪ [c(v 2 )] has cardinality at most 4 and so at most 5 colours are forbidden in t 2 . Hence one can extend c into a (G, T )-colouring , a contradiction. So we may assume that {c

  Assume f = rv 1 . Since f is the successor of e, then v 1 t 2 is not an edge and sorv 2 ∈ E(G) because G is triangulated. By minimality of G, there exists a (G -{u, t 2 , v 2 }, T -{u, t 2 , v 2 })-colouring c. Setting c(u) = 1,one can then extend c greedily to t 2 and v 2 to get a (G, T )-colouring, a contradiction.2.2. Assume thatf = rv 2 . By minimality of (G, T ), there is a (G-{u, t 1 , v 1 }, T -{u, t 1 , v 1 })-colouring. Setting c(u) = 1, one can then extend c greedily to t 1 and v 1 to get a (G, T )-colouring, a contradiction.2.3 Assume thatf = t 1 v 2 .Since f is the sucessor of e, the cycle t 1 v 1 v 2 is empty, an so v 1 contradicts Lemma 7. Similarly, if f = t 2 v 1 , then v 2 contradicts Lemma 7.

	2. Assume that C int e	is A 2 .
	2.1.

2.4. Assume that f = v 1 t 3 with t 3 a twig distinct from t 2 . Since f is the sucessor of e, t 2 v 1 is not an edge. Then either rv 2 is an edge or t 2 t 3 is an edge

Partly supported by the French Agence Nationale de la Recherche under Grant GRATEL ANR-09-blan-0373-01.

(a) Assume g = v v 3 with v a leaf with twig t . Since rv 1 ∈ E(G), by planarity, t = t 1 .

Let (G , T ) be the graph pair obtained from (G -{t 1 , v 1 , u, v 2 }, T -{t 1 , v 1 , u, v 2 }) by identifying t and t 2 . By minimality of (G, T ), there is a (G , T )-colouring which is a (G -{t 1 , v 1 , u, v 2 }, T -{t 1 , v 1 , u, v 2 })-colouring such that c(t ) = c(t 2 ). Set c(v 2 ) = c(v ) and c(t 1 ) = 6.

If c(t ) ∈ {5, 6}, then setting c(u) = c(v 3 ) and choosing c(v 1 ) in {2, 3, 4} \ {c(v ), c(v 3 )}, we obtain a (G, T )-colouring, a contradiction.

we obtain a (G, T )-colouring, a contradiction.

(b) Assume g = t v 3 with t a twig. We can apply an argument similar to (a) choosing

(c) Assume g = v 1 r. Since G is triangulated, the edge v 1 t 2 must exist. This is a contradiction, since f is the sucessor of e.

(d) Assume g = v 1 t 2 . Then v 3 is a leaf of degree at most 3, a contradiction from Lemma 7.

(e) Assume g = v 1 v with v a leaf with twig t 2 . Let (G , T ) be the graph pair obtained from (G-{v 3 }, T -{v 3 }) by identifying v 2 and v . By minimality of (G, T ), there is a

Assume first that rv 3 / ∈ E(G). By minimality of (G, T ), there is a

we can colour v 3 with 1. Then, by Lemma 19 (b), there is a (G, T )-colouring, a contradiction. Assume now that rv 3 ∈ E(G). Then t t 2 / ∈ E by planarity. Let (G , T ) be the graph pair obtained from (G -{u, t 2 , v 2 , v 3 }, T -{u, t 2 , v 2 , v 3 }) by identifying t 1 and t . By minimality of (G, T ), there is a (G , T )-colouring, which is a ((G -{u,

Then by Lemma 19 (a), there is a (G, T )-colouring, a contradiction.

(g) Assume g = v 1 v with v a leaf with twig t = t 2 . Since g is the succesor of f , v 1 t 2 is not an edge and v 1 r and v 1 t are not inside C g , so v 3 t ∈ E.

Assume first that rv 3 / ∈ E(G). By minimality of (G, T ), there is a ((G -{u,

we can colour v 3 with 1. Then, colouring t 2 with a colour from Z 6 {1, 2, c(t ), c(v ), c(t 1 )} and using Lemma 19 (b), we obtain a (G, T )-colouring, a contradiction. Assume now that rv 3 / ∈ E(G). Let (G , T ) be the graph pair obtained from (G -{u, t 2 , v 2 , v 3 }, T -{u, t 2 , v 2 , v 3 }) by identifying t 1 and t . By minimality of (G, T ), there is a (G , T )-colouring, which is a ((G -{u,

) has no three consecutive integers), and using Lemma 20 (b3), we obtain a (G, T )-colouring, a contradiction. Then L(v 2 ) ∩ ([c(t 1 )] \ {c(t 1 )}) = ∅. If c(t 1 ) = 3, then {c(t ), c(v )} = {4, 6}. In this case, colouring t 2 with 3, v 3 and u with 5 and v 2 with 6, we can obtain a (G, T )-colouring, a contradiction. If c(t 1 ) = 4, then {c(t ), c(v )} = {3, 5}, and if c(t 1 ) = 5, then {c(t ), c(v )} = {4, 6}. In both cases, setting c(t 2 ) = c(t 1 ), choosing c(v 3 ) in Z 6 \ {1, 2, [c(t 1 )]} and using Lemma 20 (a), we obtain a (G, T )-colouring, a contradiction.

Hence c(v ) = 1. If c(t 1 ) ∈ {3, 4}, colour t 2 with 3 (if c(t ) = 3) or 4 (otherwise). If c(t 1 ) = 5, colour t 2 with 6 (if c(t ) = 6) or 5 (otherwise). These cases satisfy the conditions c(t 2 ) ∈ [c(t 1 ] and Z 6 \ {1, 2, c(t ), [c(t 2 )]} = ∅. Then, colouring v 3 with a colour from Z 6 \ {1, 2, c(t ), [c(t 2 )]}, and using Lemma 20 ((a) or (b3)), we obtain (G, T )-colouring, a contradiction.

Lemmas 18, 21, 22 and 23 directly imply the following.

Corollary 24 (G, T ) has no antepenultimate edges.