# Independent sets versus 4-dominating sets
in outerplanar graphs

Dmitrii Taletskii1,2,3
1 National Research University Higher School of Economics,
Bolshaya Pechyorskaya ul. 25/12, Nizhny Novgorod, 603155 Russia
2Lobachevsky Nizhny Novgorod State University,
ul. Gagarina 23, Nizhny Novgorod, 603950 Russia
3Saint Petersburg University, 7/9 Universitetskaya nab.,
St. Petersburg, 199034 Russia
e-mail<EMAIL_ADDRESS>
###### Abstract

We show that the number of independent sets in every outerplanar graph is
greater than the number of its 4-dominating sets.

Keywords— independent set, dominating set, $k$-dominating set, outerplanar
graph

##  1 Introduction

Throughout this paper we consider only simple and finite graphs. Let $G$ be a
graph with a vertex set $V(G)$ and an edge set $E(G)$. An independent set is a
pairwise nonadjacent subset of $V(G)$. For $k\geq 1$, a $k$-dominating set
$D_{k}$ is a subset of $V(G)$ such that every vertex not from $D_{k}$ is
adjacent to at least $k$ vertices from $D_{k}$. We use the abbriveations ‘IS’
and ‘$k$-DS’ for the terms ‘independent set’ and ‘$k$-dominating set’
respectively. Let $i(G)$ (resp. $\partial_{k}(G)$) be the number of all IS
(resp. $k$-DS) of a graph $G$. Denote by $\mathfrak{D}_{k}(G)$ the family of
all $k$-DS of a graph $G$.

A planar graph is called outerplanar if it has an embedding in the plane such
that all vertices belong to the boundary of its outer face. An outerplanar
graph $G$ is called maximal outerplanar (or MOP) if $G+uv$ is not outerplanar
for any two non-adjacent vertices $u,v\in V(G)$. It is well-known that every
inner face of a MOP is a triangle and every MOP with at least 3 vertices has
at least 2 vertices of degree 2. Denote by $\mathcal{OP}$ and $\mathcal{MOP}$
the classes of all outerplanar and maximal outerplanar graphs, respectively.

The definition of $k$-dominating set implies that for every graph $G$, any two
non-adjacent vertices $u,v\in V(G)$ and any integer $k\geq 1$ we have
$\partial_{k}(G)\leq\partial_{k}(G+uv)$. Therefore, a complete graph $K_{n}$
has the maximum number of $k$-independent sets among all $n$-vertex graphs.
Trees with extremal numbers of $k$-dominating sets were described in [1] for
$k=1$ and in [2] for $k\geq 2$. In [3] and [4] for every $k\geq 2$ new upper
bounds for the number of $k$-dominating independent sets in $n$-vertex graphs
were presented.

The empty graph $nK_{1}$ has the maximum possible number of independent sets
among all $n$-vertex graphs. Moon and Moser [5] described $n$-vertex graphs
with maximal possible number of maximal independent (i.e. independent
1-dominating) sets. In [6] for all $n\geq 5$ the graphs
$H_{n}\in\mathcal{MOP}$ and $H^{\prime}_{n}\in\mathcal{MOP}$ with the maximum
and minimum possible number of IS among all $n$-vertex MOPs were described.

Figure 1: Graphs $H^{\prime}_{9}$ and $H_{9}$

The main result of this paper is the following fact:

######  Theorem 1.

For every outerplanar graph $G$ we have $i(G)>\partial_{4}(G)$.

The rest of the paper is organized as follows. In Section 2 we introduce some
graph terminology and present a maximal outerplanar graph partition. In
Section 3 we prove Theorem 1. In Section 4 we consider a possible
generalization of Theorem 1 and obtain a similar result for the class of
trees.

##  2 Preliminaries

###  2.1 Basic terminology

A tree is a connected acyclic graph and a leaf is a vertex of degree one in a
tree. A support vertex in a tree is a vertex which is adjacent to at least one
leaf. A diameter of a connected graph is the maximum possible distance between
its vertices. A simple path is called diametral, if its length is equal to the
diameter of a graph. Clearly, the ends of any diametral path in a tree are
leaves.

For a graph $G\in\mathcal{OP}$ we consider a weak dual graph $T(G)$, such that
the vertices of $T(G)$ correspond to the inner faces of $G$ and two vertices
are adjacent if and only if the corresponding faces have a common edge. It is
well-known that if $G\in\mathcal{MOP}$, then $T(G)$ is a subcubic tree.

Let $G$ be a graph and $U\subset V(G)$ be its vertex subset. Let $G\setminus
U$ be an induced subgraph of $G$ with the set of vertices $V(G)\setminus U$.

An inner face of a MOP is called an end face if it has a vertex of degree 2.
Note that a face $f$ of a MOP $G$ is an end face if and only if the
corresponding vertex in $T(G)$ has degree at most one. We say that a graph $G$
contains a face $f$, if all vertices and edges from $f$ belong to $G$.

Suppose that $f$ and $f^{\prime}$ are two adjacent inner faces of $G$ with a
common edge $uv$. Denote by $G[f;f^{\prime}]$ the maximal by inclusion
subgraph of $G$ such that it contains $f$, does not contain $f^{\prime}$ and
$uv$ is its outer edge. It is easy to see that if $G\in\mathcal{MOP}$, then
$G[f;f^{\prime}]\in\mathcal{MOP}$.

###  2.2 Independent and 4-dominating sets

Let $G$ be a graph and $u,v\in V(G)$. Let $i(G,u^{+})$ (resp. $i(G,u^{-})$) be
the number of IS of $G$ which contain (resp. do not contain) $u$. We denote by
$i(G,u^{+},v^{+})$ the number of IS of $G$ such that $u,v\in I$ and denote the
values $i(G,u^{+},v^{-})$, $i(G,u^{-},v^{+})$ and $i(G,u^{-},v^{-})$ in the
similar way. Clearly, for any vertices $u,v\in V(G)$ we have

$i(G)=i(G,u^{+},v^{+})+i(G,u^{+},v^{-})+i(G,u^{-},v^{+})+i(G,u^{-},v^{-}).$

Moreover, $i(G,u^{+},v^{+})=0$, if and only if $uv\in E(G)$.

Let $\partial_{4}(G,u^{+})$ (resp. $\partial_{4}(G,u^{-})$) be the number of
4-DS in $G$ which contain (resp. do not contain) $u$. We denote the values
$\partial_{4}(G,u^{+},v^{+})$, $\partial_{4}(G,u^{+},v^{-})$,
$\partial_{4}(G,u^{-},v^{+})$ and $\partial_{4}(G,u^{-},v^{-})$ in the similar
way. Again, for any vertices $u,v\in V(G)$ we have

$\partial_{4}(G)=\partial_{4}(G,u^{+},v^{+})+\partial_{4}(G,u^{+},v^{-})+\partial_{4}(G,u^{-},v^{+})+\partial_{4}(G,u^{-},v^{-}).$

Note that $\partial_{4}(G,u^{+},v^{+})>0$ for any graph $G$. It is easy to see
that $\partial_{4}(G,u^{-},v^{+})>0$, if and only if $deg(u)\geq 4$. Moreover,
$\partial_{4}(G,u^{-},v^{-})>0$, if and only if either
$\min(deg(u),deg(v))\geq 5$ or $uv\notin E(G)$ and $\min(deg(u),deg(v))\geq
4$.

###  2.3 MOP-partition

Consider a graph $G\in\mathcal{MOP}$ and its edge $uv\in E(G)$. Let
$G_{L},G_{R}\in\mathcal{MOP}$ be two maximal by inclusion subgraphs of $G$
such that $E(G_{L})\cap E(G_{R})=uv$ and $uv$ is an outer edge in both $G_{L}$
and $G_{R}$. Clearly, if $uv$ is not an outer edge in $G$ than both $G_{L}$
and $G_{R}$ have at least 3 vertices (otherwise one of them has 2 vertices and
the other coincides with $G$). Call a triple $(G_{L},G_{R},uv)$ a MOP-
partition of $G$. For the given MOP-partition $(G_{L},G_{R},uv)$ we shall use
the notation

$\mathcal{I}_{00}=i(G_{R},u^{-},v^{-}),\
\mathcal{I}_{01}=i(G_{R},u^{-},v^{+}),\
\mathcal{I}_{10}=i(G_{R},u^{+},v^{-}).$

Since $i(G_{R},u^{+},v^{+})=0$, we have
$i(G_{R})=\mathcal{I}_{00}+\mathcal{I}_{01}+\mathcal{I}_{10}$. Morever, if
$G_{R}$ has at least 3 vertices, than
$\mathcal{I}_{00}>\textrm{max}(\mathcal{I}_{01},\mathcal{I}_{10})$.

We now introduce a similar concept for 4-DS. For the given MOP-partition
$(G_{L},G_{R},uv)$ of a graph $G$ let
$\mathcal{D}_{11}=\partial_{4}(G_{R},u^{+},v^{+})$. Denote by
$\mathcal{D}^{k}_{01}$ the number of 4-DS $D^{\prime}$ of a graph
$G_{R}\setminus u$ such that $v\in D^{\prime}$ and the vertex $u$ has at least
$\max(0,4-k)$ neighbors from $D^{\prime}\setminus v$ in $G$. In other words,
$\mathcal{D}^{k}_{01}$ is the number of ‘almost 4-dominating’ sets
$D^{\prime}$ of $G_{R}$ with respect to the vertex $u$. Denote
$\mathcal{D}^{k}_{10}$ in the same way as $\mathcal{D}^{k}_{01}$. Finally, let
$\mathcal{D}^{kl}_{00}$ be the number of 4-DS $D^{\prime\prime}$ of a graph
$G_{R}\setminus\\{u,v\\}$, such that in the graph $G_{R}$ the vertices $u$ and
$v$ have at least $\max(0,4-k)$ and $\max(0,4-l)$ neighbors from
$D^{\prime\prime}$, respectively.

From the definitions of $\mathcal{D}^{k}_{01}$, $\mathcal{D}^{k}_{10}$ and
$\mathcal{D}^{kl}_{00}$ it follows immediately that for all $1\leq
k^{\prime}\leq k$ and $1\leq l^{\prime}\leq l$ we have
$\mathcal{D}^{k^{\prime}}_{01}\leq\mathcal{D}^{k}_{01},\mathcal{D}^{l^{\prime}}_{10}\leq\mathcal{D}^{l}_{10}$
and $\mathcal{D}^{k^{\prime}l^{\prime}}_{00}\leq\mathcal{D}^{kl}_{00}$. We now
prove a few more similar properties.

######  Lemma 1.

Let $G\in\mathcal{MOP}$. For the given MOP-partition $(G_{L},G_{R},uv)$ the
following holds:

