# Partitioning edges of a planar graph into linear forests
and a matching

Marthe Bonamy LaBRI, University of Bordeaux, France Jadwiga Czyżewska
University of Warsaw, Poland Łukasz Kowalik22footnotemark: 2 Michał
Pilipczuk22footnotemark: 2

###### Abstract

We show that the edges of any planar graph of maximum degree at most $9$ can
be partitioned into $4$ linear forests and a matching. Combined with known
results, this implies that the edges of any planar graph $G$ of odd maximum
degree $\Delta\geq 9$ can be partitioned into $\tfrac{\Delta-1}{2}$ linear
forests and one matching. This strengthens well-known results stating that
graphs in this class have chromatic index $\Delta$ [Vizing, 1965] and linear
arboricity at most $\left\lceil(\Delta+1)/2\right\rceil$ [Wu, 1999].

##  1 Introduction

A linear forest is a forest in which every connected component is a path. The
linear arboricity ${\rm la}(G)$ of a graph $G$ is the minimum number of linear
forests in $G$, whose union is the whole $G$. The parameter was introduced by
Harary [8] in 1970 and determining its value for various graph classes is a
vital area of research by today.

Note that since matchings are linear forests, linear arboricity lies between
the chromatic index (partitioning into matchings) and the arboricity
(partitioning into forests). The connection with chromatic index can be deeper
than it seems, namely it is conjectured that linear arboricity enjoys an
analogue of Vizing’s theorem. This analogue is called Linear Arboricity
Conjecture [1, 3] and states that for every graph $G$, we have
$\left\lceil\tfrac{\Delta}{2}\right\rceil\leq{\rm
la}(G)\leq\left\lceil\tfrac{\Delta+1}{2}\right\rceil$ (the lower bound being
trivial). The conjecture has been proved for $\Delta\in\\{3,4,5,6,8,10\\}$ [1,
2, 6, 7], for complete bipartite graphs [1], for planar graphs [11, 12] and
recently for 3-degenerate graphs [4].

In this paper we focus on planar graphs. Cygan et al. [5] proved the following
theorem.

######  Theorem 1 ([5]).

For any planar graph $G$ with maximum degree $\Delta\geq 9$, we have ${\rm
la}(G)=\lceil\tfrac{\Delta}{2}\rceil$.

They have posed the following conjecture.

######  Conjecture 1 (Planar Linear Arboricity Conjecture [5]).

For any planar graph $G$ of maximum degree $\Delta\geq 5$, we have ${\rm
la}(G)=\left\lceil\tfrac{\Delta}{2}\right\rceil$.

Note that Conjecture 1 implies the Vizing Planar Graph Conjecture [10],
stating that any planar graph $G$ of maximum degree $\Delta\geq 6$ has
chromatic index $\Delta$ (currently open only for $\Delta=6$).

The equality ${\rm la}(G)=\left\lceil\tfrac{\Delta}{2}\right\rceil$ holds for
all odd values of $\Delta$, which follows from the weaker upper bound ${\rm
la}(G)\leq\left\lceil\tfrac{\Delta+1}{2}\right\rceil$ [11, 12]. Clearly, the
odd case gives much more freedom, since then for each vertex $v$ there is at
least one linear forest which has at most one edge incident with $v$. The
motivating question of this work is Can we use this freedom to get an even
tighter result? More specifically, we conjecture the following.

######  Conjecture 2.

For every planar graph $G$ of odd maximum degree $\Delta\geq 7$ the edges of
$G$ can be partitioned into $\tfrac{\Delta-1}{2}$ linear forests and one
matching.

Note that Conjecture 2 cannot be extended to $\Delta\in\\{3,5\\}$. This is
because Conjecture 2 implies that the graph under consideration has chromatic
index $\Delta$ (color each linear forests with two colours and the matching
forms the last colour). However, the 4-clique and the icosahedron, each with
one edge subdivided, are well-known to have chromatic index $\Delta+1$ [10].

On the other hand, known results imply Conjecture 2 for $\Delta\geq 11$.
Indeed, pick a $\Delta$-edge colouring of $G$ which exists by a theorem of
Vizing [10]. Let $M$ be the matching formed by an arbitrary colour in the
colouring. Then $G-M$ has maximum degree $\Delta-1$, which is even. The claim
follows by combining the matching $M$ with the partition of $G-M$ into
$(\Delta(G)-1)/2$ linear forests, obtained using Theorem 1.

Thus, the only two missing cases of Conjecture 2 are $\Delta=7$ and
$\Delta=9$. In this work, we resolve the latter, as follows.

######  Theorem 2.

For any planar graph $G$ with maximum degree $\Delta(G)\leq 9$, we can
partition the edges of $G$ into four linear forests and a matching.

Note that Theorem 2 strengthens well-known results stating that graphs in this
class have chromatic index $\Delta$ [Vizing, 1965] and linear arboricity at
most $\left\lceil(\Delta+1)/2\right\rceil$ [Wu 1999]. By combining Theorem 2
with Theorem 1 and the argument for the case $\Delta\geq 11$ of Conjecture 2
described above, we get the following corollary.

######  Corollary 1.

Let $G$ be a planar graph with maximum degree $\Delta(G)\geq 9$. If
$\Delta(G)$ is even, the edges of $G$ can be partitioned into $\Delta(G)/2$
linear forests. If $\Delta(G)$ is odd, the edges of $G$ can be partitioned
into $(\Delta(G)-1)/2$ linear forests and a matching.

Theorem 2 is proved with the discharging method, by now a standard tool in
colouring of planar graphs. It can be sketched as follows. We find a set of 10
configurations which cannot appear in a minimal counterexample, i.e., are
reducible. Then, we show that Euler’s formula implies that a minimal
counterexample has to contain one of these configurations. Unfortunately, the
nature of our kind of colouring reveals much less symmetry than, for example,
edge colouring or ‘pure’ linear arboricity. This is because in our case a
colour forms either a linear forest or a matching. As a result, the
reducibility proofs for configurations become even more lengthy and tedious
than usual. This is why here we include traditional hand-made proofs for only
two configurations, while the reducibility of all the remaining ones is
verified by a computer program.

The program has been extensively tested for a number of configurations. We
compared results of two different implementations, one in C++, and another in
Python. The Python implementation (150 lines of code, excluding comments) was
optimized for readability and is publicly available in a Github repository
https://github.com/lkowalik/linear-arboricity. We give a detailed description
of the program in Section 4 (and in the comments included in the code).

##  2 Preliminaries

All graphs in this paper are simple, i.e., do not contain multiple edges or
loops. By a triangle we mean a cycle of length $3$.

For a graph $G$ and a vertex $v$ of $G$, by $d_{G}(v)$ we denote the degree of
$v$ in $G$, and we omit the subscript when it is clear from the context. A
vertex of degree $d$ is called a $d$-vertex. Notation $d^{+}$-vertex (resp.
$d^{-}$-vertex) means that this vertex is of degree at least (resp. at most)
$d$.

A neighbour of degree $d$ adjacent to a vertex $v$ is called a $d$-neighbour
of $v$. A neighbour of degree at least (resp. at most) $d$ to a vertex $v$ is
called a $d^{+}$-neighbour (resp. $d^{-}$-neighbour) of $v$. Given two
vertices $u$ and $v$, the vertex $u$ is a _weak neighbour_ (resp. _semi-weak_)
of $v$ if the edge $(u,v)$ belongs to exactly $2$ (resp. exactly $1$)
triangles.

As $\ell(f)$ we denote the number of edges incident to a face $f$. A face is
$big$ if $\ell(f)\geq 4$.

A facial walk $w$ corresponding to a face $f$ is the shortest closed walk
induced by all edges incident with $f$.

Let $f$ be a face and let $v_{0},v_{1},\ldots,v_{\ell}$ be the facial walk of
$f$, $v_{\ell}=v_{0}$. Then, for every $i=0,\ldots,\ell-1$, the triple
$s=(v_{i-1},v_{i},v_{i+1})$ will be called a $v_{i}$-segment or just segment
(indices considered modulo $\ell$). The length of $s$ is defined as the length
of $f$. We say that $v_{i}$ is incident to $s$. We stress that $v_{i-1}$,
$v_{i+1}$ are not incident to $s$. A _triangular segment_ is a segment
$s=(x,y,z)$ where $x$ and $z$ are connected with an edge.

Note that if $v$ is not a cutvertex, there is a one-to-one correspondence
between $v$-segments and faces incident to $v$. When $v$ is a cutvertex, a
$v$-segment $(x,v,y)$ can be thought of as a region of the face incident with
edges $vx$ and $vy$.

##  3 Proof of Theorem 2

Let $\mathcal{G}$ be a family of minimal counterexamples, i.e.,
$G\in\mathcal{G}$ if $G$ is a simple planar graph with $\Delta(G)\leq 9$ whose
edges cannot be partitioned into four linear forests and a matching and, among
such graphs, $G$ has the minimum possible number of edges.

###  3.1 Structure of a minimal counterexample

. We define configurations ($C_{\ref{c:edge}}$) to
($C_{\ref{c:2neighbour33bigface}}$) (see Figure 1).

  * •

($C_{\ref{c:edge}}$) is an edge $uv$ with $d(u)+d(v)\leq 10$.

  * •

