, Now by Lemma 8, there is at least one big vertex outside of S that has a neighbour in S. Note that if there are at least two of these vertices, or if one of them has at least two neighbours in S

, Therefore S is a bud. In this case, S ends up with a charge of at least ?. We will

, For every big vertex v, v gives 1 ? 2 to each of its sons, does not give anything to its father (if it has one), and gives 1? 2 to its other 2-neighbours

, The common pot gives to every internal 2-vertex

, Every vertex has non-negative charge at the end of the procedure, Lemma, vol.17

Note that by what precedes every small 3 +-vertex v has non-negative charge. Every 2-vertex that is not in L receives 1? 2 from each of its neighbours. Every light 2-vertex that is not adjacent to a 2-vertex (i.e. every 2-vertex of L that is not an internal 2-vertex) receives 1 ? 2 from its father and from its other neighbour ,

Every internal 2-vertex receives 1 ? 2 from its father and from the common pot ,

, Let c(v) be the initial charge of v, and c (v) be the final charge of v. Suppose by contradiction that c (v) < 0. By Lemma 9, vertex v has at most k ? 1 sons. Moreover, if v has k ? 1 sons, then its last neighbour is either the father of v

, ? 1 sons, then v gives 1 ? 2 to each of its k ? 1 sons, and 2(k ? d ? 1) to the common pot, therefore c (v) = c(v) ? (1 ? 2)(k ? 1) + 2(k ? d ? 1), and thus as c (v) < 0

By Lemma 16, this charge is at least times the number of internal 2-vertices. The common pot gives to each internal 2-vertex, therefore it has non-negative charge at the end of the procedure, the electronic journal of combinatorics, vol.25, issue.1, 2018. ,

Every planar map is four colorable. Part 1: Discharging, Illinois Journal of Mathematics, vol.21, pp.429-490, 1977. ,

Every planar map is four colorable. Part 2: Reducibility, Illinois Journal of Mathematics, vol.21, pp.491-567, 1977. ,

A proof of Grünbaum's conjecture on the acyclic 5-colorability of planar graphs (Russian), Dokl. Akad. Nauk SSSR, vol.231, issue.1, pp.18-20, 1976. ,

On the partition of a planar graph of girth 5 into an empty and an acyclic subgraph (Russian), Diskretnyi Analiz i Issledovanie Operatsii, vol.8, issue.4, pp.34-53, 2001. ,

Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k, Journal of Graph Theory, vol.65, issue.2, pp.83-93, 2010. ,

URL : https://hal.archives-ouvertes.fr/hal-00377372

Vertex partitions of sparse graphs into an independent vertex set and subgraph of maximum degree at most one (Russian), Siberian Mathematical Journal, vol.52, pp.796-801, 2011. ,

Defective 2-colorings of sparse graphs, Journal of Combinatorial Theory, Series B, vol.104, pp.72-80, 2014. ,

A complexity dichotomy for the coloring of sparse graphs, Journal of Graph Theory, vol.73, issue.1, pp.85-102, 2013. ,

URL : https://hal.archives-ouvertes.fr/lirmm-00736468

How to orient the edges of a graph, In Combinatorics, I, Colloq. Math. Soc. János Bolyai, vol.18, pp.353-364, 1978. ,

Improper coloring of sparse graphs with a given girth, I:(0, 1)-colorings of triangle-free graphs, European Journal of Combinatorics, vol.42, pp.26-48, 2014. ,

Near-colorings: Non-colorable graphs and npcompleteness, The Electronic Journal of Combinatorics, vol.22, issue.1, 2015. ,

URL : https://hal.archives-ouvertes.fr/lirmm-01263770

On the linear vertex-arboricity of a plane graph, the electronic journal of combinatorics, vol.14, issue.1, pp.73-75, 1990. ,