1\. For all $k,l\geq 0$ we have
$\mathcal{D}_{11}\geq\max(\mathcal{D}^{k}_{10},\mathcal{D}^{k}_{01})$ and
$\min(\mathcal{D}^{k}_{10},\mathcal{D}^{k}_{01})\geq\mathcal{D}^{kl}_{00}.$

2\. If $deg_{G_{R}}(u)\geq 2$, then
$2\cdot\mathcal{D}^{3}_{10}\geq\mathcal{D}^{4}_{10}$ and
$2\cdot\mathcal{D}^{3}_{01}\geq\mathcal{D}^{4}_{01}$.

3\. If $deg_{G_{R}}(u)=3$, then
$3\cdot\mathcal{D}^{2}_{01}\geq\mathcal{D}^{3}_{01}$. Moreover, if
$deg_{G_{R}}(u)\geq 4$, then
$2\cdot\mathcal{D}^{2}_{01}\geq\mathcal{D}^{3}_{01}$.

###### Proof.

Statement 1. We show that for all $k\geq 0$ the inequality
$\mathcal{D}_{11}\geq\mathcal{D}^{k}_{10}$ holds. Consider the function

$F:\mathfrak{D}_{4}(G_{R}\setminus v)\longrightarrow\mathfrak{D}_{4}(G_{R}),$

which maps a 4-DS $D$ of $G_{R}\setminus v$ into a 4-DS $D\cup\\{v\\}$ of
$G_{R}$. Clearly, $F$ is injective, therefore $\partial_{4}(G_{R}\setminus
v)\leq\partial_{4}(G)$, this implies the inequality. The inequalities
$\mathcal{D}_{11}\geq\mathcal{D}^{k}_{01}$ and
$\min(\mathcal{D}^{k}_{10},\mathcal{D}^{k}_{01})\geq\mathcal{D}^{kl}_{00}$ are
easy to prove using the same approach.

Statement 2. The inequality $deg_{G_{R}}(u)\geq 2$ means that the subgraph
$G_{R}$ has at least 3 vertices, thus $deg_{G_{R}}(v)\geq 2$. We denote by $w$
the common neighbor of $u$ and $v$, such that $w\in V(G_{R})$ (since $uv$ is
an outer edge of $G_{R}\in\mathcal{MOP}$, there is exactly one such vertex).
Our goal is to show that
$\mathcal{D}^{4}_{10}-\mathcal{D}^{3}_{10}\leq\mathcal{D}^{3}_{10}$. The left
hand side equals to the number of 4-DS of the graph $G_{R}\setminus v$ such
that they don’t have vertices from $N_{G_{R}}[u]\setminus v$. The right hand
side equals the number of 4-DS of the same graph which contain at least 1
vertex from the set $N_{G_{R}}[u]\setminus v$, therefore the inequality holds.
It is easy to prove that $2\mathcal{D}^{3}_{10}\geq\mathcal{D}^{4}_{10}$,
using the same approach.

Statement 3. By the definition, $\mathcal{D}^{2}_{01}$ is the number of 4-DS
of $G_{R}\setminus u$ with at least two vertices from the set
$N_{G_{R}}[u]\setminus v$. Therefore, the difference
$\mathcal{D}^{3}_{01}-\mathcal{D}^{2}_{01}$ equals to the number of 4-DS of
the graph $G_{R}\setminus u$, with exactly one vertex from the set
$N_{G_{R}}[u]\setminus v$. Let $N_{G_{R}}[u]\setminus v=\\{w_{1},\ldots
w_{s}\\}$, where $s\geq 2$. If $s=2$, then the number of 4-DS with both
vertices $w_{1}$ and $w_{2}$ is at least half of the number of 4-DS with one
fixed vertex, this yields the inequality
$\mathcal{D}^{3}_{01}-\mathcal{D}^{2}_{01}\geq 2\cdot\mathcal{D}^{2}_{01}$. If
$s\geq 3$, then it is easy to see that the number of 4-DS with exactly one
vertex from the set $N_{G_{R}}[u]\setminus v$ is less than then the number of
4-DS with at least two vertices, therefore
$\mathcal{D}^{3}_{01}-\mathcal{D}^{2}_{01}\geq\mathcal{D}^{2}_{01}$, as
required. ∎

##  3 Proof of Theorem 1

We call a graph $G\in\mathcal{MOP}$ critical, if $i(G)\leq\partial_{4}(G)$ and
for every outerplanar graph $G^{\prime}$ such that $|V(G^{\prime})|<|V(G)|$ we
have $i(G^{\prime})>\partial_{4}(G^{\prime})$. In this section we show that
there are no critical graphs, therefore Theorem 1 holds. It suffices to
consider only maximal outerplanar graphs, since for every graph
$G_{0}\in\mathcal{OP}$ there exists a graph $G\in\mathcal{MOP}$ such that
$G_{0}$ is a spanning subgraph of $G$ and the inequalities $i(G_{0})>i(G)$ and
$\partial_{4}(G_{0})\leq\partial_{4}(G)$ hold.

Therefore, we consider a graph $G\in\mathcal{MOP}$ and its weak dual graph
$T(G)$ (remind that $T(G)$ is a subcubic tree). Let $x_{1}x_{2}\ldots x_{k}$
be some diametral path in $T(G)$. If $k\leq 3$, then there are only 3 possible
MOPs up to isomorphism and it is easy to check that they are not critical.
Thus we assume that $k\geq 4$.

######  Lemma 2.

If a graph $G\in\mathcal{MOP}$ has an edge $uv$ such that $deg(u)=2$ and
$deg(v)=3$, then $G$ is not critical.

###### Proof.

Since $G\in\mathcal{MOP}$, the vertices $u$ and $v$ have the unique common
neighbor $a$ and the vertices $v$ and $a$ have the unique common neighbor $b$,
other then $u$. Let $G_{1}=G\setminus u$ and $G_{3}=G\setminus\\{u,a,v\\}$.
Then

$i(G)=i(G,u^{-})+i(G,u^{+})=i(G_{1})+i(G_{3}).$

We now show that

$\partial_{4}(G)-\partial_{4}(G_{1})\leq\partial_{4}(G_{3}).$

The difference $\partial_{4}(G)-\partial_{4}(G_{1})$ equals to the number of
4-DS $D$ of the graph $G$ such that $D\setminus u$ is not a 4-DS for the graph
$G_{1}$. Since $v$ belongs to every 4-DS in both $G$ and $G_{1}$, this is
possible if and only if $a\notin D$ and exactly two vertices from the set
$N(a)\setminus\\{u,v\\}$ belong to $D$. Let $\mathfrak{D}^{\prime}_{4}(G_{1})$
be the family of 4-DS $D^{\prime}$ of $G$ such that $D^{\prime}\setminus u$ is
a 4-DS of $G_{1}$. Consider the function

$F:(\mathfrak{D}_{4}(G)\setminus\mathfrak{D}^{\prime}_{4}(G_{1}))\longrightarrow\mathfrak{D}_{4}(G_{3}),$

such that $F(D)=(D\cup\\{b\\})\setminus\\{u,v\\}$. It is easy to see that $F$
is injective, because if
$D^{\prime},D^{\prime\prime}\in\mathfrak{D}_{4}(G)\setminus\mathfrak{D}^{\prime}_{4}(G_{1})$
are two distinct 4-DS of $\mathfrak{D}_{4}(G)$, then the sets
$D^{\prime}\setminus\\{u,v,b\\}$ and $D^{\prime\prime}\setminus\\{u,v,b\\}$
are also distinct. Therefore,

$\partial_{4}(G)\leq\partial_{4}(G_{1})+\partial_{4}(G_{3})<i(G_{1})+i(G_{3})=i(G)$

and $G$ is not critical. ∎

Lemma 2 implies that every support vertex of $T(G)$ has degree 3. In
partucular, $deg(x_{2})=3$ and $f_{2}$ is adjacent to some end faces $f_{1}$
and $f^{\prime}_{1}$. In the rest of the chapter we denote the faces $f_{1}$,
$f^{\prime}_{1}$, $f_{2}$ and $f_{3}$ by $a_{1}a_{2}b_{1}$, $a_{2}a_{3}b_{2}$,
$b_{1}b_{2}a_{2}$ and $b_{1}b_{2}c_{1}$ respectively.

######  Lemma 3.

If $deg(x_{2})=deg(x_{3})=deg(x^{\prime}_{2})=3$, then $G$ is not critical.

###### Proof.

Suppose that $b_{2}c_{1}$ is the common edge of the faces $f_{3}$ and $f_{4}$.
Let $G_{L}=G[f_{3};f_{4}]$. Consider the $(G_{L},G_{R},b_{2}c_{1})$-partition
of $G$. Since $G$ is critical, we have $i(G_{R})>\partial_{4}(G_{R})$. Our
goal is to find a constant $c>0$ such that $i(G)\geq c\cdot i(G_{R})$ and
$\partial_{4}(G)\leq c\cdot\partial_{4}(G_{R})$. It is easy to check that the
following holds:

$i(G)=i(G_{L})\cdot\mathcal{I}_{00}+i(G_{L},c^{+}_{1})\cdot\mathcal{I}_{01}+i(G_{L},b^{+}_{2})\cdot\mathcal{I}_{10}=29\cdot\mathcal{I}_{00}+10\cdot\mathcal{I}_{01}+10\cdot\mathcal{I}_{10}.$

Since $\mathcal{I}_{00}\geq\max(\mathcal{I}_{01},\mathcal{I}_{10})$, we have

$i(G)>16\cdot(\mathcal{I}_{00}+\mathcal{I}_{01}+\mathcal{I}_{10})=16\cdot
i(G_{R}).$

Moreover,

$\partial_{4}(G)=\partial_{4}(G,b_{2}^{+},c_{1}^{+})+\partial_{4}(G,b_{2}^{+},c_{1}^{-})+\partial_{4}(G,b_{2}^{-},c_{1}^{+})+\partial_{4}(G,b_{2}^{-},c_{1}^{-})$
$=5\cdot\mathcal{D}_{11}+(2\cdot\mathcal{D}^{4}_{10}+\mathcal{D}^{3}_{10})+(2\cdot\mathcal{D}^{4}_{01}+\mathcal{D}^{3}_{01})+(\mathcal{D}^{44}_{00}+\mathcal{D}^{33}_{00}).$

By Lemma 1, we have $\partial_{4}(G)\leq
13\cdot\mathcal{D}_{11}<16\cdot\partial_{4}(G_{R})$. Therefore, $G$ is not
critical. ∎

######  Lemma 4.

If $deg(x_{3})=3$ and $f_{3}$ is adjacent to some end face $f^{\prime}_{2}$,
then $G$ is not critical.

###### Proof.