($C_{\ref{c:kite}}$) is a triangular segment $(u,v,w)$ where $u$ has another
neighbour $x$ such that $d(v)=d(x)=11-d(u)$.

  * •

($C_{\ref{c:2degree2neighbours}}$) is a vertex with two $2$-neighbours.

  * •

($C_{\ref{c:2consweak3neighbours}}$) is a vertex $u$ with neighbors $x$, $y$,
$w$, $s$, $t$, where $d(y)=d(s)=3$, and $xywst$ is a path.

  * •

($C_{\ref{c:2weak3neighbours3neighbour}}$) is a vertex $u$ with three
$3$-neighbours, from which at least two are weak and $u$ is the only common
neighbour of any pair of weak $3$-neighbours of $u$.

  * •

($C_{\ref{c:weak3degree2}}$) is a vertex $u$ with both a weak $3$-neighbour
and a $2$-neighbour.

  * •

($C_{\ref{c:8weak3degree4}}$) is a vertex $u$ of degree $8$ with both a weak
$3$-neighbour and a $4$-neighbour.

  * •

($C_{\ref{c:smalltriangles}}$) is a triangle $(u,v,w)$ where $d(u)\leq 5$,
$d(v)\leq 6$, $d(w)\leq 8$.

  * •

($C_{\ref{c:23triangles-3}}$) is a vertex $u$ with a $3$-neighbours $w$ and
$z$, a $2$-neighbour $x$, and a neighbor $y$ which is adjacent to both $z$ and
$x$.

  * •

($C_{\ref{c:2neighbour33bigface}}$) is a vertex $u$ with neighbors $v$, $x$,
$y$, $z$, $s$, $t$, where $d(v)=2$, $d(y)=d(s)=3$, $y$ and $s$ share a common
neigbour $z$ other than $u$, $x$ is adjacent to $y$ and $t$ is adjacent to
$s$.

$u$$v$$d(u)+d(v)\leq 10$ (a)

$u$$v$$w$$x$$d(v)=d(x)=11-d(u)$ (b)

2$u$$v$2$w$ (c)

$u$$x$$3$$y$$w$$3$$s$$t$ (d)

$u$$x$$3$$y$$w$$z$$3$$s$$t$3 (e)

$u$$x$$3$$y$$z$2$w$ (f)

8$u$$x$$3$$y$$z$4$w$ (g)

$5$$u$$6$$v$$8$$w$ (h)

3$w$$u$$2$$x$$y$3$z$ (i)

2$v$$u$$x$$3$$y$$z$$3$$s$$t$ (j)

Figure 1:  Reducible configurations. The vertices drawn above are pairwise
different.

We stress here that configurations are defined as graphs (think: subgraphs of
$G\in\mathcal{G}$) and not as plane embeddings of graphs. Hence, for example
when we write that $G$ contains ($C_{\ref{c:kite}}$) it does not imply that
the triangle $(u,v,w)$ bounds a triangular face.

We now present human-made proofs that configurations ($C_{\ref{c:edge}}$) and
($C_{\ref{c:2degree2neighbours}}$) are reducible. In these proofs we use some
common notation as follows. We treat partitions to linear forests and a
matching as colourings, i.e., functions $c:E(G)\rightarrow\\{0,\ldots,4\\}$
such that for $i=1,\ldots,4$ we have that $c^{-1}(i)$ is a linear forest and
$c^{-1}(0)$ is a matching. By $d_{i}(c,v)$ we denote the number of edges which
are incident with $v$ and coloured with $i$ in the colouring $c$.

######  Lemma 1.

For every $G\in\mathcal{G}$, graph $G$ does not contain configuration
($C_{\ref{c:edge}}$).

###### Proof.

Assume for a contradiction that there is an edge $uv$ such that $d(u)+d(v)\leq
10$. Let $G^{\prime}$ be the planar graph obtained from $G$ by removing edge
$uv$. Since $G$ is a minimal counterexample, there is a colouring $c^{\prime}$
of $G^{\prime}$.

Now we extend $c^{\prime}$ to a colouring $c$ of $G$ to get a contradiction.
There are two cases to consider. If there is a colour $i\in\\{1,2,3,4\\}$ such
that $d_{i}(c^{\prime},u)+d_{i}(c^{\prime},v)\leq 1$ we put $c(uv)=i$. Then
$d_{i}(c,u)=1$ and $d_{i}(c,v)\leq 2$ or vice versa, so the edges of colour
$i$ still form a collection of paths, and $c$ is as desired. Hence we can
assume that for every colour $i\in\\{1,2,3,4\\}$ we have
$d_{i}(c^{\prime},u)+d_{i}(c^{\prime},v)=2$. Then, since
$d_{G^{\prime}}(u)+d_{G^{\prime}}(v)\leq 8$ we get that
$d_{0}(c^{\prime},u)=d_{0}(c^{\prime},v)=0$. We simply put $c(uv)=0$. ∎

######  Corollary 2.

For every $G\in\mathcal{G}$, graph $G$ does not contain $1$-vertices.

###### Proof.

Immediate from Lemma 1, since $\Delta(G)\leq 9$. ∎

######  Lemma 2.

For every $G\in\mathcal{G}$, if graph $G$ does not contain
($C_{\ref{c:kite}}$), then $G$ does not contain configuration
($C_{\ref{c:2degree2neighbours}}$).

###### Proof.

$v$$2$$y$$2$$x$$a=b$ (a)

$a$$2$$x$$v$$2$$y$$b$ (b)

Figure 2:  Two possible cases when configuration
($C_{\ref{c:2degree2neighbours}}$) appears.

Suppose for a contradiction that a vertex $v$ has two $2$-neighbours namely
$x$ and $y$. Let $a$ (resp. $b$) be the neighbour of $x$ (resp. $y$) different
than $v$. Note that $a$ may coincide with $b$ (see Fig. 2).

We consider two cases.

  1. 1.

$a=b$

Consider $G^{\prime}=(G-x)\cup\\{av\\}$. Note that
$d_{G^{\prime}}(v)=d_{G}(v)=9$, as ($C_{\ref{c:edge}}$) is excluded in $G$.
Moreover, $G^{\prime}$ is simple, because if $av\in E(G)$, then $G$ contains
($C_{\ref{c:kite}}$) (triangle $(v,x,a)$ and edge $vy$). By the minimality of
$G$ there exists a colouring $c^{\prime}$ of $G^{\prime}$. Now we define a
colouring $c$ of $G$. For every edge $e\in E(G)\setminus\\{ax,\ ay,\ vx,\
vy\\}$ we put $c(e)=c^{\prime}(e)$. Let $\alpha$, $\beta$, $\gamma$ be the
colours in $c^{\prime}$ of $ay$, $yv$, $av$ respectively. We put
$c(ay)=\alpha$, $c(yv)=\gamma$, $c(ax)=\gamma$ and $c(xv)=\beta$. Note that
$d_{i}(c^{\prime},v)=d_{i}(c,v)$ and $d_{i}(c^{\prime},a)=d_{i}(c,a)$ for
$i=0,\ldots,4$. Moreover, $d_{i}(c,x)$, $d_{i}(c,y)$ are not greater than $2$
for $i=1,\ 2,\ 3,\ 4$ and $d_{0}(c,x)$, $d_{0}(c,y)$ are not greater than $1$,
as otherwise $c^{\prime}$ contains incident edges coloured with $0$. Hence, it
suffices to show that there is no monochromatic cycle in $c$.

Assume there is a monochromatic cycle $C$ in $c$. Then $C$ contains one of the
edges of $ax$, $ay$, $bx$, $by$, because otherwise $C$ is monochromatic in
$c^{\prime}$, a contradiction. Since $d_{G}(x)=2$ and $d_{G}(y)=2$, it follows
that $C$ contains the path $axv$ or $ayv$. By symmetry assume the former. It
follows that $\beta=\gamma$ and $C$ is coloured by $\gamma$. Then $C$ contains
$vy$ (because $vy$ is coloured by $\gamma$). Since $d_{G}(y)=2$, also $ya\in
C$. Hence, $\alpha=\gamma$. Thus, we obtained that $\alpha=\beta=\gamma$ and
the triangle $ayv$ was monochromatic in $c^{\prime}$, a contradiction.

  2. 2.

$a\neq b$

Since we excluded configuration ($C_{\ref{c:edge}}$), $d(v)=9$. Note that $G$
contains neither edge $av$ nor $vb$ as we excluded configuration
($C_{\ref{c:kite}}$). Consider a simple graph
$G^{\prime}=G\setminus\\{x,y\\}\cup\\{av,\ vb\\}$. By the minimality of $G$
there exists a colouring $c^{\prime}$ of $G^{\prime}$. Now we define a
colouring of $G$. For every edge $e\in E(G)\setminus\\{ax,\ xv,\ vy,\ yb\\}$
we put $c(e)=c^{\prime}(e)$. Let $\alpha$ and $\beta$ be the colours of $av$
and $vb$ respectively. We can put $c(ax)=\alpha,\ c(xv)=\beta,\ c(vy)=\alpha,\
c(yb)=\beta$. Note that $d_{i}(c^{\prime},v)=d_{i}(c,v),\
d_{i}(c^{\prime},a)=d_{i}(c,a),\ d_{i}(c^{\prime},b)=d_{i}(c,b)$ for
$i=0,\ldots,4$. Moreover, $d_{i}(c,x),\ d_{i}(c,y)$ are not greater than $2$
for $i=1,\ 2,\ 3,\ 4$ and $d_{0}(c,x),\ d_{0}(c,y)$ are not greater than $1$,
otherwise $c^{\prime}$ contains incident edges coloured with $0$.