Denote the face $f_{4}$ by $c_{1}b_{2}c_{2}$ and let $G_{L}=G[f_{3};f_{4}]$.
Consider the $(G_{L},G_{R},b_{2}c_{1})$-partition of graph $G$ and the
$(G^{\prime}_{L},G_{R},b_{2}c_{1})$-partition of graph
$G_{2}=\\{a_{1},a_{3}\\}$, where
$G^{\prime}_{L}=G_{L}\setminus\\{a_{1},a_{3}\\}$. Again, our goal is to find a
constant $c>0$ such that $i(G)\geq c\cdot i(G_{2})$ and $\partial_{4}(G)\leq
c\cdot\partial_{4}(G_{2})$. We have

$i(G)=i(G_{L})\cdot\mathcal{I}_{00}+i(G_{L},c^{+}_{1})\cdot\mathcal{I}_{01}+i(G_{L},b^{+}_{2})\cdot\mathcal{I}_{10}=12\cdot\mathcal{I}_{00}+5\cdot\mathcal{I}_{01}+4\cdot\mathcal{I}_{10};$
$i(G_{2})=i(G^{\prime}_{L})\cdot\mathcal{I}_{00}+i(G^{\prime}_{L},c^{+}_{1})\cdot\mathcal{I}_{01}+i(G^{\prime}_{L},b^{+}_{2})\cdot\mathcal{I}_{10}=5\cdot\mathcal{I}_{00}+2\cdot\mathcal{I}_{01}+2\cdot\mathcal{I}_{10}.$

Since $\mathcal{I}_{00}\geq\max(\mathcal{I}_{01},\mathcal{I}_{10})$, we have
$i(G)>\frac{16}{7}\cdot i(G_{2})$. Moreover,

$\partial_{4}(G)=3\cdot\mathcal{D}_{11}+(2\cdot\mathcal{D}^{3}_{10}+\mathcal{D}^{2}_{10})+(\mathcal{D}^{4}_{01}+\mathcal{D}^{3}_{01})+\mathcal{D}^{32}_{00};$
$\partial_{4}(G_{2})=2\cdot\mathcal{D}_{11}+\mathcal{D}^{3}_{10}+\mathcal{D}^{3}_{01}+\mathcal{D}^{22}_{00}.$

We now show that

$3\cdot\mathcal{D}_{11}+(2\cdot\mathcal{D}^{3}_{10}+\mathcal{D}^{2}_{10})+(\mathcal{D}^{4}_{01}+\mathcal{D}^{3}_{01})+\mathcal{D}^{32}_{00}\leq\frac{16}{7}\cdot(2\cdot\mathcal{D}_{11}+\mathcal{D}^{3}_{10}+\mathcal{D}^{3}_{01}+\mathcal{D}^{22}_{00}).$

It is sufficient to prove the inequality

$\mathcal{D}^{2}_{10}+\mathcal{D}^{4}_{01}+\mathcal{D}^{32}_{00}\leq\frac{11}{7}\cdot\mathcal{D}_{11}+\frac{2}{7}\cdot\mathcal{D}^{3}_{10}+\frac{9}{7}\cdot\mathcal{D}^{3}_{01}.$

If $|V(G_{R})|=2$, then $\mathcal{D}^{2}_{10}=\mathcal{D}^{32}_{00}=0$ and we
are done. Otherwise by Lemma 1 we have
$2\cdot\mathcal{D}^{3}_{01}\geq\mathcal{D}^{4}_{01}$ and
$\mathcal{D}^{3}_{01}\geq\mathcal{D}^{32}_{00}$, therefore

$\mathcal{D}^{2}_{10}+\frac{6}{7}\cdot\mathcal{D}^{4}_{01}\leq\frac{11}{7}\cdot\mathcal{D}_{11}+\frac{2}{7}\cdot\mathcal{D}^{3}_{10}.$

This completes the proof. ∎

In the rest of the chapter we assume that $deg(x_{3})=2$ and denote the face
$f_{4}$ by $b_{2}c_{1}c_{2}$.

######  Lemma 5.

If $deg(x_{4})=3$, then $G$ is not critical.

###### Proof.

Let $G_{L}=G[f_{4};f_{5}]$. and $f^{\prime}_{3}$ be the face adjacent to
$f_{4}$, other than $f_{3}$ and $f_{5}$. We have two cases depending on the
location of $f^{\prime}_{3}$.

Case 1. $f^{\prime}_{3}$ contains the edge $b_{2}c_{2}$. We consider the
$(G_{L},G_{R},c_{1}c_{2})$-partition of $G$.

Subcase 1. $deg(x^{\prime}_{3})=1$. Let
$G_{3}=G\setminus\\{a_{1},a_{2},a_{3}\\}$. Consider the
$(G^{\prime}_{L},G_{R},c_{1}c_{2})$-partition of $G_{3}$, where
$G^{\prime}_{L}=G_{L}\setminus\\{a_{1},a_{2},a_{3}\\}$. We have

$i(G)=16\cdot\mathcal{I}_{00}+7\cdot\mathcal{I}_{01}+10\cdot\mathcal{I}_{10}>3\cdot(5\cdot\mathcal{I}_{00}+2\cdot\mathcal{I}_{01}+2\cdot\mathcal{I}_{10})=3\cdot
i(G_{3});$
$\partial_{4}(G)=4\cdot\mathcal{D}_{11}+(2\cdot\mathcal{D}^{3}_{10}+\mathcal{D}^{2}_{10})+(3\cdot\mathcal{D}^{3}_{01}+\mathcal{D}^{2}_{01})+(2\cdot\mathcal{D}^{22}_{00}+\mathcal{D}^{11}_{00});$
$\partial_{4}(G_{3})=2\cdot\mathcal{D}_{11}+\mathcal{D}^{3}_{10}+\mathcal{D}^{3}_{01}+\mathcal{D}^{22}_{00}.$

Clearly, $\partial_{4}(G)\leq 3\cdot\partial_{4}(G_{3})<3\cdot i(G_{3})\leq
i(G)$, as required.

Subcase 2. $deg(x^{\prime}_{3})=3$. By the previous lemma, $f^{\prime}_{3}$ is
adjacent to some end faces $f^{\prime}_{2}$ and $f^{\prime\prime}_{2}$. We
have

$i(G)=39\cdot\mathcal{I}_{00}+14\cdot\mathcal{I}_{01}+25\cdot\mathcal{I}_{10}\geq
26\cdot(\mathcal{I}_{00}+\mathcal{I}_{01}+\mathcal{I}_{10})=26\cdot i(G_{R});$
$\partial_{4}(G)=7\cdot\mathcal{D}_{11}+(3\cdot\mathcal{D}^{4}_{10}+\mathcal{D}^{3}_{10})+(4\cdot\mathcal{D}^{4}_{01}+\mathcal{D}^{3}_{01})+(2\cdot\mathcal{D}^{12}_{00}+\mathcal{D}^{01}_{00}).$

By Lemma 1, we have $\partial_{4}(G)\leq
19\cdot\mathcal{D}_{11}<26\cdot\partial_{4}(G_{R})$.

Subcase 3. $deg(x^{\prime}_{3})=2$ and $deg(b_{2})=6$. In this case
$f^{\prime}_{3}$ is adjacent to a face $f^{\prime}_{2}$ which is adjacent to
end faces $f^{\prime}_{1}$ and $f^{\prime\prime}_{1}$. Therefore,

$i(G)=59\cdot\mathcal{I}_{00}+14\cdot\mathcal{I}_{01}+35\cdot\mathcal{I}_{10}\geq
36\cdot(\mathcal{I}_{00}+\mathcal{I}_{01}+\mathcal{I}_{10})=36\cdot i(G_{R});$
$\partial_{4}(G)=11\cdot\mathcal{D}_{11}+(6\cdot\mathcal{D}^{3}_{01}+2\cdot\mathcal{D}^{2}_{01})+(3\cdot\mathcal{D}^{4}_{10}+\mathcal{D}^{3}_{10})+2\cdot(\mathcal{D}^{24}_{00}+\mathcal{D}^{13}_{00})$
$\leq 26\cdot\mathcal{D}_{11}=26\cdot\partial_{4}(G_{R}).$

Subcase 4. $deg(x^{\prime}_{3})=2$ and $deg(b_{2})=8$. Again, $f^{\prime}_{3}$
is adjacent to a face $f^{\prime}_{2}$ which is adjacent to end faces
$f^{\prime}_{1}$ and $f^{\prime\prime}_{1}$. Therefore,

$i(G)=53\cdot\mathcal{I}_{00}+35\cdot\mathcal{I}_{01}+35\cdot\mathcal{I}_{10}\geq
41\cdot(\mathcal{I}_{00}+\mathcal{I}_{01}+\mathcal{I}_{10})=41\cdot i(G_{R});$
$\partial_{4}(G)\leq 4\cdot\partial_{4}(G,b^{+}_{2},c^{+}_{2})=4\cdot
10\cdot\mathcal{D}_{11}\leq 40\cdot i(G_{R}).$

Case 2. The face $f^{\prime}_{3}$ contains the edge $c_{1}c_{2}$. Consider the
$(G_{L},G_{R},b_{2}c_{2})$-partition of $G$.

Subcase 1. $deg(x^{\prime}_{3})=1$. Let
$G_{3}=G\setminus\\{a_{1},a_{2},a_{3}\\}$. Consider the
$(G^{\prime}_{L},G_{R},b_{2}c_{2})$-partition of $G_{3}$, where
$G^{\prime}_{L}=G_{L}\setminus\\{a_{1},a_{2},a_{3}\\}$. We have

$i(G)=19\cdot\mathcal{I}_{00}+7\cdot\mathcal{I}_{01}+4\cdot\mathcal{I}_{10}>3\cdot(5\cdot\mathcal{I}_{00}+2\cdot\mathcal{I}_{01}+2\cdot\mathcal{I}_{10})=3\cdot
i(G_{3});$
$\partial_{4}(G)=5\cdot\mathcal{D}_{11}+3\cdot\mathcal{D}^{3}_{10}+\mathcal{D}^{4}_{01}+\mathcal{D}^{42}_{00}\leq
3\cdot(2\cdot\mathcal{D}_{11}+\mathcal{D}^{3}_{10}+\mathcal{D}^{3}_{01}+\mathcal{D}^{22}_{00})=3\cdot\partial_{4}(G_{3}).$

By Lemma 1, we have
$\mathcal{D}_{11}+3\cdot\mathcal{D}^{3}_{01}>\mathcal{D}^{42}_{00}+\mathcal{D}^{4}_{01}$,
as required.

Subcase 2. $deg(x^{\prime}_{3})=3$. By the previous lemma, $f^{\prime}_{3}$ is
adjacent to end faces $f^{\prime}_{2}$ and $f^{\prime\prime}_{2}$. We have

$i(G)=45\cdot\mathcal{I}_{00}+14\cdot\mathcal{I}_{01}+10\cdot\mathcal{I}_{10}\geq
23\cdot(\mathcal{I}_{00}+\mathcal{I}_{01}+\mathcal{I}_{10})=23\cdot i(G_{R});$
$\partial_{4}(G)=8\cdot\mathcal{D}_{11}+(3\cdot\mathcal{D}^{4}_{10}+2\cdot\mathcal{D}^{3}_{10})+3\cdot\mathcal{D}^{4}_{01}+\mathcal{D}^{43}_{00}\leq
17\cdot\mathcal{D}_{11}<23\cdot\partial_{4}(G_{R}).$

Subcase 3. $deg(x^{\prime}_{3})=2$ and $deg(c_{1})=4$. $f^{\prime}_{3}$ is
adjacent to a face $f^{\prime}_{2}$ which is adjacent to end faces
$f^{\prime}_{1}$ and $f^{\prime\prime}_{1}$. We have

$i(G)=74\cdot\mathcal{I}_{00}+14\cdot\mathcal{I}_{01}+14\cdot\mathcal{I}_{10}\geq
34\cdot(\mathcal{I}_{00}+\mathcal{I}_{01}+\mathcal{I}_{10})=34\cdot i(G_{R});$
$\partial_{4}(G)=13\cdot\mathcal{D}_{11}+3\cdot\mathcal{D}^{4}_{10}+3\cdot\mathcal{D}^{4}_{01}+\mathcal{D}^{44}_{00}\leq
20\cdot\mathcal{D}_{11}<34\cdot\partial_{4}(G_{R}).$

Subcase 4. $deg(x^{\prime}_{3})=2$ and $deg(c_{1})=6$. $f^{\prime}_{3}$ is
adjacent to a face $f^{\prime}_{2}$ which is adjacent to end faces
$f^{\prime}_{1}$ and $f^{\prime\prime}_{1}$. We have

$i(G)=59\cdot\mathcal{I}_{00}+35\cdot\mathcal{I}_{01}+14\cdot\mathcal{I}_{10}>36\cdot(\mathcal{I}_{00}+\mathcal{I}_{01}+\mathcal{I}_{10})=36\cdot
i(G_{R});$ $\partial_{4}(G)\leq
3\cdot\partial_{4}(G,b^{+}_{2},c^{+}_{2})+\partial_{4}(G,b^{-}_{2},c^{-}_{2})=3\cdot
11\cdot\mathcal{D}_{11}+(2\cdot\mathcal{D}^{42}_{00}+\mathcal{D}^{31}_{00})$

By Lemma 1, we have $\partial_{4}(G)\leq 36\cdot\mathcal{D}_{11}\leq
36\cdot\partial_{4}(G_{R})$. ∎

######  Lemma 6.

If $deg(x_{3})=deg(x_{4})=2$ and $deg(c_{1})=3$, then $G$ is not critical.

###### Proof.

If $deg(x_{3})=deg(x_{4})=2$ and $deg(c_{1})=3$, then $f_{5}$ contains
$b_{2}c_{2}$. Let $G_{L}=G[f_{3};f_{4}]$. For the
$(G_{L},G_{R},b_{2}c_{1})$-partition of $G$ we have

$i(G)=7\cdot\mathcal{I}_{00}+5\cdot\mathcal{I}_{01}+2\cdot\mathcal{I}_{10}>4\cdot(\mathcal{I}_{00}+\mathcal{I}_{01}+\mathcal{I}_{10})=4\cdot
i(G_{R});$
$\partial_{4}(G)=\partial_{4}(G,b^{+}_{2},c^{+}_{1})+\partial_{4}(G,b^{-}_{2},c^{+}_{1})=3\cdot\mathcal{D}_{11}+\mathcal{D}^{4}_{01}\leq
4\cdot\mathcal{D}_{11}\leq\partial_{4}(G_{R}).$

Therefore, $G$ is not critical. ∎

######  Lemma 7.

If $deg(x_{3})=deg(x_{4})=2$ and $deg(x_{5})=3$, then $G$ is not critical.

###### Proof.

We denote the faces $f_{2},f_{3},f_{4}$ by
$a_{2}b_{1}b_{2},b_{1}b_{2}c_{1},b_{2}c_{1}c_{2}$ respectively. By the
previous lemma, $deg(c_{1})\geq 4$ and the face $f_{5}$ corresponds to the
triangle $c_{1}c_{2}d_{1}$. Let $f^{\prime}_{4}$ be the face adjacent to
$f_{5}$, other than $f_{4}$ and $f_{6}$. Let $G_{L}=G[f_{5};f_{6}]$. There are
two possible cases depending on the location of $f^{\prime}_{4}$ in $G$.

Case 1. The face $f^{\prime}_{4}$ contains the edge $c_{1}d_{1}$. Let $d_{0}$
be the third vertex of $f^{\prime}_{4}$. Consider the
$(G_{L},G_{R},c_{2}d_{1})$-partition of $G$.

Subcase 1a. $deg(x^{\prime}_{4})=1$ and
$\min(deg_{G}(c_{2}),deg_{G}(d_{1}))\geq 5$. Consider the graph
$G_{6}=G\setminus\\{a_{1},a_{2},a_{3},b_{1},b_{2},d_{0}\\}$ and the
$(G_{L}\cap V(G_{6}),G_{R},c_{2}d_{1})$-partition of $G_{6}$. We have

$i(G)=23\cdot\mathcal{I}_{00}+9\cdot\mathcal{I}_{01}+14\cdot\mathcal{I}_{10}>10\cdot(2\cdot\mathcal{I}_{00}+\mathcal{I}_{01}+\mathcal{I}_{10})=10\cdot
i(G_{6}).$

We now prove that

$\partial_{4}(G)=7\cdot\mathcal{D}_{11}+(4\cdot\mathcal{D}^{3}_{10}+2\cdot\mathcal{D}^{2}_{10})+(3\cdot\mathcal{D}^{3}_{01}+3\cdot\mathcal{D}^{2}_{01})+(3\cdot\mathcal{D}^{22}_{00}+\mathcal{D}^{12}_{00})\leq$
$10\cdot(\mathcal{D}_{11}+\mathcal{D}^{2}_{10}+\mathcal{D}^{2}_{01}+\mathcal{D}^{11}_{00})=10\cdot\partial_{4}(G_{6}).$

It remains to show that

$3\cdot\mathcal{D}_{11}+8\cdot\mathcal{D}^{2}_{10}+7\cdot\mathcal{D}^{2}_{01}\geq
4\cdot\mathcal{D}^{3}_{10}+3\cdot\mathcal{D}^{3}_{01}+3\cdot\mathcal{D}^{22}_{00}+\mathcal{D}^{12}_{00}.$

Since $\min(deg(a),deg(c))\geq 5$, we have
$3\cdot\mathcal{D}^{2}_{10}\geq\mathcal{D}^{3}_{10}$ and
$3\cdot\mathcal{D}^{2}_{01}\geq\mathcal{D}^{3}_{01}$ by Lemma 1. Moreover,
$\min(\mathcal{D}^{2}_{01},\mathcal{D}^{2}_{10})\geq\mathcal{D}^{22}_{00}$. If
$deg(a)=5$, then $\mathcal{D}^{12}_{00}=0$ and we are done. If $deg(a)\geq 6$,
then $2\cdot\mathcal{D}^{2}_{01}\geq\mathcal{D}^{3}_{01}$ and we are done.

Subcase 1b. $deg(x^{\prime}_{4})=1$ and $\min(deg(a),deg(c))=4$. Consider the
graph $G_{4}=G\setminus\\{a_{1},a_{2},a_{3},b_{1}\\}$ and the $(G_{L}\cap
V(G_{4}),G_{R},c_{2}d_{1})$-partition of $G_{4}$. We have

$i(G)=23\cdot\mathcal{I}_{00}+9\cdot\mathcal{I}_{01}+14\cdot\mathcal{I}_{10}\geq\frac{9}{2}\cdot(5\cdot\mathcal{I}_{00}+2\cdot\mathcal{I}_{01}+2\cdot\mathcal{I}_{10})=\frac{9}{2}\cdot
i(G_{4}).$

We now prove that

$\partial_{4}(G)=7\cdot\mathcal{D}_{11}+(4\cdot\mathcal{D}^{3}_{10}+2\cdot\mathcal{D}^{2}_{10})+(3\cdot\mathcal{D}^{3}_{01}+3\cdot\mathcal{D}^{2}_{01})+(3\cdot\mathcal{D}^{22}_{00}+\mathcal{D}^{11}_{00})\leq$
$\frac{9}{2}\cdot(2\cdot\mathcal{D}_{11}+\mathcal{D}^{3}_{10}+\mathcal{D}^{3}_{01}+\mathcal{D}^{22}_{00})=\frac{9}{2}\cdot\partial_{4}(G_{4}).$

It suffices to show that

$2\cdot\mathcal{D}_{11}+\frac{1}{2}\cdot\mathcal{D}^{3}_{10}+\frac{3}{2}\cdot\mathcal{D}^{3}_{01}\geq
2\cdot\mathcal{D}^{2}_{10}+3\cdot\mathcal{D}^{2}_{01}.$

Since $\min(deg(a),deg(c))=4$, we have
$\textrm{min}(\mathcal{D}^{2}_{10},\mathcal{D}^{2}_{01})=0$, therefore the
inequality holds.

Subcase 2. $deg(x^{\prime}_{4})=3$. The face $f^{\prime}_{4}$ is adjacent to
some faces $f^{\prime}_{3}$ and $f^{\prime\prime}_{3}$. By the previous
lemmas, both $f^{\prime}_{3}$ and $f^{\prime\prime}_{3}$ are end faces.
Therefore,

$i(G)=55\cdot\mathcal{I}_{00}+18\cdot\mathcal{I}_{01}+35\cdot\mathcal{I}_{10}\geq
36\cdot(\mathcal{I}_{00}+\mathcal{I}_{01}+\mathcal{I}_{10})=36\cdot i(G_{R});$
$\partial_{4}(G)\leq
2\cdot\partial_{4}(G,c^{+}_{2},d^{+}_{2})+2\cdot\partial_{4}(G,c^{+}_{2},d^{-}_{2})=2\cdot(11\cdot\mathcal{D}_{11}+4\cdot\mathcal{D}^{4}_{10}+2\cdot\mathcal{D}^{3}_{10})$
$\leq 34\cdot\mathcal{D}_{11}<36\cdot\partial_{4}(G_{R}).$

In the remaining subcases we consider the induced subgraph $G^{\prime}$ of $G$
with the vertex set $(V(G)\setminus V(G_{L}))\cup\\{b_{2},c_{2},d_{2}\\}$ and
the $(G^{\prime}_{L},G_{R},c_{1}d_{1})$-partition of $G$, where
$G^{\prime}_{L}$ is an induced subgraph of $G_{L}$ with the vertex set
$\\{b_{2},c_{1},c_{2},d_{0},d_{1}\\}$.