We also claim that there is no monochromatic cycle in $c$. Indeed, if there is
a cycle formed by edges in colour $\alpha$ (resp. $\beta$), then it goes
through $x$ and $y$, so $\alpha=\beta$ and there is a monochromatic cycle in
$c^{\prime}$, a contradiction.

∎

######  Lemma 3.

For every $G\in\mathcal{G}$, graph $G$ does not contain any of configurations
($C_{\ref{c:kite}}$) and ($C_{\ref{c:2consweak3neighbours}}$) to
($C_{\ref{c:2neighbour33bigface}}$).

###### Proof.

This proof is done by a computer program, see Section 4 for details. ∎

###  3.2 A minimal counterexample does not exist

Initial charge. We consider a planar embedding $\mathcal{M}=(V,E,F)$ of
$G\in\mathcal{G}$ and attribute a charge $\text{ch}(v)=d(v)-4$ to each vertex
$v$ and a charge $\text{ch}(f)=\ell(f)-4$ to each face $f$.

Discharging rules We introduce four discharging rules as follows:

  * •

Rule • ‣ 3.2 applies to a vertex $u$ with a neighbour $v$ of degree $2$. Then
$u$ sends $1$ to $v$.

  * •

Rule • ‣ 3.2 applies to a vertex $u$ with a neighbour $v$ of degree $3$. Then
$u$ sends $\tfrac{1}{3}$ to $v$.

  * •

Rule • ‣ 3.2 applies to a face $f$ of length $5^{+}$ and its segment
$(x,y,z)$. If $d(x)=d(z)=3$, then $f$ sends $\tfrac{2}{3}$ to $y$ through
$(x,y,z)$. If $d(x)=2$ or $d(z)=2$, then $f$ sends $\tfrac{1}{2}$ to $y$
through $(x,y,z)$.

  * •

Rule • ‣ 3.2 applies to a vertex $u$ incident to a triangular face
$f=(v,u,w)$. Then $u$ sends $m(d(v),d(u),d(w))$ through segment $(v,u,w)$ to
$f$, as described in Table 1.

In Rule • ‣ 3.2 we send a charge from a face to segments and then they pass
the charge to vertices. This may look overcomplicated at the moment, but will
become handy in the proof.

| $a\leq 4$ | $a=5$ | $a=6$ | $a\geq 7$
---|---|---|---|---
| $b\leq 4$ | $b=5$ | $b\geq 6$
| $c=6$ | $c\geq 7$
$m(b,a,c)$ | $0$ | $\tfrac{1}{5}$ | $\tfrac{1}{3}$ | $\tfrac{1}{2}$ | $\tfrac{7}{15}$ | $\tfrac{2}{5}$ | $\tfrac{1}{3}$
Table 1: A table to define the weight redistribution by Rule • ‣ 3.2. We
consider $b\leq c$ and set $m(c,a,b)=m(b,a,c)$. Note that the case $b=c=5$ is
not used in Rule • ‣ 3.2, because this would mean that edge $vw$ contradicts
Lemma 1.

In what follows, we will show that for every face and for every vertex, the
final charge, after applying the rules, is non-negative.

######  Lemma 4.

Let $G$ be a graph belonging to the family $\mathcal{G}$ and let $\mathcal{M}$
be its planar embedding. Then, after applying the discharging rules to $G$,
for every face $f$ of $\mathcal{M}$ its final charge is non-negative.

###### Proof.

Let $f$ be a face of $\mathcal{M}$. Recall that by $\ell(f)$ we denote the
length of $f$. We consider following cases.

  * •

${\ell(f)=3}$

The initial charge of $f$ is $-1$. It receives the charge from vertices on its
boundary depending on their degree by Rule • ‣ 3.2. Consider a few subcases
depending on the sorted degree sequence of the vertices on $f$ (note that
these are the only possible triangles as we excluded ($C_{\ref{c:edge}}$)):

    * –

$(4^{-},7^{+},7^{+})$. The $7^{+}$ vertices send $\tfrac{1}{2}$ to $f$, so its
received charge is $2\cdot\tfrac{1}{2}=1$.

    * –

$(5,6,8^{-})$. These triangles are excluded by ($C_{\ref{c:smalltriangles}}$).

    * –

$(5,6,9)$. Then, $f$ receives $\tfrac{1}{5}+\tfrac{1}{3}+\tfrac{7}{15}=1$ from
its vertices.

    * –

$(5,7^{+},7^{+})$. Then, $f$ receives
$\tfrac{1}{5}+\tfrac{2}{5}+\tfrac{2}{5}=1$ from its vertices.

    * –

$(6^{+},6^{+},6^{+})$. Then, $f$ receives at least $3\cdot\tfrac{1}{3}=1$ from
its vertices.

In each case $f$ receives at least $1$, so its final charge is non-negative.

  * •

${\ell(f)=4}$

The initial and the final charge of $f$ is $0$, as it does not send or receive
any charge.

  * •

${\ell(f)=5}$

The initial charge of $f$ is $1$. Note that since ($C_{\ref{c:edge}}$),
($C_{\ref{c:2degree2neighbours}}$) and $1$-vertices are excluded, $f$ has
either two vertices of degree $3$ or at most one of degree $2$ on its
boundary. In these situations $f$ sends $\tfrac{2}{3}$ or at most
$2\cdot\tfrac{1}{2}$, respectively, by Rule • ‣ 3.2. In both cases its final
charge remains non-negative.

33 (a)

$2$ (b)

Figure 3:  $5$-faces sending any charge to vertices

  * •

${\ell(f)\geq 6}$

We will show the following claim.

######  Claim 1.

$f$ sends at most $\ell(f)/3$ of charge.

###### Proof.

Let us implement Rule • ‣ 3.2 in the following way.

> Face $f$ sends $\tfrac{1}{3}$ to every edge on its boundary. Next, for every
> edge $e=uv$ on the boundary of $f$ we do the following. Let $xuvy$ be a
> fragment of the facial walk of $f$. If $v$ is a $2$\- or $3$-vertex, $e$
> sends $\tfrac{1}{3}$ to $u$ through $(x,u,v)$. Similarly, if $u$ is a $2$\-
> or $3$-vertex, $e$ sends $\tfrac{1}{3}$ to $v$ through $(u,v,y)$. Otherwise,
> $e$ sends $\tfrac{1}{6}$ both to $u$ and $v$ through $(x,u,v)$ and
> $(u,v,y)$, respectively.

Note that every edge sends at most $\tfrac{1}{3}$ of charge, as
$3^{-}$-vertices cannot be connected by an edge, because ($C_{\ref{c:edge}}$)
is excluded. Hence, it suffices to show that for every segment $s=(u,v,w)$, if
$v$ fulfills the conditions from Rule • ‣ 3.2, then $v$ gets appropriate
charge from $s$. Indeed, if $d(u)=d(w)=3$, then $v$ gets $\tfrac{1}{3}$
through $s$ from both $uv$ and $vw$, so it gets $\tfrac{2}{3}$ as required.
Otherwise, $d(u)=2$ or $d(w)=2$, by symmetry assume the latter. Then, $v$ gets
$\tfrac{1}{3}$ through $s$ from $vw$ and at least $\tfrac{1}{6}$ from $vu$
through $s$, so $v$ gets at least $\tfrac{1}{2}$ through $s$, as required. ∎

Since the initial charge of $f$ is $\ell(f)-2$ and $\ell(f)-2-\ell(f)/3\geq 0$
whenever ${\ell(f)\geq 6}$, this concludes the proof of Lemma 4.

∎

######  Lemma 5.

Let $G$ be a graph belonging to the family $\mathcal{G}$. Then, after applying
the discharging rules to $G$, the final charge of every vertex $v$ is non-
negative.

###### Proof.

Let $v$ be a vertex of $G$. Let us state simple observations which follow from
the discharging rules, and will be used frequently in the remainder.

######  Observation 1.

Vertex $v$ sends nothing to incident non-triangular segments.

######  Observation 2.

Vertex $v$ sends at most $\tfrac{1}{2}$ to an incident triangular segment.

######  Observation 3.

Vertex $v$ sends at most $\tfrac{1}{3}$ to an incident triangular segment with
no $5^{-}$ vertices.

In what follows we consider cases depending on the degree of $v$.

Assume ${d(v)\leq 1}$. By Corollary 2 there are no vertices of this kind in
$G$.

Assume ${d(v)=2}$. The initial charge of $v$ is $-2$. By Rule • ‣ 3.2 $v$
receives $1$ from each of the two neighbours, and since it does not send any
charge, its final charge is $0$.

Assume ${d(v)=3}$. The initial charge of $v$ is $-1$. By Rule • ‣ 3.2 $v$
receives $\tfrac{1}{3}$ from each of the three neighbours, and since it does
not send any charge, its final charge is $0$.