Subcase 3. $deg(x^{\prime}_{4})=deg(x^{\prime}_{3})=2$. The face
$f^{\prime}_{3}$ is adjacent to some face $f^{\prime}_{2}$. By Lemma 3
$f^{\prime}_{2}$ is adjacent to end faces $f^{\prime}_{1}$ and
$f^{\prime\prime}_{1}$. Moreover, by the previous lemmas, the faces
$f^{\prime}_{3}$ and $f^{\prime}_{4}$ does not contain any vertices of degree
3.

Subcase 3a. $deg(c_{1})\geq 6$. If $deg(c_{1})\geq 7$, then $deg(d_{0})=3$, a
contradiction. Suppose that $deg(c_{1})=6$.

$i(G)=106\cdot\mathcal{I}_{00}+63\cdot\mathcal{I}_{01}+63\cdot\mathcal{I}_{10}>20\cdot(5\cdot\mathcal{I}_{00}+2\cdot\mathcal{I}_{01}+2\cdot\mathcal{I}_{10})=20\cdot
i(G^{\prime});$ $\partial_{4}(G)\leq
25\cdot\mathcal{D}_{11}+(12\cdot\mathcal{D}^{3}_{10}+10\cdot\mathcal{D}^{2}_{10})+(12\cdot\mathcal{D}^{3}_{01}+10\cdot\mathcal{D}^{2}_{01})$
$+9\cdot\mathcal{D}^{22}_{00}+3\cdot\mathcal{D}^{21}_{00}+3\cdot\mathcal{D}^{12}_{00}+4\cdot\mathcal{D}^{11}_{00}$
$\leq
25\cdot\mathcal{D}_{11}+22\cdot\mathcal{D}^{3}_{10}+22\cdot\mathcal{D}^{3}_{01}+19\cdot\mathcal{D}^{22}_{00}$
$<20\cdot(2\cdot\mathcal{D}_{11}+\mathcal{D}^{3}_{10}+\mathcal{D}^{3}_{01}+\mathcal{D}^{22}_{00})=20\cdot\partial_{4}(G^{\prime}).$

Subcase 3b. $deg(c_{1})=5$. If $deg_{G_{L}}(d_{1})\geq 5$, then $deg(d_{0})=3$
and we use Lemma 6. Suppose that $deg_{G_{L}}(d_{1})=4$ and
$deg_{G_{L}}(d_{0})=5$. We have

$i(G)=116\cdot\mathcal{I}_{00}+45\cdot\mathcal{I}_{01}+63\cdot\mathcal{I}_{10}>23\cdot(5\cdot\mathcal{I}_{00}+2\cdot\mathcal{I}_{01}+2\cdot\mathcal{I}_{10})=23\cdot
i(G^{\prime});$
$\partial_{4}(G)=28\cdot\mathcal{D}_{11}+(8\cdot\mathcal{D}^{4}_{10}+14\cdot\mathcal{D}^{3}_{10}+2\cdot\mathcal{D}^{2}_{10})+(12\cdot\mathcal{D}^{3}_{01}+10\cdot\mathcal{D}^{2}_{01})$
$+(6\cdot D^{23}_{00}+3\cdot D^{22}_{00}+2\cdot D^{13}_{00}+1\cdot
D^{12}_{00})\leq$ $\leq
28\cdot\mathcal{D}_{11}+8\cdot\mathcal{D}_{11}+16\cdot\mathcal{D}^{3}_{10}+22\cdot\mathcal{D}^{3}_{01}+8\cdot\mathcal{D}_{11}+4\cdot\mathcal{D}^{22}_{00}$
$\leq
23\cdot(2\cdot\mathcal{D}_{11}+\mathcal{D}^{3}_{10}+\mathcal{D}^{3}_{01}+\mathcal{D}^{22}_{00})\leq
23\cdot\partial_{4}(G^{\prime}).$

Subcase 4. $deg(x^{\prime}_{4})=2$, $deg(x^{\prime}_{3})=3$. This is possible
only if $f^{\prime}_{3}$ is adjacent to end faces, otherwise we use Lemma 5.

Subcase 4a. $deg(c_{1})=7$. The face $f^{\prime}_{3}$ is adjacent to two end
faces by Lemmas 3 and 6. We have

$i(G)=73\cdot\mathcal{I}_{00}+45\cdot\mathcal{I}_{01}+49\cdot\mathcal{I}_{10}>14\cdot(5\cdot\mathcal{I}_{00}+2\cdot\mathcal{I}_{01}+2\cdot\mathcal{I}_{10})=14\cdot
i(G^{\prime});$ $\partial_{4}(G)\leq
15\cdot\mathcal{D}_{11}+15\cdot\mathcal{D}^{3}_{10}+15\cdot\mathcal{D}^{3}_{01}+15\cdot\mathcal{D}^{22}_{00}$
$<14\cdot(2\cdot\mathcal{D}_{11}+\mathcal{D}^{3}_{10}+\mathcal{D}^{3}_{01}+\mathcal{D}^{22}_{00})\leq
14\cdot\partial_{4}(G^{\prime}).$

Subcase 4b. $deg(c_{1})=5$, $deg(x^{\prime}_{4})=2$, $deg(x^{\prime}_{3})=2$.
The face $f^{\prime}_{3}$ is adjacent to two end faces by Lemmas 3 and 6. We
have

$i(G)=88\cdot\mathcal{I}_{00}+18\cdot\mathcal{I}_{01}+49\cdot\mathcal{I}_{10}>15\cdot(5\cdot\mathcal{I}_{00}+2\cdot\mathcal{I}_{01}+2\cdot\mathcal{I}_{10})=15\cdot
i(G^{\prime});$ $\partial_{4}(G)\leq
18\cdot\mathcal{D}_{11}+6\cdot\mathcal{D}^{4}_{10}+(9\cdot\mathcal{D}^{3}_{01}+9\cdot\mathcal{D}^{2}_{01})+(3\cdot\mathcal{D}^{23}_{00}+\mathcal{D}^{13}_{00})$
$<15\cdot(2\cdot\mathcal{D}_{11}+\mathcal{D}^{3}_{10}+\mathcal{D}^{3}_{01}+\mathcal{D}^{22}_{00})\leq
14\cdot\partial_{4}(G^{\prime}).$

Case 2. The face $f^{\prime}_{4}$ corresponds to the triangle
$c_{2}d_{1}d_{2}$. We consider the $(G_{L},G_{R},c_{1}d_{1})$-partition of
$G$.

Subcase 1. $deg(x^{\prime}_{4})=1$. Consider the graph
$G_{4}=G\setminus\\{a_{1},a_{2},a_{3},b_{1}\\}$ and the $(G_{L}\cap
V(G_{4}),G_{R},c_{2}d_{1})$-partition of $G_{4}$. We have

$i(G)=25\cdot\mathcal{I}_{00}+9\cdot\mathcal{I}_{01}+10\cdot\mathcal{I}_{10}\geq\frac{34}{7}\cdot(5\cdot\mathcal{I}_{00}+2\cdot\mathcal{I}_{01}+2\cdot\mathcal{I}_{10})=\frac{34}{7}\cdot
i(G_{4}).$

Moreover,

$\partial_{4}(G)=7\cdot\mathcal{D}_{11}+4\cdot\mathcal{D}^{3}_{10}+(2\cdot\mathcal{D}^{4}_{01}+\mathcal{D}^{3}_{01})+(2\cdot\mathcal{D}^{32}_{00}+\mathcal{D}^{22}_{00})\leq$
$\frac{34}{7}\cdot(2\cdot\mathcal{D}_{11}+\mathcal{D}^{3}_{10}+\mathcal{D}^{3}_{01}+\mathcal{D}^{22}_{00})=\frac{34}{7}\cdot\partial_{4}(G_{4}).$

It suffices to show that

$\frac{19}{7}\cdot\mathcal{D}_{11}+\frac{6}{7}\cdot\mathcal{D}^{3}_{10}+\frac{27}{7}\cdot\mathcal{D}^{3}_{01}\geq
2\cdot\mathcal{D}^{4}_{01}+2\cdot\mathcal{D}^{32}_{00}.$

By Lemma 1, we have $\mathcal{D}_{11}>\mathcal{D}^{4}_{01}$ and
$\mathcal{D}^{3}_{01}>\mathcal{D}^{32}_{00}$, thus the inequality holds.

Subcase 2. $deg(x^{\prime}_{4})=3$. We assume that $f^{\prime}_{4}$ is
adjacent to end faces $f^{\prime}_{3}$ and $f^{\prime\prime}_{3}$ (it was
shown in the previous case that the other configurations are not possible).
Therefore,

$i(G)=59\cdot\mathcal{I}_{00}+18\cdot\mathcal{I}_{01}+25\cdot\mathcal{I}_{10}\geq
34\cdot(\mathcal{I}_{00}+\mathcal{I}_{01}+\mathcal{I}_{10})=34\cdot i(G_{R});$
$\partial_{4}(G)=12\cdot\mathcal{D}_{11}+(4\cdot\mathcal{D}^{4}_{10}+3\cdot\mathcal{D}^{3}_{10})+(4\cdot\mathcal{D}^{4}_{01}+4\cdot\mathcal{D}^{4}_{01})+2\cdot\mathcal{D}^{33}_{00}+\mathcal{D}^{23}_{00}$
$\leq 30\cdot\mathcal{D}_{11}<34\cdot\partial_{4}(G_{R}).$

In the remaining subcases we consider the induced subgraph $G^{\prime\prime}$
of $G$ with the vertex set $(V(G)\setminus
V(G_{L}))\cup\\{b_{2},c_{2},d_{2}\\}$ and the
$(G^{\prime}_{L},G_{R},c_{1}d_{1})$-partition of $G$, where $G^{\prime}_{L}$
is an induced subgraph of $G_{L}$ with the vertex set
$\\{b_{2},c_{2},d_{2},c_{1},d_{1}\\}$.

Subcase 3. $deg(x^{\prime}_{4})=deg(x^{\prime}_{3})=2$. As in the previous
case, $f^{\prime}_{3}$ is adjacent to some face $f^{\prime}_{2}$ which is
adjacent to end faces $f^{\prime}_{1}$ and $f^{\prime\prime}_{1}$. Again, we
assume that the faces $f^{\prime}_{3}$ and $f^{\prime}_{4}$ does not contain
vertices of degree 3.

Subcase 3a. $deg(c_{2})\geq 5$. If $deg(c_{2})=7$, then $deg(d_{2})=3$, a
contradiction. Thus we assume that $deg(c_{2})=5$ and $d_{2}$ belongs to
$f^{\prime}_{2}$ and $f^{\prime}_{3}$. Therefore,