Assume ${d(v)=4}$. The initial charge and the final charge of $v$ are equal to
$0$, as it does not send or receive any charge.

Assume ${d(v)=5}$. The initial charge of $v$ is $1$. Vertex $v$ sends charge
only to incident triangular segments by Rule • ‣ 3.2. Thus, each incident
segment to $v$ receives at most $\tfrac{1}{5}$ from $v$. Hence, $v$ sends at
most $5\cdot\tfrac{1}{5}=1$ and its final charge is non-negative.

Assume ${d(v)=6}$. The initial charge of $v$ is $2$. Vertex $v$ sends charge
only to incident triangular segments by Rule • ‣ 3.2. Thus, each segment
incident to $v$ receives at most $\tfrac{1}{3}$ from $v$. Hence, $v$ sends at
most $6\cdot\tfrac{1}{3}=2$ and its final charge is non-negative.

Assume ${d(v)=7}$. The initial charge of $v$ is $3$. Vertex $v$ sends charge
only to incident triangular segments by Rule • ‣ 3.2. We claim that $v$ is
incident to at most two triangular segments such that each contains a
$4$-vertex. Indeed, if $v$ is incident to a triangular segment containing a
$4$-vertex, $v$ cannot have another $4$-neighbour as the configuration
($C_{\ref{c:kite}}$) is excluded. Hence every such segment contains edge $vx$,
and there are at most two segments with this property.

By Rule • ‣ 3.2 $v$ sends $\tfrac{1}{2}$ to triangular segments containing a
$4$-vertex and at most $\tfrac{2}{5}$ to each of the remaining segments (by
($C_{\ref{c:smalltriangles}}$) the triangular segments $(7,6,5)$ are
excluded). Thus, $v$ sends at most $2\cdot\tfrac{1}{2}+(7-2)\tfrac{2}{5}=3$ to
the segments, so its final charge is non-negative.

Assume ${d(v)=8}$. The initial charge of $v$ is $4$. By ($C_{\ref{c:edge}}$)
$v$ cannot have $2$-neighbours, so $v$ passes the charge only to triangular
segments and $3$-vertices by Rule • ‣ 3.2 and Rule • ‣ 3.2. Let us consider
the following cases:

  1. 1.

There is a weak $3$-neighbour $a$.
By ($C_{\ref{c:kite}}$) and ($C_{\ref{c:8weak3degree4}}$) $v$ has no
$4^{-}$-neighbours apart from $a$. This observation and
($C_{\ref{c:smalltriangles}}$) imply that $v$ sends $\tfrac{1}{3}$ to $a$,
$\tfrac{1}{2}$ to each of the two incident triangular segments containing $a$
and at most $\tfrac{2}{5}$ to each of the remaining segments. Thus, $v$ sends
at most

$\tfrac{1}{3}+2\cdot\tfrac{1}{2}+\tfrac{2}{5}(8-2)=3\tfrac{11}{15}\leq 4.$

  2. 2.

There is a semi-weak $3$-neighbour $a$.
By ($C_{\ref{c:kite}}$) $v$ has no more $3$-neighbours. Since $a$ is the semi-
weak neighbour, $v$ is incident to at most $7$ triangular segments. Thus, $v$
sends at most

$\tfrac{1}{3}+\tfrac{1}{2}(8-1)=3\tfrac{5}{6}\leq 4.$

  3. 3.

There are no weak or semi-weak $3$-neighbours.
Let $k$ be the number of $3$-neighbours of $v$. For each such $3$-neighbour
$a$ there are exactly two non-triangular $v$-segments containing $a$. Since
every non-triangular $v$-segment contains at most two $3$-neighbours of $v$,
there are at least $k$ non-triangular $v$-segments, so $v$ sends at most:

$\tfrac{1}{3}k+\tfrac{1}{2}(8-k)=4-\tfrac{1}{6}k\leq 4.$

In each case $v$ sends at most $4$ to adjacent vertices and segments. Thus,
its final charge remains non-negative.

Finally, assume ${d(v)=9}$. The initial charge of $v$ is $5$. We consider
several cases:

Case 1 $v$ has no $2$-neighbours.
Let $n_{3_{1,0}}$ be the number of $3$-neighbours of $v$ which are not weak
and let $\mathcal{S}$ be the set of non-triangular $v$-segments. Recall that
no pair of $3$-neighbours of $v$ can be adjacent as ($C_{\ref{c:edge}}$) is
excluded. We claim that

$|\mathcal{S}|\geq\left\lceil\tfrac{n_{3_{1,0}}}{2}\right\rceil.$ (1)

Indeed, every non-weak $3$-neighbour belongs to at least one non-triangular
$v$-segment and each non-triangular $v$-segment contains at most two such
$3$-neighbours.
Let $n_{3_{2}}$ be the number of weak $3$-neighbours of $v$. By
($C_{\ref{c:2weak3neighbours3neighbour}}$) we have a bound $n_{3_{2}}\leq 2$.
We will consider three subcases depending on $n_{3_{2}}$.

Case 1.1 $n_{3_{2}}=0$
First, assume $n_{3_{1,0}}=8$. Then, $v$ has at most one $8^{+}$-neighbour, so
since ($C_{\ref{c:edge}}$) is excluded, $v$ is incident to at most two
triangular segments. In total $v$ sends at most

$8\cdot\tfrac{1}{3}+2\cdot\tfrac{1}{2}=3\tfrac{2}{3},$

which is smaller than the initial charge. Thus, assume $n_{3_{1,0}}\neq 8$.
Then $v$ sends at most $\tfrac{1}{3}n_{3_{1,0}}+\tfrac{1}{2}(9-|\mathcal{S}|)$
to adjacent vertices and segments, so its final charge is at least

$5-\tfrac{1}{3}n_{3_{1,0}}-\tfrac{1}{2}(9-|\mathcal{S}|)=\tfrac{1}{2}+\tfrac{1}{2}|\mathcal{S}|-\tfrac{1}{3}n_{3_{1,0}}\stackrel{{\scriptstyle\eqref{eq:facesbound}}}{{\geq}}\tfrac{1}{2}+\tfrac{1}{2}\left\lceil\tfrac{n_{3_{1,0}}}{2}\right\rceil-\tfrac{1}{3}n_{3_{1,0}}.$

For odd $n_{3_{1,0}}$ we get
$\tfrac{1}{2}+\tfrac{1}{2}\tfrac{n_{3_{1,0}}+1}{2}-\tfrac{1}{3}n_{3_{1,0}}=\tfrac{3}{4}-\tfrac{n_{3_{1,0}}}{12}$,
which is non-negative when $n_{3_{1,0}}\leq 9$. For even $n_{3_{1,0}}$, we get
$\tfrac{1}{2}+\tfrac{n_{3_{1,0}}}{4}-\tfrac{1}{3}n_{3_{1,0}}=\tfrac{1}{2}-\tfrac{n_{3_{1,0}}}{12}$.
Since $n_{3_{1,0}}\neq 8$ we are left with even $n_{3_{1,0}}\leq 6$ and then
$\tfrac{1}{2}-\tfrac{n_{3_{1,0}}}{12}\geq 0$, as required.

Case 1.2 $n_{3_{2}}=1$
Note that $n_{3_{1,0}}\leq 6$. Indeed, $v$ has nine neighbours, one of them is
a weak $3$-neighbour and by ($C_{\ref{c:edge}}$) the neighbours it shares with
$v$ have degree $8^{+}$.

######  Claim 2.

If $n_{3_{1,0}}=4$ the final charge of $v$ is non-negative.

###### Proof.

$v$$3$$3$$3$$3$$3$ (a)

$v$$3$$3$$3$$3$$3$ (b)

Figure 4:  Possible configurations of neighbours of $v$
for $|\mathcal{S}|=2$, $n_{3_{2}}=1$ and $n_{3_{1,0}}=4$

Note that $v$ has exactly five $3$-neighbours. Recall that
$|\mathcal{S}|\geq\left\lceil\tfrac{n_{3_{1,0}}}{2}\right\rceil$. Hence,
$|\mathcal{S}|\geq 2$. Suppose $|\mathcal{S}|=2$. Since $n_{3_{1,0}}=4$ and
each of these four $3$-neighbours belongs to at least one non-triangular
$v$-segment, each of the two non-triangular segments contains two semi-weak
$3$-neighbours of $v$. Hence, we consider two cases — see Figures 4a and 4b,
as they are the only possible configurations. In both cases, by
($C_{\ref{c:edge}}$), $v$ belongs to a segment with the degree sequence
$(8^{+},9,8^{+})$, which gets only $\tfrac{1}{3}$ of charge from $v$.

Then $v$ sends at most

$6\cdot\tfrac{1}{2}+\tfrac{1}{3}+5\cdot\tfrac{1}{3}=5.$

Finally, suppose $|\mathcal{S}|\geq 3$. Then, $v$ sends at most

$\tfrac{1}{2}(9-|\mathcal{S}|)+5\cdot\tfrac{1}{3}=6\tfrac{1}{6}-\tfrac{1}{2}|\mathcal{S}|\leq
6\tfrac{1}{6}-\tfrac{1}{2}\cdot 3=4\tfrac{2}{3}\leq 5.$

∎

######  Claim 3.

If $n_{3_{1,0}}=6$ the final charge of $v$ is non-negative.

###### Proof.

For $n_{3_{1,0}}=6$ the neighbourhood of $v$ consists of a weak $3$-neighbour,
its two $8^{+}$-neighbours and six $3$-neighbours which are not weak. In
particular, the six non-weak $3$-neighbours are consecutive around $v$. By
($C_{\ref{c:edge}}$), it follows that for each pair $x$, $y$ of these six
neighbours the segment $(x,v,y)$ is non-triangular. Hence, $|\mathcal{S}|\geq
5$.

Then, $v$ sends at most

$7\cdot\tfrac{1}{3}+(9-|S|)\cdot\tfrac{1}{2}=4\tfrac{1}{3}<5.$

∎

Now we will show that the final charge of $v$ is non-negative also in the
remaining cases. Vertex $v$ sends at most
$\tfrac{1}{3}+\tfrac{1}{3}n_{3_{1,0}}+\tfrac{1}{2}(9-|\mathcal{S}|)$ to
adjacent vertices and segments, so its final charge is at least

$5-\tfrac{1}{3}-\tfrac{1}{3}n_{3_{1,0}}-\tfrac{1}{2}(9-|\mathcal{S}|)=\tfrac{1}{6}+\tfrac{1}{2}|\mathcal{S}|-\tfrac{1}{3}n_{3_{1,0}}\stackrel{{\scriptstyle\eqref{eq:facesbound}}}{{\geq}}\tfrac{1}{6}+\tfrac{1}{2}\left\lceil\tfrac{n_{3_{1,0}}}{2}\right\rceil-\tfrac{1}{3}n_{3_{1,0}}.$

For odd $n_{3_{1,0}}$, this value is equal to
$\tfrac{1}{6}+\tfrac{1}{2}\tfrac{n_{3_{1,0}}+1}{2}-\tfrac{1}{3}n_{3_{1,0}}=\tfrac{5}{12}-\tfrac{n_{3_{1,0}}}{12}$
which is non-negative for $n_{3_{1,0}}\leq 5$. For even $n_{3_{1,0}}$ it is
equal
$\tfrac{1}{6}+\tfrac{1}{2}\tfrac{n_{3_{1,0}}}{2}-\tfrac{1}{3}n_{3_{1,0}}=\tfrac{1}{6}-\tfrac{n_{3_{1,0}}}{12}$,
which is non-negative for $n_{3_{1,0}}\leq 2$. Since $n_{3_{1,0}}\leq 6$,
these are all the cases not covered by Claims 2 and 3.

Case 1.3 $n_{3_{2}}=2$
Let $a$, $b$ be the weak $3$-neighbours of $v$.

$v$$3$$3$ (a)

$v$$3$$3$ (b)

Figure 5:  Possible configurations of vertices incident to $v$

######  Claim 4.

In this case $v$ is incident to at least one triangular segment not containing
a $5^{-}$ vertex or to at least one non-triangular segment.

###### Proof.

By ($C_{\ref{c:2consweak3neighbours}}$) we know that the two weak
$3$-neighbours $a$ and $b$ do not share a neighbour other than $v$, so there
are exactly three neighbours of $v$ which are neither $a$ nor $b$ nor the
neighbours of $a,\ b$. Let $C$ be the set of such vertices. There are two ways
of how the vertices of $C$ may be arranged around $v$: either exactly two of
them are consecutive (see Fig 5a) or all of them are consecutive (see Fig 5b).

Suppose that all segments incident to $v$ are triangular, for otherwise we are
done. In the case $(a)$, the two consecutive vertices of $C$ are neighbours,
so by ($C_{\ref{c:edge}}$) one of them, call it $x$, has degree at least $6$.
Taking $x$, $v$ and the common neighbour of $v$, $x$, and $a$ or $b$ we get
the triangular segment from the claim.

In the case $(b)$, the sought triangular segment is formed by $v$ and
neighbours of $a$ and $b$. ∎

According to Rule • ‣ 3.2, $v$ sends $\tfrac{1}{3}$ to every triangular
segment containing no vertices of degree $5^{-}$, if any. Moreover, $v$ sends
no charge to non-triangular segments. Hence, by Claim 4 $v$ sends at most
$\tfrac{1}{3}+8\cdot\tfrac{1}{2}$ to triangular segments. Also, $v$ sends
$2\cdot\tfrac{1}{3}$ to $a$ and $b$, and nothing more to the other neighbours
by ($C_{\ref{c:edge}}$) and ($C_{\ref{c:2weak3neighbours3neighbour}}$). Thus,
the total charge sent by $v$ is at most

$2\cdot\tfrac{1}{3}+\tfrac{1}{3}+8\cdot\tfrac{1}{2}=5.$

Case 2 $v$ has a $2$-neighbour.
By ($C_{\ref{c:2degree2neighbours}}$) $v$ has exactly one $2$-neighbour, let
us denote it by $a$. By ($C_{\ref{c:weak3degree2}}$) $v$ does not have weak
$3$-neighbours. In the next paragraphs we study the dependence between the
number of $3$-neighbours of $v$ and that of non-triangular $v$-segments.

We introduce the following notation. Let $\mathcal{N}_{3}$ be the set of
$3$-neighbours of $v$. For a segment $s$ let $n_{3}(s)$ be the number of
$3$-vertices in $s$. Let $\mathcal{S}$ be the set of all non-triangular
$v$-segments and let $\mathcal{S}^{i}$ be the set of segments of length $i$
incident with $v$ (recall that the length of a segment is defined as the
length of face it belongs to). Moreover, we define

  * •

$\mathcal{S}_{d}=\\{s\in\mathcal{S}\ |\ s\mbox{ contains a }d\mbox{-neighbour
of }v\\}$,

  * •

$\mathcal{S}_{d,d^{\prime}}=\\{(x,v,y)\in\mathcal{S}\ |\
\\{d_{G}(x),d_{G}(y)\\}=\\{d,d^{\prime}\\}\\}$

For example, $\mathcal{S}_{3}$ is a set of segments containing a $3$-neighbour
of $v$ (note that it may contain a $2$-neighbour or another $3$-neighbour). We
extend this notation in a natural way to degree lower bounds, for example,
$\mathcal{S}_{2,4^{+}}$ is a set of segments containing exactly one
$2$-neighbour of $v$ and a $4^{+}$-neighbour of $v$.

We also define $\mathcal{S}_{l}^{d}=\mathcal{S}^{d}\cap\mathcal{S}_{l}$, e.g.,
$\mathcal{S}_{3,4+}^{5+}=\mathcal{S}^{5+}\cap\mathcal{S}_{3,4+}$. Moreover,
let

$\mathcal{N}_{3}^{*}=\\{x\in\mathcal{N}_{3}\ |\ \mbox{if }x\text{ belongs to
}s\in\mathcal{S},\mbox{ then
}s\in\mathcal{S}_{3}^{4}\cup\mathcal{S}_{3,4+}^{5+}\\}.$

We also use the notation defined above with respect to any subgraph
$G^{\prime}$ of $G$ and a vertex $v^{\prime}\in V(G^{\prime})$, for example
$\mathcal{S}(G^{\prime},v^{\prime})$ is the set of all non-triangular
$v^{\prime}$-segments,
$\mathcal{S}_{d}(G^{\prime},v^{\prime})=\\{s\in\mathcal{S}(G^{\prime},v^{\prime})\
|\ s\text{ contains a }d\text{-neighbour of }v^{\prime}\\}$ etc.

######  Claim 5.

Let $G^{\prime}$ be a subgraph of $G$, and let $v^{\prime}$ be a vertex of
$G^{\prime}$ such that $v^{\prime}$ has no weak $3$-neighbours and it is not
incident with a $4$-face with two semi-weak $3$-neighbours on its boundary.
Then

$|\mathcal{N}_{3}^{*}(G^{\prime},v^{\prime})|\leq\tfrac{3}{2}|\mathcal{S}_{3}^{4}(G^{\prime},v^{\prime})\cup\mathcal{S}_{3,4+}^{5+}(G^{\prime},v^{\prime})|.$

###### Proof.

We use a discharging argument. Each segment
$s\in\mathcal{S}_{3}^{4}(G^{\prime},v^{\prime})\cup\mathcal{S}_{3,4+}^{5+}(G^{\prime},v^{\prime})$
sends the charge using the following rules:

Consider a segment
$s=(x,v^{\prime},y)\in\mathcal{S}_{3}^{4}(G^{\prime},v^{\prime})\cup\mathcal{S}_{3,4+}^{5+}(G^{\prime},v^{\prime})$.
First assume $s$ contains a semi-weak $3$-neighbour, say $x$. By our
assumption $y$ is not semi-weak $3$-neighbour. Then $s$ sends $1$ to $x$ and
$\tfrac{1}{2}$ to $y$. Otherwise, suppose that in our plane embedding $x$
appears just before $y$ among the neighbours of $v$ in the clockwise order
around $v$. Then, $s$ sends $1$ to $y$ and $\tfrac{1}{2}$ to $x$.