$i(G)=116\cdot\mathcal{I}_{00}+63\cdot\mathcal{I}_{01}+45\cdot\mathcal{I}_{10}\geq
23\cdot(5\cdot\mathcal{I}_{00}+2\cdot\mathcal{I}_{01}+2\cdot\mathcal{I}_{10})=20\cdot
i(G^{\prime\prime});$ $\partial_{4}(G)\leq
24\cdot\mathcal{D}_{11}+12\cdot(\mathcal{D}^{4}_{10}+\mathcal{D}^{3}_{10})+8\cdot(\mathcal{D}^{4}_{01}+\mathcal{D}^{3}_{01})+12\cdot\mathcal{D}^{32}_{00}$
$<20\cdot(2\cdot\mathcal{D}_{11}+\mathcal{D}^{3}_{10}+\mathcal{D}^{3}_{01}+\mathcal{D}^{22}_{00})=20\cdot\partial_{4}(G^{\prime\prime}).$

Subcase 3b. $deg(c_{2})=4$. If $deg(d_{2})=3$, the we apply Lemma. We assume
that $deg(d_{2})=5$. Therefore,

$i(G)=130\cdot\mathcal{I}_{00}+45\cdot\mathcal{I}_{01}+45\cdot\mathcal{I}_{10}>24\cdot(5\cdot\mathcal{I}_{00}+2\cdot\mathcal{I}_{01}+2\cdot\mathcal{I}_{10})=24\cdot
i(G^{\prime\prime});$
$\partial_{4}(G)=25\cdot\mathcal{D}_{11}+(8\cdot\mathcal{D}^{4}_{10}+4\cdot\mathcal{D}^{3}_{10})+(8\cdot\mathcal{D}^{4}_{01}+4\cdot\mathcal{D}^{3}_{01})+(4\cdot\mathcal{D}^{22}_{00}+2\cdot\mathcal{D}^{32}_{00}+2\cdot\mathcal{D}^{23}_{00}+\mathcal{D}^{22}_{00});$
$\partial_{4}(G)\leq
24\cdot(2\cdot\mathcal{D}_{11}+\mathcal{D}^{3}_{10}+\mathcal{D}^{3}_{01}+\mathcal{D}^{22}_{00})=24\cdot\partial_{4}(G^{\prime\prime}).$

Subcase 4. $deg(x^{\prime}_{4})=2$, $deg(x^{\prime}_{3})=3$. As in the
previous case, it is possible only if $f^{\prime}_{3}$ is adjacent to two end
faces.

Subcase 4a. $deg(c_{2})=6$. We have

$i(G)=77\cdot\mathcal{I}_{00}+45\cdot\mathcal{I}_{01}+35\cdot\mathcal{I}_{10}>15\cdot(5\cdot\mathcal{I}_{00}+2\cdot\mathcal{I}_{01}+2\cdot\mathcal{I}_{10})=15\cdot
i(G^{\prime\prime});$ $\partial_{4}(G)\leq
16\cdot\mathcal{D}_{11}+(8\cdot\mathcal{D}^{3}_{10}+3\cdot\mathcal{D}^{2}_{10})+(6\cdot\mathcal{D}^{4}_{01}+6\cdot\mathcal{D}^{3}_{01}+\mathcal{D}^{2}_{01})+(4\cdot\mathcal{D}^{32}_{00}+2\cdot\mathcal{D}^{22}_{00}+2\cdot\mathcal{D}^{21}_{00}+\mathcal{D}^{11}_{00})$
$\leq
16\cdot\mathcal{D}_{11}+11\cdot\mathcal{D}^{3}_{10}+13\cdot\mathcal{D}^{4}_{01}+9\cdot\mathcal{D}^{32}_{00}\leq
15\cdot(2\cdot\mathcal{D}_{11}+\mathcal{D}^{3}_{10}+\mathcal{D}^{3}_{01}+\mathcal{D}^{22}_{00})\leq
15\cdot\partial_{4}(G^{\prime\prime}).$

Subcase 4b. $deg(c_{2})=4$. We have

$i(G)=98\cdot\mathcal{I}_{00}+18\cdot\mathcal{I}_{01}+35\cdot\mathcal{I}_{10}>16\cdot(5\cdot\mathcal{I}_{00}+2\cdot\mathcal{I}_{01}+2\cdot\mathcal{I}_{10})=16\cdot
i(G^{\prime\prime});$ $\partial_{4}(G)\leq
18\cdot\mathcal{D}_{11}+4\cdot\mathcal{D}^{4}_{10}+(6\cdot\mathcal{D}^{4}_{01}+3\cdot\mathcal{D}^{3}_{01})+2\cdot(\mathcal{D}^{34}_{00}+\mathcal{D}^{24}_{00})$
$\leq
18\cdot\mathcal{D}_{11}+4\cdot\mathcal{D}^{4}_{10}+9\cdot\mathcal{D}^{4}_{01}+3\cdot\mathcal{D}^{34}_{00}$
$<16\cdot(2\cdot\mathcal{D}_{11}+\mathcal{D}^{3}_{10}+\mathcal{D}^{3}_{01}+\mathcal{D}^{22}_{00})\leq
16\cdot\partial_{4}(G^{\prime\prime}).$

∎

######  Lemma 8.

If $deg(x_{3})=deg(x_{4})=deg(x_{5})=deg(x_{6})=2$, then $G$ is not critical.

###### Proof.

We denote the faces $f_{2},f_{3},f_{4}$ by
$a_{2}b_{1}b_{2},b_{1}b_{2}c_{1},b_{2}c_{1}c_{2}$ respectively. By Lemma 6, we
have $deg(c_{1})\geq 4$. There are three possible cases.

Case 1. $deg(c_{1})\geq 5$. In this case $deg(c_{2})=3$, the face $f_{5}$
contains $c_{1}c_{2}$ and $c_{1}$ belongs to $f_{6}$. Let
$G_{L}=G[f_{4};f_{5}]$. Consider the $(G_{L},G_{R},c_{1}c_{2})$-partition of
$G$.

$i(G)=9\cdot\mathcal{I}_{00}+7\cdot\mathcal{I}_{01}+5\cdot\mathcal{I}_{10}\geq
7\cdot(\mathcal{I}_{00}+\mathcal{I}_{01}+\mathcal{I}_{10})=7\cdot i(G_{R});$
$\partial_{4}(G)=4\cdot\mathcal{D}_{11}+(2\cdot\mathcal{D}^{3}_{01}+\mathcal{D}^{2}_{01})\leq
7\cdot\mathcal{D}_{11}\leq 7\cdot\partial_{4}(G_{R}).$

In the remaining cases we denote the faces $f_{5}$ and $f_{6}$ by
$c_{1}c_{2}d_{1}$ and $c_{2}d_{1}d_{2}$ respectively.

Case 2. $deg(c_{2})\geq 5$. In this case $deg(d_{1})=3$. Let
$G_{L}=G[f_{5};f_{6}]$. Consider the $(G_{L},G_{R},c_{2}d_{1})$-partition of
$G$.

$i(G)=14\cdot\mathcal{I}_{00}+9\cdot\mathcal{I}_{01}+7\cdot\mathcal{I}_{10}>10\cdot(\mathcal{I}_{00}+\mathcal{I}_{01}+\mathcal{I}_{10})=10\cdot
i(G_{R});$
$\partial_{4}(G)=\partial_{4}(G,c^{+}_{2},d^{+}_{1})+\partial_{4}(G,c^{-}_{2},d^{+}_{1})=6\cdot\mathcal{D}_{11}+3\cdot\mathcal{D}^{3}_{01}+\mathcal{D}^{2}_{01}\leq\partial_{4}(G_{R}).$

Case 3. $deg(c_{1})=deg(c_{2})=4$. Let $G_{L}=G[f_{4};f_{5}]$. Consider the
$(G_{L},G_{R},c_{1}c_{2})$-partition of $G$ and the
$(G^{\prime}_{L},G_{R},c_{1}c_{2})$-partition of the graph
$G_{3}=G\setminus\\{a_{1},a_{2},a_{3}\\}$, where
$G^{\prime}_{L}=G_{L}\setminus\\{a_{1},a_{2},a_{3}\\}$.

First, we show that $\mathcal{I}_{00}\leq\mathcal{I}_{01}+\mathcal{I}_{10}$.
Denote by $G^{\prime}_{R}$ the induced subgraph of $G_{R}$ with the vertex set
$V(G_{R})\setminus\\{c_{1},c_{2}\\}$. Clearly,

$\mathcal{I}_{00}=i(G^{\prime}_{R}),\
\mathcal{I}_{10}=i(G^{\prime}_{R},d^{-}_{1}),\
\mathcal{I}_{01}=i(G^{\prime}_{R},d^{-}_{1},d^{-}_{2}).$

Therefore, $\mathcal{I}_{10}>\mathcal{I}_{01}$ and
$\mathcal{I}_{00}-\mathcal{I}_{10}=i(G^{\prime}_{R},d^{+}_{1})\leq\mathcal{I}_{01}$.
We have

$i(G)=9\cdot\mathcal{I}_{00}+7\cdot\mathcal{I}_{01}+5\cdot\mathcal{I}_{10}\geq\frac{10}{3}\cdot(3\cdot\mathcal{I}_{00}+2\cdot\mathcal{I}_{01}+1\cdot\mathcal{I}_{10})=\frac{10}{3}\cdot
i(G_{1}).$

Moreover,

$\partial_{4}(G)=4\cdot\mathcal{D}_{11}+3\cdot\mathcal{D}^{2}_{10}+2\cdot
D^{3}_{01},\
\partial_{4}(G^{\prime})=\mathcal{D}_{11}+\mathcal{D}^{2}_{10}+D^{3}_{01}.$

It remains to show that
$\partial_{4}(G)\leq\frac{10}{3}\cdot\partial_{4}(G^{\prime})$ or
$\mathcal{D}_{11}\leq 2\cdot\mathcal{D}^{3}_{01}$. Indeed,
$\mathcal{D}_{11}-\mathcal{D}^{3}_{01}$ equals to the number of 4-DS of
$G_{R}$ which contain $c_{1}$ and $c_{2}$ and does not contain $d_{1}$ and
$\mathcal{D}^{3}_{01}$ equals to the number of 4-DS which contain
$c_{1},c_{2}$ and $d_{1}$. For every 4-DS $D$ of $G_{R}$ such that
$d_{1}\notin D$, the set $D\cup\\{d_{1}\\}$ is also a 4-DS of $G_{R}$, thus
the inequality holds. ∎

######  Lemma 9.

If $deg(x_{3})=deg(x_{4})=deg(x_{5})=2$ and $deg(x_{6})=3$, then $G$ is not
critical.