Observe that to show the claim it suffices to prove that ($i$) every vertex
$x\in\mathcal{N}_{3}^{*}(G^{\prime},v^{\prime})$ gets at least $1$ charge and
($ii$) every segment of
$\mathcal{S}_{3}^{4}(G^{\prime},v^{\prime})\cup\mathcal{S}_{3,4+}^{5+}(G^{\prime},v^{\prime})$
sends at most $\tfrac{3}{2}$ charge.

Consider $x\in\mathcal{N}_{3}^{*}(G^{\prime},v^{\prime})$. If $x$ is incident
to two segments from $\mathcal{S}(G^{\prime},v^{\prime})$, then $x$ gets at
least $\tfrac{1}{2}$ from each of them, so at least $1$ charge in total.
Otherwise, $x$ is incident to exactly one segment from
$\mathcal{S}(G^{\prime},v^{\prime})$, because weak $3$-neighbours are
excluded. Hence, $x$ is a semi-weak $3$-neighbour and it gets $1$ charge from
the incident segment, so ($i$) holds. For ($ii$) it suffices to show that each
segment from
$\mathcal{S}_{3}^{4}(G^{\prime},v^{\prime})\cup\mathcal{S}_{3,4^{+}}^{5+}(G^{\prime},v^{\prime})$
has on its boundary at most one semi-weak $3$-neighbour of $v$. Indeed, a
segment from $\mathcal{S}_{3,4^{+}}^{5+}(G^{\prime},v^{\prime})$ has exactly
one by definition and a segment of length $4$ cannot be incident to two semi-
weak $3$-neighbours by our assumption. ∎

######  Claim 6.

If
$|\mathcal{S}_{2,4^{+}}^{4}\cup\mathcal{S}_{2}^{5+}\cup\mathcal{S}_{3,3}^{5+}\cup\mathcal{S}_{4^{+},4^{+}}|\geq
1$, then $v$ has non-negative final charge.

###### Proof.

Note that
$|\mathcal{S}|=|\mathcal{S}_{2,4^{+}}^{4}|+|\mathcal{S}_{2}^{5+}|+|\mathcal{S}_{3,3}^{5+}|+|\mathcal{S}_{3}^{4}\cup\mathcal{S}_{3,4+}^{5+}|+|\mathcal{S}_{4^{+},4^{+}}|$.
Consider a $3$-neighbour $x\in\mathcal{N}_{3}\setminus\mathcal{N}_{3}^{*}$. By
($C_{\ref{c:weak3degree2}}$) $x$ is not a weak $3$-neighbour, so it is
incident to at least one segment $s\in\mathcal{S}$. Since
$x\in\mathcal{N}_{3}\setminus\mathcal{N}_{3}^{*}$, we may choose $s$ so that
$s\in\mathcal{S}_{3}\setminus(\mathcal{S}_{3}^{4}\cup\
\mathcal{S}_{3,4+}^{5+})\subseteq\mathcal{S}_{2}^{5+}\cup\mathcal{S}_{3,3}^{5+}.$
There are at most $|\mathcal{S}_{2}^{5+}|$, resp. $2|\mathcal{S}_{3,3}^{5+}|$,
such $x$’s incident to a segment from $\mathcal{S}_{2}^{5+}$, resp.
$\mathcal{S}_{3,3}^{5+}$. Hence,
$|\mathcal{N}_{3}\setminus\mathcal{N}_{3}^{*}|\leq|\mathcal{S}_{2}^{5+}|+2|\mathcal{S}_{3,3}^{5+}|$.
By Claim 5 (applied with $G^{\prime}=G$ and $v^{\prime}=v$, note that the
assumptions are met because ($C_{\ref{c:weak3degree2}}$) and
($C_{\ref{c:2neighbour33bigface}}$) are excluded), it follows that
$|\mathcal{N}_{3}|\leq|\mathcal{S}_{2}^{5+}|+2|\mathcal{S}_{3,3}^{5+}|+\tfrac{3}{2}|\mathcal{S}_{3}^{4}\cup\mathcal{S}_{3,4+}^{5+}|$.

Thus, $v$ sends at most

$\displaystyle
1+\tfrac{1}{3}|\mathcal{N}_{3}|+\tfrac{1}{2}(9-|\mathcal{S}|)=5\tfrac{1}{2}+\tfrac{1}{3}|\mathcal{N}_{3}|-\tfrac{1}{2}|\mathcal{S}|\leq$
(2) $\displaystyle\leq
5\tfrac{1}{2}+\tfrac{1}{3}(|\mathcal{S}_{2}^{5+}|+2|\mathcal{S}_{3,3}^{5+}|+\tfrac{3}{2}|\mathcal{S}_{3}^{4}\cup\mathcal{S}_{3,4+}^{5+}|)-\tfrac{1}{2}(|\mathcal{S}_{2,4^{+}}^{4}|+|\mathcal{S}_{2}^{5+}|+|\mathcal{S}_{3,3}^{5+}|+|\mathcal{S}_{3}^{4}\cup\mathcal{S}_{3,4+}^{5+}|+|\mathcal{S}_{4^{+},4^{+}}|)=$
$\displaystyle=5\tfrac{1}{2}-\tfrac{1}{6}|\mathcal{S}_{2}^{5+}|+\tfrac{1}{6}|\mathcal{S}_{3,3}^{5+}|-\tfrac{1}{2}|\mathcal{S}_{4^{+},4^{+}}|-\tfrac{1}{2}|\mathcal{S}_{2,4^{+}}^{4}|.$

The initial charge increased by the charge $v$ receives from segments by Rule
• ‣ 3.2 is equal to

$5+\tfrac{1}{2}|\mathcal{S}_{2}^{5+}|+\tfrac{2}{3}|\mathcal{S}_{3,3}^{5+}|.$

Hence, the final charge at $v$ is at least

$\displaystyle\left(5+\tfrac{1}{2}|\mathcal{S}_{2}^{5+}|+\tfrac{2}{3}|\mathcal{S}_{3,3}^{5+}|\right)-\left(5\tfrac{1}{2}-\tfrac{1}{6}|\mathcal{S}_{2}^{5+}|+\tfrac{1}{6}|\mathcal{S}_{3,3}^{5+}|-\tfrac{1}{2}|\mathcal{S}_{4^{+},4^{+}}|-\tfrac{1}{2}|\mathcal{S}_{2,4^{+}}^{4}|\right)=$
(3)
$\displaystyle\tfrac{2}{3}|\mathcal{S}_{2}^{5+}|+\tfrac{1}{2}|\mathcal{S}_{3,3}^{5+}|+\tfrac{1}{2}|\mathcal{S}_{4^{+},4^{+}}|+\tfrac{1}{2}|\mathcal{S}_{2,4^{+}}^{4}|-\tfrac{1}{2}$

which is non-negative if
$|\mathcal{S}_{2,4^{+}}^{4}\cup\mathcal{S}_{2}^{5+}\cup\mathcal{S}_{3,3}^{5+}\cup\mathcal{S}_{4^{+},4^{+}}|\geq
1$. ∎

As we excluded ($C_{\ref{c:weak3degree2}}$),
($C_{\ref{c:2neighbour33bigface}}$), by Claim 6 we can assume that
$\mathcal{S}_{2}^{5+}=\mathcal{S}_{3,3}^{5+}=\mathcal{S}_{4^{+},4^{+}}=S_{2,4^{+}}^{4}=\emptyset.$
In other words,

$\mathcal{S}=\mathcal{S}_{3}^{4}\cup\mathcal{S}_{3,4^{+}}^{5+}$ (4)

and thus $\mathcal{N}_{3}=\mathcal{N}_{3}^{*}$.

We consider two subcases. (recall that $a$ is the unique $2$-neighbour of
$v$.)

Case 2.1 $a$ is incident to at least one triangular segment.
Since $G$ is simple $a$ is incident to exactly one non-triangular segment
(denote it by $s$) and one triangular one. By (4) $s$ has length $4$ and $s$
contains a $3$-neighbour. The $3$-neighbour in $s$ has to be incident to
another segment from $\mathcal{S}$ for otherwise we get the excluded
configuration ($C_{\ref{c:weak3degree2}}$). Thus, $|\mathcal{S}|\geq 2$.

9$v$$2$$a$$3$ (a)  Figure 6:  Configuration of $a$ belonging to exactly one
triangle

Note that by ($C_{\ref{c:23triangles-3}}$) $v$ has no more $3$-neighbours.
Hence, $v$ sends at most

$1+\tfrac{1}{3}+\tfrac{1}{2}(9-|\mathcal{S}|)\leq
1+\tfrac{1}{3}+\tfrac{1}{2}(9-2)=4\tfrac{5}{6},$

which is smaller than the initial charge. Hence, $v$ has non-negative final
charge.

Case 2.2 $a$ is not incident to any triangular segment.

######  Claim 7.

$\tfrac{3}{2}(|\mathcal{S}|-1)\geq n_{3}$

###### Proof.

Consider a subgraph $G^{\prime}$ of $G$ obtained by removing the vertex $a$.
By our assumption $a$ is incident to two non-triangular segments in $G$, which
are of length $4$ by (4), since by definition
$\mathcal{S}_{3,4^{+}}^{5+}\cap\mathcal{S}_{2}=\emptyset$. Then in the process
of obtaining $G^{\prime}$ from $G$ we remove two segments of length $4$, say
$s_{1},\ s_{2}$ and create a new segment $s^{\prime}$, also of length $4$ (see
Figure 7). By (4), $s_{1},\ s_{2}\in\mathcal{S}_{3}^{4}(G,v)$ and hence
$s^{\prime}\in\mathcal{S}_{3}^{4}(G^{\prime},v)$. In other words

$\mathcal{S}_{3}^{4}(G^{\prime},v)\cup\mathcal{S}_{3,4+}^{5+}(G^{\prime},v)=\mathcal{S}(G,v)\setminus\\{s_{1},s_{2}\\}\cup\\{s^{\prime}\\}.$
(5)

$v$$2$$s_{1}$$s_{2}$ (a)

$v$$s^{\prime}$ (b)

Figure 7:  Segments in $G$ and in $G^{\prime}$.

Then, (4) and (5) implies that
$\mathcal{S}(G^{\prime},v)=\mathcal{S}_{3}^{4}(G^{\prime},v)\cup\mathcal{S}_{3,4^{+}}^{5+}(G^{\prime},v),$
and hence
$\mathcal{N}_{3}^{*}(G^{\prime},v)=\mathcal{N}_{3}(G^{\prime},v)=\mathcal{N}_{3}(G,v)$.

Since $G$ does not contain configurations ($C_{\ref{c:weak3degree2}}$) and
($C_{\ref{c:2neighbour33bigface}}$), also in $G^{\prime}$ vertex $v$ has no
weak $3$-neighbours and is not incident to any $4$-face having two semi-weak
$3$-neighbours on its boundary (recall that configurations are defined as
subgraphs, so if $G^{\prime}$ contains ($C_{\ref{c:2neighbour33bigface}}$), so
does $G$). Therefore, we can apply Claim 5 for $G^{\prime}$ and
$v^{\prime}=v$. Hence, by Claim 5 and equalities (4) and (5) to get the
following

$|N_{3}(G,v)|\stackrel{{\scriptstyle\eqref{eq:facetypes}}}{{=}}|\mathcal{N}_{3}^{*}(G^{\prime},v)|\stackrel{{\scriptstyle\text{Claim
\ref{l:faces3degree}}}}{{\leq}}\tfrac{3}{2}|\mathcal{S}_{3}^{4}(G^{\prime},v)\cup\mathcal{S}_{3,4^{+}}^{5+}(G^{\prime},v)|\stackrel{{\scriptstyle\eqref{eq:podgraphfaces}}}{{=}}\tfrac{3}{2}\left(|\mathcal{S}(G,v)|-1\right).$

∎

Vertex $v$ sends $1$ to its $2$-neighbour, $\tfrac{1}{3}$ to its
$3$-neighbours and at most $\tfrac{1}{2}$ to incident triangular segments.
Thus, it sends at most

$1+\tfrac{1}{3}n_{3}+\tfrac{1}{2}(9-|\mathcal{S}|)\leq
5\tfrac{1}{2}+\tfrac{1}{3}n_{3}-\tfrac{1}{2}(\tfrac{2}{3}n_{3}+1)=5$

so the final charge of $v$ remains non-negative. ∎

By lemmas 4 and 5 every face and every vertex has non-negative final charge.
Since the total charge does not change when the discharging rules are applied,
we obtain that $\sum_{v\in V}(d(v)-4)+\sum_{f\in F}(\ell(f)-4)\geq 0$, thus
$4|E|-4|V|-4|F|\geq 0$. However, by Euler’s formula $|E|-|V|-|F|=-2$, a
contradiction. It follows that the minimal counterexample does not exist, and
thus we have proved Theorem 2.

##  4 Computer-assisted reducibility

In this section we describe the algorithm used for the computer-assisted proof
of Lemma 3.

The input to the algorithm consists of a graph $H$ that describes a
configuration: a graph and a degree function $d:V(H)\rightarrow\mathbb{N}$
that describes degrees of vertices of $H$ in graph $G$, e.g. for
($C_{\ref{c:23triangles-3}}$) $d(x)=2$, $d(w)=d(z)=3$ and $d(y)=d(y)=9$.
Additionally, the input specifies an edge $e_{H}\in E(H)$, whose meaning will
be explained in what follows.

Let us first describe the structure of the proofs generated by our program
reduce.py, and next we will elaborate on how we implemented finding such
proofs.

###  4.1 Proof structure

The proof structure is simple. We remove edge $e_{H}$ from $G$ obtaining a new
graph $G^{\prime}$, colour the graph $G^{\prime}$ with a colouring
$c^{\prime}$ which exists by the minimality of $G$. Next, we uncolour all the
edges of $E(H)$ and the goal is to find a proper colouring $c$ of all edges
$G$ (together with $e_{H}$) such that $c|_{E(G)\setminus
E(H)}=c^{\prime}|_{E(G)\setminus E(H)}$. Note that this proof structure fits
the proof of Lemma 1 but does not fit the proof of Lemma 2, and in fact
configuration ($C_{\ref{c:2degree2neighbours}}$) cannot be reduced this way.

Of course, even a computer cannot enumerate all colourings of $G^{\prime}$,
since we do not know $G$, and although $H$ is fixed, the number of possible
graphs $G$ is infinite. Instead, we enumerate certain classes of colourings of
$G^{\prime}$. Such a class is characterized by:

  * •

$\mathcal{C}=\\{C_{v}\mid v\in V(H)\\}$, where $C_{v}$ is a multiset of
colours of the $d_{G}(v)-d_{H}(v)$ edges incident with $v$ outside $H$, for
every vertex $v\in V(H)$,

  * •

a set $\mathcal{P}$ that contains a triple $(i,u,v)$ for $i\in\\{1,2,3,4\\}$
and $u,v\in V(H)$ iff (1) both $u$ and $v$ have exactly one incident edge in
$E(G)\setminus E(H)$ colored with $i$ and (2) there is an $i$-colored path in
$E(G)\setminus E(H)$ between $u$ and $v$ in the coloring $c^{\prime}$.

Note that the number of possible sets $\mathcal{P}$ is bounded for a fixed
configuration $(H,d)$. Hence we are able to enumerate all the classes of
colourings of $G^{\prime}$. Moreover, we claim it is sufficient to know just
the class that $c^{\prime}$ belongs to in order to check whether a colouring
of $E(H)$ combined with $c^{\prime}|_{E(G)\setminus E(H)}$ is a proper
colouring of $G$. Indeed, $\mathcal{C}$ is sufficient to make sure that for
every vertex of $H$ the number of occurrences of every colour $i$ in the
combined colouring is correct (i.e., at most two for $i=1,2,3,4$ and at most
one for $i=0$). Such a colouring could still contain a monochromatic cycle.
However, if there is such a cycle $C$, it means that there is a colour
$i=1,2,3,4$ and a collection $\mathcal{A}$ of $i$-coloured paths in $E(H)$ and
another collection $\mathcal{B}$ of $i$-coloured paths in $E(G)\setminus E(H)$
such that $C$ is formed by paths coming alternately from $\mathcal{A}$ and
$\mathcal{B}$. Clearly, $\mathcal{P}$ is sufficient to guarantee that this
does not happen.

Note that the colouring of the inner edges of the configuration, i.e.,
$c^{\prime}|_{E(H)\setminus\\{e_{H}\\}}$ is not needed here. However, we do
check if there is at least one colouring $c_{\text{inner}}$ of
${E(H)\setminus\\{e_{H}\\}}$ that is consistent with $\mathcal{C}$ and
$\mathcal{P}$, because otherwise the pair $(\mathcal{C},\mathcal{P})$ does not
correspond to any colour class and we can safely skip it. Here, consistent
means that $c_{\text{inner}}$ can be extended by outer colorings in the class
$(\mathcal{C},\mathcal{P})$, i.e., (1) for every $v\in V(H)$, the multiset
$C_{v}\cup\\{c_{\text{inner}}(vw)\mid vw\in E(H)\setminus\\{e_{H}\\}\\}$ has
at most two copies of every color and at most one copy of color $0$, (2) for
every $(i,u,v)\in\mathcal{P}$ we have $i\in C_{u}\cap C_{v}$, and (3) after
extending the graph $(V(H),{E(H)\setminus\\{e_{H}\\}})$ colored with
$c_{\text{inner}}$ by colored edges corresponding to paths in $\mathcal{P}$ we
do not get monochromatic cycles.

Let us call a reducibility proof with structure as above, a standard proof.

Recall that in our configurations each vertex has an upper bound on its degree
in $G$ (for example 3 for vertex $w$ in ($C_{\ref{c:23triangles-3}}$)). For
some vertices this upper bound seems not to be specified (for example for
vertex $u$ in ($C_{\ref{c:23triangles-3}}$)) but then it is just equal to the
maximum degree, i.e., 9. These upper bounds are exactly the values of function
$d$ that is a part of the input to our program. Thus one may think that the
program verifies only reducibility for one particular choice of the values of
degrees, i.e., the maximal values. However, this implies reducibility also for
any degree function $d^{\prime}:V(G)\rightarrow\mathbb{N}$ such that for each
$v\in V(H)$, $d_{H}(v)\leq d^{\prime}(v)\leq d(v)$, as shown in the lemma
below. The intuition behind the proof of this lemma should be clear: a
standard reducibility proof for configuration $C$ works also for configuration
$C^{\prime}$.