###### Proof.

Denote the faces $f_{5}$ and $f_{6}$ by $c_{1}c_{2}d_{1}$ and
$c_{2}d_{1}d_{2}$ respectively. Let $f^{\prime}_{5}$ be the face adjacent to
$f_{6}$ other than $f_{5}$ and $f_{7}$. By Lemma 8, $deg(c_{1})=4$ and
$deg(c_{2})\geq 5$. Let $G_{L}=G[f_{4};f_{5}]$. We assume that $G_{L}$
contains at most one face of degree 3 except $f_{2}$, which is adjacent to two
end faces. By previous lemmas, $G_{L}$ contains no vertices of degree 3. There
are two possible cases depending on the location of $f^{\prime}_{5}$ in $G$.

Case 1. $f^{\prime}_{5}$ contains the edge $c_{2}d_{2}$. Denote by $c_{3}$ the
third vertex of $f^{\prime}_{5}$. In each of the following subcases we
consider the partition $(G_{L},G_{R},d_{1}d_{2})$ of the graph $G$ and the
partition $(G^{\prime}_{L},G_{R},d_{1}d_{2})$ of the graph $G^{\prime}$, where
$G^{\prime}$ is a spanning subgraph of $G$ with the vertex set $(V(G)\setminus
V(G_{L}))\cup\\{c_{1},c_{2},c_{3},d_{1},d_{2}\\}$. Clearly,

$\partial_{4}(G^{\prime})=2\cdot\mathcal{D}_{11}+\mathcal{D}^{3}_{10}+\mathcal{D}^{3}_{01}+\mathcal{D}^{22}_{00}.$

It is not hard to check using Lemma 1, that in all subcases below we have
$i(G)>\partial_{4}(G)$, therefore $G$ is not critical.

Subcase 1. $deg(x^{\prime}_{5})=1$.

$i(G)=35\cdot\mathcal{I}_{00}+14\cdot\mathcal{I}_{01}+18\cdot\mathcal{I}_{10}>7\cdot(5\cdot\mathcal{I}_{00}+2\cdot\mathcal{I}_{01}+2\cdot\mathcal{I}_{10})=7\cdot
i(G^{\prime});$
$\partial_{4}(G)=10\cdot\mathcal{D}_{11}+(6\cdot\mathcal{D}^{3}_{10}+3\cdot\mathcal{D}^{2}_{10})+(4\cdot\mathcal{D}^{3}_{01}+4\cdot\mathcal{D}^{2}_{01})+4\cdot\mathcal{D}^{22}_{00}.$

Subcase 2. $deg(x^{\prime}_{5})=3$ and $f^{\prime}_{5}$ is adjacent to some
faces $f^{\prime}_{4}$ and $f^{\prime\prime}_{4}$. By the previous lemmas,
both $f^{\prime}_{4}$ and $f^{\prime\prime}_{4}$ are end faces. Therefore,

$i(G)=70\cdot\mathcal{I}_{00}+28\cdot\mathcal{I}_{01}+45\cdot\mathcal{I}_{10}>14\cdot(5\cdot\mathcal{I}_{00}+2\cdot\mathcal{I}_{01}+2\cdot\mathcal{I}_{10})=7\cdot
i(G^{\prime});$
$\partial_{4}(G)=22\cdot\mathcal{D}_{11}+(6\cdot\mathcal{D}^{4}_{10}+4\cdot\mathcal{D}^{3}_{10})+(8\cdot\mathcal{D}^{3}_{01}+4\cdot\mathcal{D}^{2}_{01})+(4\cdot\mathcal{D}^{23}_{00}+4\cdot\mathcal{D}^{12}_{00}).$

Subcase 3. $deg(x^{\prime}_{5})=2$ and $f^{\prime}_{4}$ is adjacent to end
faces $f^{\prime}_{3}$ and $f^{\prime\prime}_{3}$. Two configurations are
possible:

Subcase 3a. $deg(c_{2})=7$ and $c_{2}$ belong to $f^{\prime}_{4}$.

$i(G)=98\cdot\mathcal{I}_{00}+70\cdot\mathcal{I}_{01}+63\cdot\mathcal{I}_{10}>19\cdot(5\cdot\mathcal{I}_{00}+2\cdot\mathcal{I}_{01}+2\cdot\mathcal{I}_{10})=19\cdot
i(G^{\prime});$ $\partial_{4}(G)\leq
22\cdot(\mathcal{D}_{11}+\mathcal{D}^{3}_{10}+\mathcal{D}^{3}_{01}+\mathcal{D}^{22}_{00})\leq
19\cdot(2\cdot\mathcal{D}_{11}+\mathcal{D}^{3}_{10}+\mathcal{D}^{3}_{01}+\mathcal{D}^{22}_{00}).$

Subcase 3b. $deg(c_{2})=5$ and $c_{2}$ does not belong to $f^{\prime}_{4}$.

$i(G)=98\cdot\mathcal{I}_{00}+28\cdot\mathcal{I}_{01}+63\cdot\mathcal{I}_{10}>18\cdot(5\cdot\mathcal{I}_{00}+2\cdot\mathcal{I}_{01}+2\cdot\mathcal{I}_{10})=7\cdot
i(G^{\prime});$
$\partial_{4}(G)=26\cdot\mathcal{D}_{11}+10\cdot\mathcal{D}^{4}_{10}+(12\cdot\mathcal{D}^{3}_{01}+8\cdot\mathcal{D}^{2}_{01})+4\cdot\mathcal{D}^{24}_{00};$

Subcase 4. $deg(x^{\prime}_{5})=deg(x^{\prime}_{4})=2$ and $f^{\prime}_{3}$ is
adjacent to end faces $f^{\prime}_{2}$ and $f^{\prime\prime}_{2}$. Since
$G_{L}$ has no vertices of degree 3 in $G$, only two configurations are
possible:

Subcase 4a. $deg(c_{2})=6$.

$i(G)=161\cdot\mathcal{I}_{00}+98\cdot\mathcal{I}_{01}+81\cdot\mathcal{I}_{10}>32\cdot(5\cdot\mathcal{I}_{00}+2\cdot\mathcal{I}_{01}+2\cdot\mathcal{I}_{10})=32\cdot
i(G^{\prime});$ $\partial_{4}(G)\leq
36\cdot(\mathcal{D}_{11}+\mathcal{D}^{3}_{10}+\mathcal{D}^{3}_{01}+\mathcal{D}^{22}_{00})\leq
36\cdot(2\cdot\mathcal{D}_{11}+\mathcal{D}^{3}_{10}+\mathcal{D}^{3}_{01}+\mathcal{D}^{22}_{00}).$

Subcase 4b. $deg(c_{2})=5$.

$i(G)=175\cdot\mathcal{I}_{00}+70\cdot\mathcal{I}_{01}+81\cdot\mathcal{I}_{10}>35\cdot(5\cdot\mathcal{I}_{00}+2\cdot\mathcal{I}_{01}+2\cdot\mathcal{I}_{10})=35\cdot
i(G^{\prime});$
$\partial_{4}(G)=39\cdot\mathcal{D}_{11}+(12\cdot\mathcal{D}^{4}_{10}+14\cdot\mathcal{D}^{3}_{10})+(16\cdot\mathcal{D}^{3}_{01}+16\cdot\mathcal{D}^{2}_{01})+8\cdot\mathcal{D}^{33}_{00}+4\cdot\mathcal{D}^{23}_{00};$
$\partial_{4}(G^{\prime})=2\cdot\mathcal{D}_{11}+\mathcal{D}^{3}_{10}+\mathcal{D}^{3}_{01}+\mathcal{D}^{22}_{00}.$

Subcase 5. $deg(x^{\prime}_{5})=deg(x^{\prime}_{4})=deg(x^{\prime}_{3})=2$ and
$f^{\prime}_{2}$ is adjacent to end faces $f^{\prime}_{1}$ and
$f^{\prime\prime}_{1}$. Again, since $G_{L}$ has no vertices of degree 3 in
$G$, only two configurations are possible:

Subcase 5a. $deg(c_{2})=6$.

$i(G)=245\cdot\mathcal{I}_{00}+126\cdot\mathcal{I}_{01}+126\cdot\mathcal{I}_{10}>49\cdot(5\cdot\mathcal{I}_{00}+2\cdot\mathcal{I}_{01}+2\cdot\mathcal{I}_{10})=49\cdot
i(G^{\prime});$ $\partial_{4}(G)\leq
52\cdot(\mathcal{D}_{11}+\mathcal{D}^{3}_{10}+\mathcal{D}^{3}_{01}+\mathcal{D}^{22}_{00})\leq
52\cdot(2\cdot\mathcal{D}_{11}+\mathcal{D}^{3}_{10}+\mathcal{D}^{3}_{01}+\mathcal{D}^{22}_{00}).$

Subcase 5b. $deg(c_{2})=5$.

$i(G)=259\cdot\mathcal{I}_{00}+98\cdot\mathcal{I}_{01}+126\cdot\mathcal{I}_{10}>51\cdot(5\cdot\mathcal{I}_{00}+2\cdot\mathcal{I}_{01}+2\cdot\mathcal{I}_{10})=52\cdot
i(G^{\prime});$
$\partial_{4}(G)=52\cdot\mathcal{D}_{11}+(18\cdot\mathcal{D}^{4}_{10}+18\cdot\mathcal{D}^{3}_{10}+3\cdot\mathcal{D}^{2}_{10})+(24\cdot\mathcal{D}^{3}_{01}+16\cdot\mathcal{D}^{2}_{01})+12\cdot\mathcal{D}^{23}_{00}+4\cdot\mathcal{D}^{22}_{00}.$

Case 2. $f^{\prime}_{5}$ contains the edge $d_{1}d_{2}$. Denote by $d_{3}$ the
third vertex of $f^{\prime}_{5}$. In each of the following subcases we
consider the partition $(G_{L},G_{R},d_{1}d_{2})$ of the graph $G$ and the
partition $(G^{\prime}_{L},G_{R},d_{1}d_{2})$ of the graph $G^{\prime}$, where
$G^{\prime}$ is a spanning subgraph of $G$ with the vertex set $(V(G)\setminus
V(G_{L}))\cup\\{c_{1},c_{2},d_{1},d_{2},d_{3}\\}$. Clearly, we have

$\partial_{4}(G^{\prime})=2\cdot\mathcal{D}_{11}+\mathcal{D}^{3}_{10}+\mathcal{D}^{3}_{01}+\mathcal{D}^{22}_{00}.$

It is not hard to check using Lemma 1, that in all subcases below we have
$i(G)>\partial_{4}(G)$.

Subcase 1. $deg(x^{\prime}_{5})=1$.

$i(G)=37\cdot\mathcal{I}_{00}+14\cdot\mathcal{I}_{01}+14\cdot\mathcal{I}_{10}>7\cdot(5\cdot\mathcal{I}_{00}+2\cdot\mathcal{I}_{01}+2\cdot\mathcal{I}_{10})=7\cdot
i(G^{\prime});$
$\partial_{4}(G)=10\cdot\mathcal{D}_{11}+6\cdot\mathcal{D}^{3}_{10}+(3\cdot\mathcal{D}^{4}_{01}+\mathcal{D}^{3}_{01})+(3\cdot\mathcal{D}^{32}_{00}+\mathcal{D}^{22}_{00}).$

Subcase 2. $deg(x^{\prime}_{5})=3$, $f^{\prime}_{5}$ is adjacent to end faces
$f^{\prime}_{4}$ and $f^{\prime\prime}_{4}$.

$i(G)=70\cdot\mathcal{I}_{00}+28\cdot\mathcal{I}_{01}+45\cdot\mathcal{I}_{10}>14\cdot(5\cdot\mathcal{I}_{00}+2\cdot\mathcal{I}_{01}+2\cdot\mathcal{I}_{10})=7\cdot
i(G^{\prime});$
$\partial_{4}(G)=16\cdot\mathcal{D}_{11}+(6\cdot\mathcal{D}^{4}_{10}+4\cdot\mathcal{D}^{3}_{10})+(6\cdot\mathcal{D}^{4}_{01}+5\cdot\mathcal{D}^{3}_{01}+\mathcal{D}^{2}_{01})+(3\cdot\mathcal{D}^{23}_{00}+\mathcal{D}^{12}_{00}).$

Subcase 3. $deg(x^{\prime}_{5})=2$ and $f^{\prime}_{4}$ is adjacent to end
faces $f^{\prime}_{3}$ and $f^{\prime\prime}_{3}$. Two configurations are
possible:

Subcase 3a. $deg(d_{1})=6$, $d_{1}$ belongs to $f^{\prime}_{4}$.

$i(G)=116\cdot\mathcal{I}_{00}+70\cdot\mathcal{I}_{01}+49\cdot\mathcal{I}_{10}>23\cdot(5\cdot\mathcal{I}_{00}+2\cdot\mathcal{I}_{01}+2\cdot\mathcal{I}_{10})=23\cdot
i(G^{\prime});$
$\partial_{4}(G)=22\cdot\mathcal{D}_{11}+12\cdot\mathcal{D}^{3}_{10}+4\cdot\mathcal{D}^{3}_{10}+(9\cdot\mathcal{D}^{4}_{01}+6\cdot\mathcal{D}^{3}_{01}+\mathcal{D}^{2}_{01})+4\cdot(6\cdot\mathcal{D}^{32}_{00}+2\cdot\mathcal{D}^{22}_{00}).$

Subcase 3b. $deg(d_{1})=4$, $d_{1}$ does not belong to $f^{\prime}_{4}$.

$i(G)=98\cdot\mathcal{I}_{00}+28\cdot\mathcal{I}_{01}+49\cdot\mathcal{I}_{10}>18\cdot(5\cdot\mathcal{I}_{00}+2\cdot\mathcal{I}_{01}+2\cdot\mathcal{I}_{10})=7\cdot
i(G^{\prime});$
$\partial_{4}(G)=26\cdot\mathcal{D}_{11}+6\cdot\mathcal{D}^{4}_{10}+(3\cdot\mathcal{D}^{3}_{01}+2\cdot\mathcal{D}^{2}_{01})+3\cdot\mathcal{D}^{34}_{00}+2\cdot\mathcal{D}^{24}_{00}.$

Subcase 4. $deg(x^{\prime}_{5})=deg(x^{\prime}_{4})=2$ and $f^{\prime}_{3}$ is
adjacent to two end faces $f^{\prime}_{2}$ and $f^{\prime\prime}_{2}$.

Subcase 4a. $deg(d_{1})=5$.

$i(G)=171\cdot\mathcal{I}_{00}+98\cdot\mathcal{I}_{01}+63\cdot\mathcal{I}_{10}>33\cdot(5\cdot\mathcal{I}_{00}+2\cdot\mathcal{I}_{01}+2\cdot\mathcal{I}_{10})=25\cdot
i(G^{\prime});$
$\partial_{4}(G)=36\cdot\mathcal{D}_{11}+(18\cdot\mathcal{D}^{3}_{10}+14\cdot\mathcal{D}^{2}_{10})+(12\cdot\mathcal{D}^{4}_{01}+10\cdot\mathcal{D}^{3}_{01}+2\cdot\mathcal{D}^{2}_{01})+9\cdot\mathcal{D}^{32}_{00}+3\cdot\mathcal{D}^{22}_{00}.$

Subcase 4b. $deg(d_{1})=4$.

$i(G)=189\cdot\mathcal{I}_{00}+70\cdot\mathcal{I}_{01}+63\cdot\mathcal{I}_{10}>35\cdot(5\cdot\mathcal{I}_{00}+2\cdot\mathcal{I}_{01}+2\cdot\mathcal{I}_{10})=35\cdot
i(G^{\prime});$
$\partial_{4}(G)=36\cdot\mathcal{D}_{11}+(12\cdot\mathcal{D}^{4}_{10}+6\cdot\mathcal{D}^{3}_{10})+(12\cdot\mathcal{D}^{4}_{01}+4\cdot\mathcal{D}^{3}_{01})+12\cdot\mathcal{D}^{33}_{00}.$

Subcase 5. $deg(x^{\prime}_{5})=deg(x^{\prime}_{4})=deg(x^{\prime}_{3})=2$ and
$x^{\prime}_{2}$ is adjacent to two end faces $x^{\prime}_{1}$ and
$x^{\prime\prime}_{1}$.

Subcase 5a. $deg(d_{1})=5$.

$i(G)=259\cdot\mathcal{I}_{00}+126\cdot\mathcal{I}_{01}+98\cdot\mathcal{I}_{10}>51\cdot(5\cdot\mathcal{I}_{00}+2\cdot\mathcal{I}_{01}+2\cdot\mathcal{I}_{10})=51\cdot
i(G^{\prime});$
$\partial_{4}(G)=52\cdot\mathcal{D}_{11}+(24\cdot\mathcal{D}^{3}_{10}+16\cdot\mathcal{D}^{2}_{10})+(18\cdot\mathcal{D}^{4}_{01}+5\cdot\mathcal{D}^{3}_{01}+4\cdot\mathcal{D}^{2}_{01})+12\cdot\mathcal{D}^{32}_{00}+4\cdot\mathcal{D}^{22}_{00}.$

Subcase 5b. $deg(d_{1})=4$.

$i(G)=277\cdot\mathcal{I}_{00}+98\cdot\mathcal{I}_{01}+98\cdot\mathcal{I}_{10}>52\cdot(5\cdot\mathcal{I}_{00}+2\cdot\mathcal{I}_{01}+2\cdot\mathcal{I}_{10})=52\cdot
i(G^{\prime});$
$\partial_{4}(G)=52\cdot\mathcal{D}_{11}+(18\cdot\mathcal{D}^{4}_{10}+6\cdot\mathcal{D}^{3}_{10})+(18\cdot\mathcal{D}^{4}_{01}+6\cdot\mathcal{D}^{3}_{01})+16\cdot\mathcal{D}^{33}_{00}.$

∎

Lemmas 2–9 imply the main result of this paper.

######  Theorem 1.

For every outerplanar graph $G$ we have $i(G)>\partial_{4}(G)$.

##  4 Concluding remarks

It seems that the following generalization of Theorem 1 is true.

######  Conjecture 1.

For every graph $G$ with the average vertex degree at most $k\geq 1$ the
inequality $i(G)\geq\partial_{k}(G)$ holds. Moreover, equality occurs if and
only if $G$ is $k$-regular.

Although we are unable to prove this statement even for $k=4$, it is easy to
obtain a similar result for the class of trees.

######  Theorem 2.

For every tree $T$ we have $i(T)>\partial_{2}(T)$.

###### Proof.

Clearly, for every tree with at most 3 vertices the inequality holds. Let $T$
be a $n$-vertex tree such that $i(T)\leq\partial_{2}(T)$ and for every tree
$T^{\prime}$ such that $|V(T^{\prime})|<|V(T)|$ we have
$i(T^{\prime})>\partial_{2}(T^{\prime})$. Consider a diametral path
$X=x_{1}x_{2}x_{3}\ldots x_{k}$ in $T$. If $k\leq 3$ then $\partial_{2}(T)\leq
2$ and $i(G)\geq 5$, thus we assume that $k\geq 4$. Let $T_{2}$ (resp.
$T_{3}$) be the maximal by inclusion subtree of $T$ such that $x_{2},x_{3}\in
V(T_{2})$ and $deg(x_{2})=1$ (resp. $x_{3},x_{4}\in V(T_{3})$ and
$deg(x_{3})=1$). Since all neighbors of $x_{2}$, except possibly $x_{3}$,
belong to every 2-DS of $T$, we have

$\partial_{2}(T)=\partial_{2}(T,x^{+}_{2})+\partial_{2}(T,x^{-}_{2})\leq\partial_{2}(T_{2})+\partial_{2}(T_{3}).$

On the other hand,

$i(T)=i(T,x^{-}_{1})+i(T,x^{+}_{1})\geq i(T_{2})+i(T_{3}).$

Since $i(T_{2})>\partial_{2}(T_{2})$ and $i(T_{3})>\partial_{2}(T_{3})$, we
have $i(T)>\partial_{2}(T)$.

∎

##  5 Acknowledgements

This work was performed at the Saint Petersburg Leonhard Euler International
Mathematical Institute and supported by the Ministry of Science and Higher
Education of the Russian Federation (agreement no. 075–15–2022–287).

## References

  * [1] D. Bród, Z. Skupien, Trees with extremal numbers of dominating sets. Australas. J Comb., 35, 273–290, 2006.
  * [2] D. S. Taletskii, Trees with extremal numbers of $k$-dominating sets. Discrete Mathematics, 345, 112656, 2022.
  * [3] Z. L. Nagy, On the Number of $k$‐Dominating Independent Sets. Journal of Graph Theory, 84(4), 566–580, 2015.
  * [4] D. Gerbner, B. Keszegh, A. Methuku, B. Patk’os, M. Vizer. An improvement on the maximum number of $k$-dominating independent sets. Journal of Graph Theory, 91(4), 88–97, 2017.
  * [5] J. W. Moon, L. Moser, On cliques in graphs. Israel Journal of Mathematics, 3, 23–28, 1965.
  * [6] A. F. Alameddine, Bounds on the Fibonacci number of a maximal outerplanar graph, The Fibonacci Quarterly, 36.3, 206–210, 1998.