######  Lemma 6.

Let $C=(H,d)$ and $C^{\prime}=(H,d^{\prime})$ be two configurations and assume
that for every vertex $v\in V(H)$ we have $d_{H}(v)\leq d^{\prime}(v)\leq
d(v)$. If $C$ is reducible by a standard proof, then $C^{\prime}$ is
reducible.

###### Proof.

Assume $C^{\prime}$ appears in a minimal counterexample $G\in\mathcal{G}$.
Then we proceed as in the standard reducibility proof for $C$, i.e., we remove
from $G$ the same edge $e$ of $H$ which was removed for $C$. Since
$G\in\mathcal{G}$, there is a colouring
$c^{\prime}:E(G)\rightarrow\\{0,1,2,3,4\\}$ of $G^{\prime}-e$. This colouring
defines sets $\mathcal{C}^{\prime}$ and $\mathcal{P}^{\prime}$, as described
above, where $\mathcal{C}^{\prime}=\\{C^{\prime}_{w}\mid w\in V(H)\\}$. For
every $v\in V(H)$ define $C_{v}$ as an arbitrary multiset of $d(v)-d_{H}(v)$
colors such that

$C^{\prime}_{v}\subseteq
C_{v}\subseteq\\{0,1,1,2,2,3,3,4,4\\}\setminus\\{c^{\prime}(vw)\mid vw\in
E(H)\setminus\\{e\\}\\}.$ (6)

Above, we use the standard notions of inclusion and difference for multisets.
Note that there is at least one candidate for $C_{v}$, because
$|C^{\prime}_{v}|=d^{\prime}(v)-d_{H}(v)$ and $d^{\prime}(v)\leq d(v)$. Define
$\mathcal{C}=\\{C_{v}\mid v\in V(H)\\}$.

Recall that in the standard reducibility proof for $C$ we check all classes of
colourings that are consistent with at least one colouring of
$E(H)\setminus\\{e_{H}\\}$. Since
$(\mathcal{C}^{\prime},\mathcal{P}^{\prime})$ is consistent with
$c^{\prime}|_{E(H)\setminus\\{e_{H}\\}}$, by (6) also
$(\mathcal{C},\mathcal{P}^{\prime})$ is consistent with
$c^{\prime}|_{E(H)\setminus\\{e_{H}\\}}$. Hence, the class
$(\mathcal{C},\mathcal{P}^{\prime})$ is checked in the standard reducibility
proof for $C$, and this proof provides a coloring $c_{\text{inner}}$ of $E(H)$
that can be extended by any coloring in $(\mathcal{C},\mathcal{P}^{\prime})$.
But this means that $c_{\text{inner}}$ can be also extended by
$c^{\prime}|_{E(G)\setminus E(H)}$, because no color appears at a vertex more
than the required number of times and there are no monochromatic cycles. Hence
$G$ can be colored and hence it is not a counterexample, a contradiction. ∎

###  4.2 Implementation

Script reduce.py generates all classes of colourings of $G^{\prime}$ as
follows. First, the recursive function generate_outside_colorings generates
all possible collections $\mathcal{C}$ (as described in Section 4.1). At the
bottom of the recursion, i.e., when the construction of $\mathcal{C}$ is
finished, it calls another recursive function generate_outer_paths. This
function in turn, generates all possible sets $\mathcal{P}$. At the bottom of
the recursion both $\mathcal{C}$ and $\mathcal{P}$ are constructed. Then, a
function color_inner is called, which checks if there is at least one
colouring of ${E(H)\setminus{e_{H}}}$ that is consistent with $\mathcal{C}$
and $\mathcal{P}$. If this is not the case, the pair
$(\mathcal{C},\mathcal{P})$ is skipped. Otherwise, the function color_inner is
called again, just this time with the parameter remove_edge set to false,
which forces the function to colour the edge $e_{H}$ as well. Function
color_inner is a straightforward recursive function which generates all
colourings of $E(H)\setminus\\{e_{H}\\}$ or $E(H)$ so that the number of edges
of given colour at every vertex is as required. Moreover, after colouring each
single edge $e=ab$ it checks if it closes a cycle with a path in $\mathcal{P}$
and if not, it updates $\mathcal{P}$, i.e., either joins two paths in
$\mathcal{P}$ (with endpoints in $a$ and $b$, respectively), or extends a path
from $\mathcal{P}$ (with an endpoint in $a$ or $b$) by $e$, or just adds a
single edge path to $\mathcal{P}$.

While writing the code, it was our priority to make it as much self-
explanatory as possible. We have chosen Python programming language for its
high readability of the code. We deliberately have not exploit symmetries
between colours to keep the algorithm and the argument simple. The price is
the running time: it used 149 hours (on a single processor, Intel Xeon CPU
E5-2698 v4, 2.20GHz) for the most demanding configuration
($C_{\ref{c:2weak3neighbours3neighbour}}$). The time used for other
configurations varied from a couple of seconds to 94 minutes.

##  5 Conclusion

We have shown that Conjecture 2 is true for $\Delta=9$ but the $\Delta=7$ is
still open. This would be an interesting strengthening of the result of
Sanders and Zhao [9] who proved that planar graphs maximum degree 7 are Class
I. We were unable to extend our approach to $\Delta=7$ and we suppose that for
that a different argument, of a more global nature, is needed. Indeed, when
$\Delta=7$ we have less charge at a vertex and we quickly arrive at
configurations with elements of negative charge that cannot be reduced using
the standard proof generated by our program. Of course it is possible that
this can be circumvented by a smart set of discharging rules, but it is worth
noting that such a discharging proof is not known for edge coloring (which is
a less constrained problem) even for $\Delta=8$.

The Planar Linear Arboricity Conjecture (see Cygan et al. [5]) is still open.
However, in the spirit of this work one can consider its weaker versions. For
example, what is the maximum $k$ such that edges of a planar graph of maximum
degree 8 can be partitioned into $k$ linear forests and $8-2k$ matchings? At
the moment, by Vizing Theorem we know that $k\geq 0$, but even the case $k=1$
has not been investigated.

## Acknowledgments

The authors are grateful to Marek Cygan who implemented an early version of
the computer program for checking reducibility in the context of linear
arboricity. We thank Arkadiusz Socała for discussions in early stage of the
project. We are also very grateful to the reviewers for careful reading and
numerous helpful comments.

This research is a part of projects that have received funding from the
European Research Council (ERC) under the European Union’s Horizon 2020
research and innovation programme Grant Agreements 677651 (ŁK, project TOTAL)
and 948057 (ŁK, MP, project BOBR). JC and ŁK were also supported by the Polish
Ministry of Science and Higher Education project Szkoła Orłów, project number
500-D110-06-0465160.

## References

  * [1] J. Akiyama, G. Exoo, and F. Harary.  Covering and packing in graphs III: Cyclic and acyclic invariants.  Math Slovaca, 30:405–417, 1980.
  * [2] J. Akiyama, G. Exoo, and F. Harary.  Covering and packing in graphs IV: Linear arboricity.  Networks, 11:69–72, 1981.
  * [3] Noga Alon.  The linear arboricity of graphs.  Israel Journal of Mathematics, 62(3):311–325, 1988.
  * [4] Manu Basavaraju, Arijit Bishnu, Mathew C. Francis, and Drimit Pattanayak.  The linear arboricity conjecture for 3-degenerate graphs.  In Isolde Adler and Haiko Müller, editors, Graph-Theoretic Concepts in Computer Science - 46th International Workshop, WG 2020, Leeds, UK, June 24-26, 2020, Revised Selected Papers, volume 12301 of Lecture Notes in Computer Science, pages 376–387. Springer, 2020.  doi:10.1007/978-3-030-60440-0\\_30.
  * [5] Marek Cygan, Jianfeng Hou, Lukasz Kowalik, Borut Luzar, and Jian-Liang Wu.  A planar linear arboricity conjecture.  J. Graph Theory, 69(4):403–425, 2012.  doi:10.1002/jgt.20592.
  * [6] H. Enomoto and B. Péroche.  The linear arboricity of some regular graphs.  J. Graph Theory, 8:309–324, 1984.
  * [7] Filip Guldan.  The linear arboricity of 10-regular graphs.  Math Slovaca, 36(3):225–228, 1986.
  * [8] Frank Harary.  Covering and packing in graphs I.  Ann. N.Y. Acad. Sci, 175:198–205, 1970.
  * [9] Daniel P. Sanders and Yue Zhao.  Planar graphs of maximum degree seven are class I.  J. Comb. Theory, Ser. B, 83(2):201–212, 2001.  doi:10.1006/jctb.2001.2047.
  * [10] V. G. Vizing.  Critical graphs with a given chromatic number.  Diskret. Analiz, 5:9–17, 1965.
  * [11] J. L. Wu.  On the linear arboricity of planar graphs.  J. Graph Theory, 31:129–134, 1999.
  * [12] J. L. Wu and Y. W. Wu.  The linear arboricity of planar graphs of maximum degree seven is four.  J. Graph Theory, 58(3):210–220, 2008.