#  Complete characterization of the minimal-ABC trees

###### Abstract

The problem of characterizing trees with minimal atom-bond-connectivity index
(minimal-ABC trees) has a reputation as one of the most demanding recent open
optimization problems in mathematical chemistry. Here firstly, we give an
affirmative answer to the conjecture, which states that enough large minimal-
ABC trees are comprised solely of a root vertex and so-called $D_{z}$\- and
$D_{z+1}$-branches. Based on the presented theoretical results here and some
already known results, we obtain enough constraints to reduce the search space
and solve the optimization problem, and thus, determine exactly the minimal-
ABC trees of a given arbitrary order.

Keywords: Molecular descriptors, atom-bond connectivity index, extremal graphs

AMS subject classification: 05C35, 05C90, 92E10

Darko Dimitrova,b, Zhibin Duc

aHochschule für Technik und Wirtschaft Berlin, Germany
bFaculty of Information Studies, Novo mesto, Slovenia
E-mail<EMAIL_ADDRESS>
cSchool of Software, South China Normal University, Guangdong 528225, China

E-mail<EMAIL_ADDRESS>
##  1 Introduction

The atom-bond connectivity (ABC) index is one of the most investigated
molecular structure descriptors, which was proved to be applicable for
practical purposes. It was introduced by Estrada et al. [26] in $1998$, who
showed that there is an excellent (linear) correlation between the ABC index
and the experimental heats of formation of alkanes. Ten years later, an
inventive explanation of this topological index based on quantum theory was
provided in [25]. The applicative potentiality of the ABC index was further
supported in [36] by Gutman et al. As a result of those seminal works, the ABC
index attracted the attention of mathematicians, chemists, and computer
scientists, which resulted in many theoretical and computational results [1,
2, 3, 4, 5, 22, 7, 8, 11, 9, 12, 15, 16, 18, 20, 21, 24, 25, 26, 27, 28, 29,
30, 32, 34, 35, 33, 36, 38, 39, 40, 41, 44, 6, 45, 46, 47, 48, 49, 37].

Among remaining open problems, the problem of full characterization of trees,
whose ABC index is minimal (referred further as minimal-ABC trees), has a
reputation as one of the most demanding recent open problems in mathematical
chemistry.

The ABC index of a simple undirected graph $G=(V,E)$ with vertex set $V=V(G)$
and edge set $E=E(G)$ is defined as

$\displaystyle{\rm ABC}(G)=\sum_{uv\in E}\sqrt{\frac{d(u)+d(v)-2}{d(u)d(v)}},$

where $d(v)$ is the degree of a vertex $v\in V$.

A pendant vertex is a vertex of degree one. If the degree of a vertex is
larger than two and no vertex of degree two is adjacent to it, then the vertex
is called a big vertex. A path, whose one end-vertex has the degree of at
least three, the other end-vertex is a pendant vertex, and the rest of the
vertices have degree two, is called a pendant path.

A path of length two adjacent to a vertex that has at least one child of
degree at least three is called a $B_{1}$-branch. A vertex $v$ with degree
$k+1$, $k\geq 2$, together with $k$ pendant paths of length $2$ attached to
it, comprised a so-called $B_{k}$-branch. The vertex $v$ is referred to as the
center of the $B_{k}$-branch. By attaching a vertex to a pendant vertex of
$B_{k}$-branch, one obtains a so-called $B_{k}^{*}$-branch. Illustrations of
$B_{k}$-, $B_{k}^{*}$-, $k\geq 1$, and $B_{3}^{**}$-branches are given in
Figure 1. We will refer to them in general as $B$-branches.

Figure 1: $B_{k}$, $B_{k}^{*}$, $k\geq 1$ and $B_{3}^{**}$ branches.

For the further analysis, besides the $D_{z}$-branches, which were introduced
in [1], we consider here also the $D_{z}^{**}$, $D_{z,x}^{2}$ $(x=1,2)$ and
$D_{z,x}^{4}$ $(x=1,2,3,4)$ branches depicted in Figure 2, which may occur in
the minimal-ABC trees. We will refer to them in general as $D$-branches. The
vertex of a $D$-branch to whom the $B$-branches are attached is referred to as
the center of the $D$-branch. Later, in Lemma 1.13 it will be shown that
$D_{z,x}^{4}$\- $(x=1,2,3,4)$ branches does not exist in minimal-ABC trees.

Figure 2: $D_{z}$-, $D_{z}^{**}$-, $D_{z,x}^{2}$\- $(x=1,2)$ and
$D_{z,x}^{4}$\- $(x=1,2,3,4)$ branches. The dashed line segments are optional.

Here, we show that when the minimal-ABC trees are enough large then they do
not contain $B_{4}$, $B_{2}$, $B_{3}^{*}$, $B_{3}^{**}$ -branches, and
consequently there are no other kinds of $D$-branches except $D_{k}$ and
$D_{k+1}$-branches (see Corollary 5.3 and Theorem 5.4). As a corollary, we
have that the radius of large minimal-ABC trees is at most $4$. The presented
theoretical results here reduce further the search space considerably such
that the minimal-ABC trees of a given arbitrary order can be exactly
determined (see Section 5.1 and Appendix A.12).

###  1.1 Some prerequisite theoretical results

The following results are needed in some of the proofs later. More known
theoretical and computational results about minimal-ABC trees can be found in
[23, 19, 42].

######  Proposition 1.1 ([10]).

Let $h(x,y)=\sqrt{(x+y-2)/(xy)}$. The expression $-h(x,y)+h(x+\Delta
x,y-\Delta y)$ increases in $x$ and decreases in $y$, where $x,y,\Delta
x,\Delta y\in\mathbb{R}$ and $x,y\geq 2$, $\Delta x\geq 0$, $0\leq\Delta y<y$.

Proposition 1.1 can be re-stated in the following manner.

######  Proposition 1.2.

The expression $-h(x,y)+h(x-\Delta x,y+\Delta y)$ decreases in $x$ and
increases in $y$, where $x,y,\Delta x,\Delta y\in\mathbb{R}$ and $x,y\geq 2$,
$\Delta y\geq 0$, $0\leq\Delta x<x$.

Lin, Gao, Chen, and Lin [43], and Gan, Liu, and You in [31] contributed the
so-called switching transformation.

######  Lemma 1.3 (Switching transformation).

[43, 31] Let $pq$ and $rs$ be two edges of a connected graph $G=(V,E)$ such
that $ps,qr\notin E$. Let $G^{\prime}=G-pq-rs+ps+qr$. If $d(p)\geq d(r)$ and
$d(q)\leq d(s)$, then ${\rm ABC}(G^{\prime})\leq{\rm ABC}(G)$. The equality
holds if and only if $d(p)=d(r)$ or $d(q)=d(s)$.

The following result gives an upper bound on the possible number of
$B_{4}$-branches contained in a minimal-ABC tree.

######  Theorem 1.4 ([10]).

There are no more than 4 $B_{4}$-branches in a minimal-ABC tree.

Some forbidden combinations of branches are stated in the next theorems.

######  Theorem 1.5 ([17]).

A $B_{1}$-branch and a $B_{4}$-branch cannot exist simultaneously in a
minimal-ABC tree.

######  Theorem 1.6 ([17]).

A $B_{2}$-branch and a $B_{4}$-branch cannot exist simultaneously in a
minimal-ABC tree.

The following two conjectures have been arisen in [1].

######  Conjecture 1.1 ([1]).

The subgraph of a minimal-ABC tree induced by its big vertices is a star.

######  Conjecture 1.2 ([1]).

After some enough large $n$, besides the big vertices, minimal-ABC trees have
only $B_{3}$-branches.

Moreover, the structure of the minimal-ABC tree depicted in Figure 3, for
enough large trees, was conjectured in [1].

Figure 3: The figure from [1] with the conjectured structure of the minimal-
ABC tree.

Recently, in [14] it was shown that Conjecture 1.1 is true. Here we give also
an affirmative answer to Conjecture 1.2 and show that the conjectured
structure from Figure 3 is indeed the structure of the minimal-ABC trees, when
the degree of its root is at least $2838$.

The following results give bounds on the size $z$ of a $D_{z}$-branch and the
possible combinations of $D$-branches.

######  Lemma 1.7 ([14]).

For $z\leq 14$, there is no minimal-ABC tree, which has a $D_{z}$-branch.

######  Remark 1.1.

This result is also valid for other types of $D$-branches, which has been
proved in [14, Section 2]. In fact, somewhat better lower bounds are obtained
there, but the (weaker) unified lower bound $15$ is good enough for our need
throughout this paper.

######  Lemma 1.8 ([14]).

A minimal-ABC tree does not contain a $D_{z}$-branch, $z\geq 132$.

Actually, the proof of Lemma 1.8 is still valid for $D_{z}^{**}$-branches.

######  Lemma 1.9.

A minimal-ABC tree does not contain a $D_{z}^{**}$-branch, $z\geq 132$.

######  Lemma 1.10.

A minimal-ABC tree does not contain a $D_{z,x}^{2}$-branch, $z\geq 132$, for
each $x=1,2$.

###### Proof.

Here, in order to simplify our proof, we recall the transformation (shown in
Figure 4) used to establish Lemma 1.8 in [14], and show that such upper bound
$131$ is also valid for $D_{z,x}^{2}$-branches, $x=1,2$. We assume that
$z\equiv x\,(\bmod\,3)$ in Figure 4, other two cases are analogous.

Figure 4: The transformation referred in Lemma 1.10, where $z\equiv
x\,(\bmod\,3)$.

Let $A_{1}$ denote the change of ABC index after applying the transformation
depicted in Figure 4, in which all of $B$-branches occurring in $G$ outside
$\bar{G}$ are $B_{3}$-branches. If we replace $x$ $B_{3}$-branch(es) by
$B_{2}$-branch(es), $x=1,2$, then we get a transformation aiming to
$D_{z,x}^{2}$-branches, and denote by $A_{2,x}$ the change of ABC index, for
$x=1,2$.

In [14, Lemma 2.5], it is shown that $A_{1}<0$ when $z\geq 132$, so we can
conclude the desired result by noting that $A_{2,x}<A_{1}$ for $x=1,2$.
Indeed, it is easy to obtain that

$\displaystyle A_{2,x}-A_{1}$ $\displaystyle=$ $\displaystyle
x\left(\left(-f(z+1,3)+f\left(\frac{z-x}{3}+1,3\right)\right)-\left(-f(z+1,4)+f\left(\frac{z-x}{3}+1,4\right)\right)\right)<0.$

The negativity of the above difference follows by Proposition 1.2. ∎

######  Remark 1.2.

The upper bound $131$ is not optimal. One can improve it by considering the
particular structures of $D_{z,x}^{2}$-branches. Since we do not think that it
would affect significantly the subsequent proofs, we omit such a feasible
improvement.

######  Lemma 1.11.

A minimal-ABC tree does not contain a $D_{z,x}^{4}$-branch, $z\geq 216$, for
each $x=1,2,3,4$.

###### Proof.

We apply the transformation $\mathcal{T}_{2}$, depicted in Figure 5, to prove
the above result. The change of ABC index after applying $\mathcal{T}_{2}$ is

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle=$
$\displaystyle-f(d(v),z+1)+f(d(v),z)+(-f(d(v),d(w))+f(d(v),d(w)+1))+x(-f(z+1,5)+f(z,5))$
$\displaystyle-(z-x)f(z+1,4)+(z-x-1)f(z,4)+f(d(w)+1,4)+(d(w)-1)(-f(d(w),4)+f(d(w)+1,4)).$

Figure 5: Transformation used to derive an upper bound on the size of
$D_{z,x}^{4}$-branches, $x=1,2,3,4$.

From Propositions 1.1 and 1.2, $-f(d(v),z+1)+f(d(v),z)$ increases in $d(v)$,
thus

$\displaystyle-f(d(v),z+1)+f(d(v),z)$ $\displaystyle\leq$
$\displaystyle\lim_{d(z)\rightarrow+\infty}(-f(d(v),z+1)+f(d(v),z))\quad=\quad-\sqrt{\frac{1}{z+1}}+\sqrt{\frac{1}{z}},$

and $-f(d(v),d(w))+f(d(v),d(w)+1)$ decreases in $d(v)\geq z+1$, i.e.,

$-f(d(v),d(w))+f(d(v),d(w)+1)\leq-f(z+1,d(w))+f(z+1,d(w)+1).$

Moreover, it is not hard to verify that $-(z-x)f(z+1,4)+(z-x-1)f(z,4)$
increases in $z$ for each of fixed $1\leq x\leq 4$, and its limit is
$-\frac{1}{2}$ when $z$ goes to infinity, i.e.,

$-(z-x)f(z+1,4)+(z-x-1)f(z,4)<-\frac{1}{2}.$

Combining all above comments, it leads to an upper bound of
$ABC(G^{\prime})-ABC(G)$:

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle\leq$
$\displaystyle-\sqrt{\frac{1}{z+1}}+\sqrt{\frac{1}{z}}+(-f(z+1,d(w))+f(z+1,d(w)+1))+x(-f(z+1,5)$
$\displaystyle+f(z,5))-\frac{1}{2}+f(d(w)+1,4)+(d(w)-1)(-f(d(w),4)+f(d(w)+1,4)).$

The right-hand side of the above inequality decreases in $z$ and is negative
for $16\leq d(w)\leq 132$, $1\leq x\leq 4$ and $z=216$ (and so is for $z\geq
216$). ∎

######  Remark 1.3.

The above unified upper bound of $215$ can be improved by involving particular
structural properties of $D_{z,x}^{4}$-branches, but the current upper bound
suffices for our needs.

######  Proposition 1.12 ([13]).

Let $x$ and $y$ be vertices of a minimal-ABC tree $G$ that have a common
parent vertex $z$, such that $d(x)\geq d(y)\geq 5$. If $x$ and $y$ have only
$B_{3}$-branches as children, and at most one of them is $B_{3}^{**}$, then
either $d(y)=d(x)$ or $d(y)=d(x)-1$.

Next, we show that if a minimal-ABC tree has $B_{4}$-branches, then they must
be adjacent to the root.

######  Lemma 1.13.

Let $G$ be a minimal-ABC tree. Then all $B_{4}$-branches (maximum $4$) are
adjacent to the root vertex of $G$.

###### Proof.

Assume the opposite, that there is at least one $B_{4}$-branch attached to a
child of the root (i.e., some $D_{z,x}^{4}$-branch exists). Recall that
$15\leq z\leq 215$, from Remark 1.1 and Lemma 1.11. It is also worth
mentioning that the existence of $D_{z,x}^{4}$-branch allows us to set an
assumption that no $B_{3}$-branch is attached to the root vertex, due to the
switching transformation (Lemma 1.3). Then we move all such $B_{4}$-branches
to the root vertex (illustrated in Figure 6 and denoted as transformation
$\mathcal{T}_{3}$).

Figure 6: Transformation which helps us to show that all $B_{4}$-branches are
attached to the root vertex of a minimal-ABC tree.

After applying this transformation, the change of ABC index is

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle=$
$\displaystyle-f(d(v),z+1)+f(d(v)+x,z-x+1)-x\,f(z+1,5)-(z-x)f(z+1,4)$ (1)
$\displaystyle+(z-x)f(z-x+1,4)+x\,f(d(v)+x,5)+\sum_{i=1}^{d(v)-1}(-f(d(v),d(u_{i}))$
$\displaystyle+f(d(v)+x,d(u_{i}))),$

where $d(u_{i})$, $i=1,2,\dots,d(v)-1$, are the neighbors of $v$, except the
center of $D_{z,x}^{4}$-branch. We show that the right-hand side of (1) is
negative in Appendix A.11 111Due to interdependencies of the results in the
appendices, at the end of the paper they do not occur in the same order as
they appear in the main text., for $1\leq x\leq 4$ and $15\leq z\leq 215$,
which concludes the proof. ∎

######  Corollary 1.14.

A minimal-ABC tree does not contain $D_{z,x}^{4}$-branches, $x=1,2,3,4$.

##  2 The size of $D_{z}$-branches

Here we give an upper bound on the size $z$ of $D_{z}$-branches depending on
their occurrences in a minimal-ABC tree.

######  Lemma 2.1.

If a minimal-ABC tree contains at least $261$ $D_{z}$-branches, then $z\leq
52$.

###### Proof.

Assume that the minimal-ABC tree $G$ has (at least) $x$ $D_{z}$-branches.
Recall that from Lemma 1.8, we may assume that $z\leq 131$. We apply the
transformation $\mathcal{T}_{4}$ depicted in Figure 7.

Figure 7: The transformation which leads to upper bounds on the sizes of
$D_{z}$-branches depending on their occurrences in minimal-ABC trees.

The change of the ABC index after applying $\mathcal{T}_{4}$ is

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle=$ $\displaystyle-
xf(d(v),z+1)-x\,z\,f(z+1,4)-3f(4,2)-3f(2,1)$ (2)
$\displaystyle+n_{k}f(d(v)+7,k+1)+n_{k-1}f(d(v)+7,k)+kn_{k}f(k+1,4)+(k-1)n_{k-1}f(k,4)$
$\displaystyle+\sum_{i=1}^{d(v)-x}(-f(d(v),d(v_{i}))+f(d(v)+7,d(v_{i}))),$

where $d(v_{i})$, $i=1,\dots,d(v)-x$, are the children of $v$, which are in
$\overline{G}$ ($\overline{G^{\prime}}$). For fixed $z$, the parameters $x$,
$k$, $n_{k}$, $n_{k-1}$ must satisfy

$\displaystyle n_{k}+n_{k-1}=x+7\quad\text{and}\quad
kn_{k}+(k-1)n_{k-1}=x\,z-1.$ (3)

It can be shown that the right-hand side of (2) is always negative, for
$53\leq z\leq 131$ and $x\geq 261$. Detailed proofs and results (for every
particular $z$) are presented in Appendix A.1. ∎

######  Lemma 2.2.

A minimal-ABC tree with a root of degree at least $3249$ cannot contain more
than $364$ $D_{z}$-branches, for $15\leq z\leq 51$.

###### Proof.

Consider the transformation $\mathcal{T}_{5}$ depicted in Figure 8.

Figure 8: The transformation which leads to upper bounds on the sizes of
$D_{z}$-branches depending on their occurrences in minimal-ABC trees and the
degrees of their root vertices.

The change of the ABC index after applying $\mathcal{T}_{5}$ is

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle=$
$\displaystyle-x\,f(d(v),z+1)-x\,z\,f(z+1,4)+3f(4,2)+3f(2,1)$ (4)
$\displaystyle+n_{k}f(d(v)-7,k+1)+n_{k-1}f(d(v)-7,k)+kn_{k}f(k+1,4)$
$\displaystyle+(k-1)n_{k-1}f(k,4)+\sum_{i=1}^{d(v)-x}(-f(d(v),d(v_{i}))+f(d(v)-7,d(v_{i})))$

with constraints

$\displaystyle n_{k}+n_{k-1}=x-7\quad\text{and}\quad
kn_{k}+(k-1)n_{k-1}=x\,z+1,$ (5)

where $d(v_{i})$, $i=1,\dots,d(v)-x$, are the children of $v$, which are in
$\overline{G}$ ($\overline{G^{\prime}}$). It can be shown that the right-hand
side of (4) is always negative, for $15\leq z\leq 51$, $d(v)\geq x\geq 365$.
We present detailed proofs and particular results, for every $z$, in Appendix
A.2. ∎

##  3 $B$-branches adjacent to the root

By Lemma 1.13, if there are $B_{4}$-branches in a minimal-ABC tree, then they
must be attached to the root. Also, the $B_{2}$-branches cannot be attached to
the root, otherwise, we can apply a switching transformation (Lemma 1.3)
between one $B_{2}$-branch attached to the root and one $B_{3}$-branch from a
$D$-branch. Using the same argumentation, we can also assume that there is no
$B_{3}^{**}$-branch attached to the root.

######  Lemma 3.1.

The number of $B$-branches adjacent to the root vertex of a minimal-ABC tree
is at most $919$.

###### Proof.

Assume that there are at least $x$ $B$-branches ($B_{3}$\- and
$B_{4}$-branches) adjacent to the root vertex $v$ (possibly there are other
branches adjacent to $v$, besides the $x$ $B$-branches). Recall that there are
at most $4$ $B_{4}$-branches, and assume that all $B_{4}$-branches are counted
in the $x$ $B$-branches. We apply the transformation $\mathcal{T}_{6}$
depicted in Figure 9.

Figure 9: The transformation which helps us to obtain an upper bound on the
number of $B$-branches attached to the root (the dashed line segments are
optional).

After applying $\mathcal{T}_{6}$, the change of the ABC index is

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{d(v)-x}(-f(d(v),d(v_{i}))+f(d(v^{\prime}),d(v_{i})))-f(d(v),4)+f(d(v^{\prime}),53)$
(6) $\displaystyle+6(-f(2,1)+f(d(v^{\prime}),53))+364(-f(d(v),4)+f(53,4))$
$\displaystyle+(x-365-n_{4})(-f(d(v),4)+f(d(v^{\prime}),4))+n_{4}(-f(d(v),5)+f(d(v^{\prime}),5)),\qquad$

where $d(v^{\prime})=d(v)-358$, $n_{4}$ is the number of $B_{4}$-branches
attached to $v$, and $v_{i}$, $i=1,\dots,d(v)-x$, are the vertices adjacent to
$v$ in $\overline{G}$ ($\overline{G^{\prime}}$). It is worth mentioning that
$v_{i}$ is the center of either a $D$-branch or a $B_{3}$-branch. When $x\geq
920$, it can be verified that the right-hand side of (6) is always negative.
We present the detailed proofs and particular results, for every possible
combination of $D$-branches, in Appendix A.3. ∎

###  3.1 Existence of $B_{4}$-branches

Here, we show that if a minimal-ABC tree is large enough, then it does not
contain $B_{4}$-branches.

######  Lemma 3.2.

A minimal-ABC tree, whose root has a degree of at least $1228$, does not
contain $B_{4}$-branches.

###### Proof.

Assume that there exists at least one $B_{4}$-branch in a minimal-ABC tree
$G$. The existence of $B_{4}$-branch means that $B_{1}$\- or $B_{2}$-branches
would not occur, from Theorems 1.5 and 1.6, so each $D$-branch occurring in
$G$ should be a $D_{z}$-branch for some $z$.

Let us consider first the case when $G$ contains a combination of $D_{49}$\-
and $D_{48}$-branches. Since $d(v)\geq 1228$, by Lemma 2.2 (Table 2), there
can be at most $121$ $D_{49}$-branches and $91$ $D_{48}$-branches. By Lemma
3.1, there cannot be more than $919$ $B$-branches attached to the root vertex-
actually in the case with a combination of $D_{49}$\- and $D_{48}$-branches
there cannot be more than $824$ $B$-branches attached to the root vertex (see
Table 4). Thus, in this case it holds that $d(v)\leq 121+91+824=1036<1228$,
which is a contradiction to the initial assumption that $d(v)\geq 1228$.
Similarly, we can show that the cases when $G$ contains a combination
$D_{z}$\- and $D_{z-1}$-branches, for $15\leq z\leq 48$ and $55\leq z\leq
131$, are not possible.

It remains to prove the claim of the lemma when $G$ contains $D_{49}$\- and
$D_{50}$-branches; $D_{50}$\- and $D_{51}$-branches; $D_{51}$\- and
$D_{52}$-branches; $D_{52}$\- and $D_{53}$-branches; and $D_{53}$\- and
$D_{54}$-branches. Consider the transformation from Figure 10. Recall that
there can be at most four $B_{4}$-branches and they are attached to the root
of the minimal-ABC tree, from Theorem 1.4 and Lemma 1.13, so in $\overline{G}$
there can be at most three $B_{4}$-branches, $B_{3}$-branches, and
$D$-branches.

Since a tree may contain a combination of $D_{z}$\- and $D_{z+1}$-branches,
with $49\leq z\leq 53$, the transformation $\mathcal{T}_{7}$ to be feasible,
there must be at least $2z-3$ $D_{z}$-branches or $2(z+1)-3$
$D_{z+1}$-branches. Observe that when this is not the case, then
$d(v)<2z-3+2(z+1)-3+919<1228$, and thus the transformation $\mathcal{T}_{7}$
can be applied. Therefore, to be consistent with the notation in Figure 10, we
further assume that $G$ contains (at least) $2z-3$ $D_{z}$-branches, $49\leq
z\leq 54$, and in addition to possibly either $D_{z-1}$-branches or
$D_{z+1}$-branches.

Figure 10: Suggested transformation, which shows that there are no
$B_{4}$-branches, when a minimal-ABC tree is large enough.

After applying $\mathcal{T}_{7}$, the change of the ABC index is

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle=$
$\displaystyle-(2z-3)f(d(v),z+1)-(2z-3)z\,f(z+1,4)-f(d(v),5)-f(4,2)-f(2,1)$
(7) $\displaystyle+(2z-1)f(d(v)+1,z)+(2z-1)(z-1)f(z,4)$
$\displaystyle+n_{3}(-f(d(v),4)+f(d(v)+1,4))+(n_{4}-1)(-f(d(v),5)+f(d(v)+1,5))$
$\displaystyle+\sum_{i=1}^{d(v)-2z+3-n_{3}-n_{4}}(-f(d(v),d(v_{i}))+f(d(v)+1,d(v_{i}))),$

where $n_{3}$ is the number of $B_{3}$-branches attached to the root, $n_{4}$
is the number of $B_{4}$-branches (attached to the root), and $d(v_{i})$,
$i=1,\dots,d(v)-2z+3-n_{3}-n_{4}$, are the children of $v$, which are centers
of $D$-branches in $\overline{G}$ ($\overline{G^{\prime}}$). By Theorem 1.4,
$n_{4}$ can be at most $4$, and $n_{3}+n_{4}\leq 919$ by Lemma 3.1.

Verification shows that the right-hand side of (7) is negative. The detailed
deductions are presented in Appendix A.4. ∎

###  3.2 $B$-branches attached to the root

######  Lemma 3.3.

If the root vertex of a minimal-ABC tree has a degree of at least $2956$, then
there are no $B$-branches attached to the root.

###### Proof.

Assume that the claim of the lemma is not true and there are some $B$-branches
attached to the root. We apply the transformation $\mathcal{T}_{8}$ depicted
in Figure 11. Since $d(v)\geq 2956$, by Lemma 3.2 there are no
$B_{4}$-branches. Here similarly as in Lemma 3.2, due to Lemmas 2.1 and 2.2
(Tables 1 and 2) and the fact that $d(v)\geq 2956$, the only possible
combinations of $D$-branches are: $D_{50}$\- and $D_{51}$-branches; $D_{51}$\-
and $D_{52}$-branches; and $D_{52}$\- and $D_{53}$-branches, together with a
possible $D$-branch containing $B_{2}$\- or $B_{3}^{**}$-branch.

Figure 11: The transformation $\mathcal{T}_{8}$, which shows that there are no
$B$-branches attached to the root, when the minimal-ABC tree is sufficiently
large.

The change of the ABC index after applying $\mathcal{T}_{8}$ is

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle=$ $\displaystyle
x(-f(d(v),z+1)+f(d(v)-x,z+2))+xz(-f(z+1,4)+f(z+2,4))$ (8)
$\displaystyle+x(-f(d(v),4)+f(z+2,4))$
$\displaystyle+\sum_{i=1}^{d(v)-2x}(-f(d(v),d(v_{i}))+f(d(v)-x,d(v_{i}))),$

where $v_{i}$, $i=1,\dots,d(v)-2x$, are the children of $v$ in $\overline{G}$
($\overline{G^{\prime}}$). A straightforward verification shows that the
right-hand side of (8) is negative. The detailed deductions can refer to
Appendix A.5. ∎

##  4 On the size and existence of $D_{z,1}^{2}$-, $D_{z,2}^{2}$\- and
$D_{z}^{**}$-branches

###  4.1 $D_{z,1}^{2}$\- and $D_{z,2}^{2}$-branches

######  Proposition 4.1.

If a minimal-ABC tree contains a $D_{z,2}^{2}$-branch, then $25\leq z\leq 50$.
If a minimal-ABC tree contains a $D_{z,1}^{2}$-branch, then $19\leq z\leq 97$.

###### Proof.

The above upper and lower bounds on $z$ for a $D_{z,2}^{2}$-branch were
presented in [23, Lemma 14], and the lower bound on $z$ for a
$D_{z,1}^{2}$-branch was given in [23, Lemma 15]. Here, we need only to show
that if a minimal-ABC tree contains a $D_{z,1}^{2}$-branch, then $z\leq 97$.

Assume that there is a $D_{z,1}^{2}$-branch in a minimal-ABC tree, with $z\geq
98$. Recall that $z\leq 131$ from Lemma 1.10. Also, assume that $z$ is odd
(the case with even $z$ can be proved analogously). Now, apply the
transformation $\mathcal{T}_{9}$ depicted in Figure 12.

Figure 12: The transformation applied to obtain an upper bound on the size of
a $D_{z,1}^{2}$-branch.

After applying $\mathcal{T}_{9}$, the change of the ABC index is

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle=$
$\displaystyle\sum_{xv\in
E(\bar{G})}(-f(d(v),d(x))+f(d(v)+3,d(x)))-f(d(v),z+1)$ (9)
$\displaystyle+2f\left(d(v)+3,\frac{z-1}{2}\right)-f(z+1,3)+2f(d(v)+3,5)$
$\displaystyle-(z-1)f(z+1,4)+(z-3)f\left(\frac{z-1}{2},4\right).$

We can show that the right-hand side of (9) is always negative when $99\leq
z\geq 131$ (note that $z$ is odd here), in which the details are given in
Appendix A.6. ∎

Next, we consider the difference between $D$-branches. The following
proposition is a modification of Proposition 1.12 and includes only the fact
that the vertex $y$ may have a $B_{2}$-branch as a child.

######  Proposition 4.2.

Let $x$ and $y$ be vertices of a minimal-ABC tree $G$ that have a common
parent vertex $z$, such that $d(x)\geq d(y)\geq 7$. If $x$ has only
$B_{3}$-branches as children and $y$ has $B_{3}$-branches and $one$
$B_{2}$-branch as children, then $d(x)\leq d(y)+5$. If $y$ has
$B_{3}$-branches and $two$ $B_{2}$-branches as children, then $d(x)\leq
d(y)+9$.

###### Proof.

First, assume that $y$ has one $B_{2}$-branch as a child. We estimate the
differences between $d(x)$ and $d(y)$ by applying transformation
$\mathcal{T}_{10}$ illustrated in Figure 13.

Figure 13: Suggested transformation, which shows that the differences between
the sizes of $D$-branches are small.

After applying $\mathcal{T}_{10}$, the degree of the vertex $x$ decreases by
$1$, while the degree of $y$ increases by $1$. The rest of the vertices do not
change their degrees. The change of the ABC index is then

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle=$
$\displaystyle-f(d(z),d(x))+f(d(z),d(x)-1)-f(d(z),d(y))+f(d(z),d(y)+1)$ (10)
$\displaystyle+(d(x)-2)(-f(d(x),4)+f(d(x)-1,4))-f(d(x),4)+f(d(y)+1,4)$
$\displaystyle+(d(y)-2)(-f(d(y),4)+f(d(y)+1,4))-f(d(y),3)+f(d(y)+1,3).$

By Proposition 1.1, the expression $-f(d(z),d(x))+f(d(z),d(x)-1)$ increases in
$d(z)$, i.e.,

$\displaystyle-f(d(z),d(x))+f(d(z),d(x)-1)$ $\displaystyle\leq$
$\displaystyle\lim_{d(z)\rightarrow+\infty}(-f(d(z),d(x))+f(d(z),d(x)-1))$
$\displaystyle=$
$\displaystyle-\sqrt{\frac{1}{d(x)}}+\sqrt{\frac{1}{d(x)-1}},$

while by Proposition 1.2, $-f(d(z),d(y))+f(d(z),d(y)+1)$ decreases in $d(z)$.
Thus,

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle\leq$
$\displaystyle-\sqrt{\frac{1}{d(x)}}+\sqrt{\frac{1}{d(x)-1}}-f(d(z),d(y))+f(d(z),d(y)+1)$
(11) $\displaystyle+(d(x)-2)(-f(d(x),4)+f(d(x)-1,4))-f(d(x),4)+f(d(y)+1,4)$
$\displaystyle+(d(y)-2)(-f(d(y),4)+f(d(y)+1,4))-f(d(y),3)+f(d(y)+1,3),$

and it decreases in $d(z)$.

By Lemmas 1.7 and 1.8, we have that $16\leq d(x)\leq 132$, and by Proposition
4.1 that $20\leq d(y)\leq 98$. When $d(z)\geq 10000$ and $d(x)\geq d(y)+6$, it
can be verified that the right-hand side of (11) is negative, for any $16\leq
d(x)\leq 132$ and $20\leq d(y)\leq 98$ (observe that since the right-hand side
of (11) decreases in $d(z)$, it suffices to verify the negativity of (11) when
$d(z)=10000$). As to $d(x)\leq d(z)<10000$ and $d(x)\geq d(y)+6$, it can be
verified that the right-hand side of (10) is always negative, from direct
calculations, for any combination of $16\leq d(x)\leq 132$ and $20\leq
d(y)\leq 98$.

The case when there are two $B_{2}$-branches attached to $y$ can be
analogously considered as the case with one $B_{2}$-branch attached to $y$,
and therefore, to avoid the repetitions of same arguments, we omit the proof
in this case. ∎

######  Lemma 4.3.

A minimal-ABC tree with at least $65$ $D_{z}$-branches and with the root of
degree at least $146$ does not contain a $D_{k,2}^{2}$-branch.

###### Proof.

Assume that there are at least $65$ $D_{z}$-branches, the degree of the root
vertex is at least $146$, and the minimal-ABC tree does contain a
$D_{k,2}^{2}$-branch. By Lemmas 2.1 and 2.2 (Tables 1 and 2), we may assume
that $43\leq z\leq 56$, and by Proposition 4.1 that $25\leq k\leq 50$. It
holds also that $k\leq z$, and by Proposition 4.2, $z\leq k+9$. So we further
assume that $34\leq k\leq 50$. Here we apply the transformation
$\mathcal{T}_{11}$ depicted in Figure 14.

Figure 14: The transformation which shows that under certain conditions there
is no $D_{k,2}^{2}$-branch.

The change of the ABC index after applying $\mathcal{T}_{11}$ is

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle=$
$\displaystyle\sum_{yv\in
E(\bar{G})}(-f(d(v),d(y))+f(d(v)+2,d(y)))-x\,f(d(v),z+1)-x\,z\,f(z+1,4)$ (12)
$\displaystyle-f(d(v),k+1)-(k-2)f(k+1,4)-2f(k+1,3)+(x+2)f(d(v)+2,z)$
$\displaystyle+(x+2)(z-1)f(z,4)+f(d(v)+2,5).$

The number of $B_{3}$-branches in $G$ (outside $\bar{G}$) is equal to the
number of $B_{3}$-branches in $G^{\prime}$ (outside $\overline{G^{\prime}}$).
Thus, it follows that $xz+k-2=(x+2)(z-1)$, or equivalently, $x=2z-k$. It can
be verified that for each $z\in[43,56]$ with constraints
$k\in[z-9,\min\\{z,50\\}]$ and $x=2z-k$ , the change of the ABC index (the
right-hand side of (12)) is always negative. The technical details are
presented in Appendix A.7. Notice that with the above given possible values of
$z$ and $k$, $x$ is at most $65$, which guarantees that the transformation
$\mathcal{T}_{11}$ is feasible. ∎

######  Lemma 4.4.

A minimal-ABC tree with at least $261$ $D_{z}$-branches and with the root of
degree at least $1228$ does not contain a $D_{k,1}^{2}$-branch.

###### Proof.

Assume that there are at least $261$ $D_{z}$-branches, the root vertex has a
degree of at least $1228$, and the minimal-ABC tree does contain a
$D_{k,1}^{2}$-branch. By Proposition 4.1, it holds that $19\leq k\leq 97$.
Since there are (at least) $261$ $D_{z}$-branches and the root of degree at
least $1228$, by Lemmas 2.1 and 2.2 (Tables 1 and 2), it follows that
$z\in\\{50,51,52\\}$. By Proposition 4.2, $z\leq k+5$. Also it holds that
$k\leq z$.

Assume that $z=50$. Clearly, it remains to argue that the claim is true for
$1228\leq d(v)<1358$. Otherwise, $n_{50}\leq 182$ from Table 2, which is a
contradiction to the hypothesis that $n_{50}\geq 261$. Recall that in the
proof of Appendix A.4, we have shown that $n_{50}\geq 222$ is impossible when
$1228\leq d(v)<1358$ by using (39) (here the only difference is $n_{4}=0$
instead of $n_{4}=1$ in Appendix A.4, but it does not affect the negativity of
the change of ABC index). It implies that $n_{50}<222$, which is a
contradiction to the hypothesis that $n_{50}\geq 261$.

For $z\in\\{51,52\\}$, we apply the transformation $\mathcal{T}_{12}$ depicted
in Figure 15.

Figure 15: The transformation which shows that under certain conditions there
is no $D_{k,1}^{2}$-branch.

The change of the ABC index after applying $\mathcal{T}_{12}$ is

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle=$
$\displaystyle\sum_{yv\in
E(\bar{G})}(-f(d(v),d(y))+f(d(v)+5,d(y)))-x\,f(d(v),z+1)-x\,z\,f(z+1,4)$ (13)
$\displaystyle-f(d(v),k+1)-(k-1)f(k+1,4)-f(k+1,3)-2f(3,2)-2f(2,1)$
$\displaystyle+(x+6)f(d(v)+5,z)+(x+6)(z-1)f(z,4).$

The number of $B_{3}$-branches in $G$ is equal to the number of
$B_{3}$-branches in $G^{\prime}$ (the ones outside $\overline{G}$
($\overline{G^{\prime}}$)), i.e., $xz+k-1=(x+6)(z-1)$, or equivalently,
$x=6z-k-5$. From $z\in\\{51,52\\}$, $k\in[z-5,z]$ and $x=6z-k-5$, it follows
that $x\leq 260$ and thus, the transformation $\mathcal{T}_{12}$ is feasible.
A verification shows that the right-hand side of (13) is negative under the
given parameters. The details are presented in Appendix A.8. ∎

######  Remark 4.1.

The above upper bound $261$ of $D_{z}$-branches can be improved by involving
particular structural properties of $D_{k,1}^{2}$-branches, but the current
upper bound suffices for the proofs of the main and computational results in
Section 5.

###  4.2 $D_{z}^{**}$-branch

######  Proposition 4.5.

If a minimal-ABC tree contains a $D_{z}^{**}$-branch, then $47\leq z\leq 74$.

###### Proof.

Assume that there is a $D_{z}^{**}$-branch in a minimal-ABC tree, with $z\geq
75$. Recall that $z\leq 131$ from Lemma 1.9. Assume, also that $z$ is odd (the
case when $z$ is even can be handled analogously). Then apply the
transformation $\mathcal{T}_{13}$ depicted in Figure 16.

Figure 16: The transformation applied to obtain an upper bound on the size of
a $D_{z}^{**}$-branch.

After applying $\mathcal{T}_{13}$, the change of the ABC index is

$\displaystyle ABC(G^{\prime})-ABC(G)$ (14) $\displaystyle=$
$\displaystyle\sum_{xv\in
E(\bar{G})}(-f(d(v),d(x))+f(d(v)+2,d(x)))-f(d(v),z+1)+2f\left(d(v)+2,\frac{z+1}{2}\right)$
$\displaystyle-z\,f(z+1,4)+(z-1)f\left(\frac{z+1}{2},4\right)-f(4,3)+f(v+2,5).$

In Appendix A.9, we show that the right-hand side of (14) is negative for
$75\leq z\leq 131$.

For the lower bound on the size $z$ of a $D_{z}^{**}$-branch, consider the
transformation $\mathcal{T}_{14}$ depicted in Figure 17.

Figure 17: The transformation applied to obtain a lower bound on the size of a
$D_{z}^{**}$-branch.

The change of the ABC index after applying $\mathcal{T}_{14}$ is

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle=$
$\displaystyle-f(d(v),z+1)+f(d(v),z+2)+(z-1)(-f(z+1,4)+f(z+2,4))$
$\displaystyle-f(z+1,4)-f(4,3)+2f(z+2,3).$

By Proposition 1.2, $-f(d(v),z+1)+f(d(v),z+2)$ decreases in $d(v)\geq z+1$.
Thus we have the following upper bound on $ABC(G^{\prime})-ABC(G)$:

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle\leq$
$\displaystyle-f(z+1,z+1)+f(z+1,z+2)+(z-1)(-f(z+1,4)+f(z+2,4))$
$\displaystyle-f(z+1,4)-f(4,3)+2f(z+2,3),$

which is negative for $15\leq z\leq 46$. ∎

######  Lemma 4.6.

If there are at least $56$ $D_{z}$-branches, then the minimal-ABC tree does
not contain a $D_{k}^{**}$-branch.

###### Proof.

Assume that there are at least $56$ $D_{z}$-branches and the minimal-ABC tree
does contain a $D_{k}^{**}$-branch. By Lemma 4.5, it holds that $47\leq k\leq
74$. Since there are at least $56$ $D_{z}$-branches, by Lemma 2.1 (see the
results in Table 1) and Lemma 2.2 (see Table 2), it follows that $38\leq z\leq
57$. By Proposition 1.12, $k=z-1,$ $z$ or $z+1$. Thus, we may assume that
$47\leq k\leq 58$ and $46\leq z\leq 57$.

Next, we apply the transformation $\mathcal{T}_{15}$ depicted in Figure 18.

Figure 18: The transformation which shows that under certain conditions there
is no $D_{z}^{**}$-branch.

The change of the ABC index after applying $\mathcal{T}_{15}$ is

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle=$
$\displaystyle\sum_{yv\in
E(\bar{G})}(-f(d(v),d(y))+f(d(v)+2,d(y)))-x\,f(d(v),z+1)-x\,z\,f(z+1,4)$ (15)
$\displaystyle-f(d(v),k+1)-k\,f(k+1,4)-f(4,3)+(x+1)f(d(v)+2,z)$
$\displaystyle+(x+1)(z-1)f(z,4)+f(d(v)+2,k)+(k-1)f(k,4)+f(d(v)+2,5).$

The number of $B_{3}$-branches in $G$ (outside $\bar{G}$) is equal to the
number of $B_{3}$-branches in $G^{\prime}$ (outside $\overline{G^{\prime}}$),
i.e., $x\,z+k-1=(x+1)(z-1)+k-1$, that is, $x=z-1$. From $z\in[46,57]$,
$k\in[\max\\{47,z-1\\},z+1]$ and $x=z-1$, it follows that $x\leq 56$, and
therefore, the transformation $\mathcal{T}_{15}$ is feasible. For these values
of $z$, $k$, and $x$, it can be shown that the right-hand side of (15) is
negative. The details are presented in Appendix A.10. ∎

##  5 Main results

By Proposition 1.12 and Lemmas 3.2, 4.3, 4.4 and 4.6 we obtain the following
result, which is an affirmative answer to Conjecture 1.2.

######  Theorem 5.1.

A minimal-ABC tree with the root vertex of degree at least $1228$ is comprised
only of a root and $D_{z}$\- and $D_{z+1}$-branches, where
$z\in\\{50,51,52\\}$ and maybe of $B_{3}$-branches and at most one of
$D_{t,1}^{2}$-branch, $z-5\leq t\leq z$, attached to the root.

###### Proof.

In general, if the degree of the root vertex is at least $1228$, besides the
$B$-branches, there are at least $1228-919=309$ $D$-branches (since there are
at most $919$ $B$-branches attached to the root vertex from Lemma 3.1), and
thus, by Lemmas 4.3 and 4.6, it follows that there is no $D_{z,2}^{2}$-branch
and no $D_{z}^{**}$-branch. In addition, by Lemma 3.2, when $d(v)\geq 1228$
there are no $B_{4}$-branches. Observe that a branch with one $B_{2}$-branch,
say $D_{t,1}^{2}$-branch for some $t$ ($z-5\leq t\leq z$ from Proposition
4.2), may exist, there is at most one of such branch with $B_{2}$-branch.

As in the proof of Lemma 3.2, we have shown that when the root vertex has
degree at least $1228$, the cases when a minimal-ABC tree contains a
combination of $D_{z}$\- and $D_{z+1}$-branches (maybe with a possible
$D_{t,1}^{2}$-branch), for $15\leq z\leq 48$ and $54\leq z\leq 131$, are not
possible. So we are remaining to eliminate the two cases: the combination of
$D_{49}$\- and $D_{50}$-branches, and the combination of $D_{53}$\- and
$D_{54}$-branches.

The same as in Appendix A.4, with the help of (39), the case that $G$ contains
a combination of $D_{49}$\- and $D_{50}$-branches (whether the
$D_{t,1}^{2}$-branch exists or not) is also impossible (here $n_{4}=0$ and the
worst case is when $n_{3}$ is also equal to $0$).

Now, consider the last remaining case when $G$ contains a combination
$D_{53}$\- and $D_{54}$-branches, maybe with a possible $D_{t,1}^{2}$-branch.
Here, the minimal-ABC tree may contain at most $882$ $B_{3}$-branches (see
Tables 3 and 5), since no $B_{4}$-branch occurs when $d(v)\geq 1228$ from
Lemma 3.2.

Case 1: There is no $D_{t,1}^{2}$-branch for any $t$.

There can be in addition $260$ $D_{53}$-branches and $130$ $D_{54}$-branches
(see Table 1). Since there are at most $882$ $B_{3}$-branches, the number of
$D_{53}$\- and $D_{54}$-branches must be at least $1228-882=346$. Here, we can
apply the transformation $\mathcal{T}_{4}$ and obtain a new upper bound on the
change of the ABC index with $z=53$, which is an improvement of the upper
bound (19) presented in Appendix A.1:

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle\leq$
$\displaystyle-x\,f(d(v),z+1)-x\,z\,f(z+1,4)-3f(4,2)-3f(2,1)+n_{k}f(d(v)+7,k+1)$
$\displaystyle+n_{k-1}f(d(v)+7,k)+k\,n_{k}f(k+1,4)+(k-1)n_{k-1}f(k,4)$
$\displaystyle+n_{3}(-f(d(v),4)+f(d(v)+7,4))$
$\displaystyle+(d(v)-x-n_{3})(-f(d(v),z+1)+f(d(v)+7,z+1)).$

Clearly, the worst case is when $n_{3}$ as large as possible, i.e.,
$n_{3}=882$. Recall that $n_{53}+n_{54}\geq 346$ and $n_{54}\leq 130$, thus
$n_{53}\geq 346-130=216$. So by setting $z=53$, $x=216$, $k=52$ ($n_{52}=74$
and $n_{51}=149$), $n_{3}=882$, the right-hand side of last inequality above
is negative for $1228\leq d(v)\leq 882+260+130=1272$.

Case 2: There is $D_{t,1}^{2}$-branch for some $t$.

In this case, the upper bound on the change of ABC index after applying
transformation $\mathcal{T}_{4}$ with $z=53$ is:

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle\leq$
$\displaystyle-x\,f(d(v),z+1)-x\,z\,f(z+1,4)-3f(4,2)-3f(2,1)+n_{k}f(d(v)+7,k+1)$
$\displaystyle+n_{k-1}f(d(v)+7,k)+k\,n_{k}f(k+1,4)+(k-1)n_{k-1}f(k,4)$
$\displaystyle+n_{3}(-f(d(v),4)+f(d(v)+7,4))+(-f(d(v),t+1)+f(d(v)+7,t+1))$
$\displaystyle+(d(v)-x-n_{3}-1)(-f(d(v),z+1)+f(d(v)+7,z+1)).$

When $d(v)\geq 1229$, $n_{53}+n_{54}\geq 1229-882-1=346$ (we minus one here
because of the occurrence of $D_{t,1}^{2}$-branch), and thus $n_{53}\geq
346-130=216$. As above, by setting $z=53$, $x=216$, $k=52$ ($n_{52}=74$ and
$n_{51}=149$), $n_{3}=882$, $t=48$ (because $t\geq 53-5=48$ from Proposition
4.2), the right-hand side of last inequality above is negative for $1229\leq
d(v)\leq 882+260+130+1=1273$.

When $d(v)=1228$, $n_{53}+n_{54}\geq 345$. In order to get $n_{53}\geq 216$ as
the case $d(v)\geq 1229$, we resort to the right-hand side of (19), by setting
$d(v)=1228$, $z=54$, $x=130$, $k=52$ ($n_{51}=105$ and $n_{52}=32$), leading
to a negative value for the right-hand side of (19). It implies that
$n_{54}\leq 129$ when $d(v)=1228$, so $n_{53}\geq 345-129=216$ follows. The
remaining parts are the same as the case $d(v)\geq 1229$.

The proof is completed. ∎

If we want to eliminate the existence of $D_{t,1}^{2}$-branch in Theorem 5.1,
Lemma 4.4 could help us a lot, when the root vertex has a somewhat larger
degree than $1228$.

######  Corollary 5.2.

A minimal-ABC tree with the root vertex of degree at least $1441$ is comprised
only of a root and $D_{z}$\- and $D_{z+1}$-branches, where
$z\in\\{50,51,52\\}$ and maybe of $B_{3}$-branches attached to the root.

###### Proof.

From Lemma 4.4, we need at least $261$ $D_{z}$-branches to guarantee the
nonexistence of $D_{t,1}^{2}$-branch. When $d(v)\geq 1441$, besides the
$B$-branches and one possible $D$-branch with $B_{2}$-branch, there are at
least $1441-919-1=521$ $D$-branches (recall that there are at most $919$
$B$-branches attached to the root vertex from Lemma 3.1). Assume that such
$D$-branches are $D_{z}$ or $D_{z+1}$-branches. Clearly, one of $n_{z}$ or
$n_{z+1}$ is at least $\lceil\frac{521}{2}\rceil=261$. ∎

By Lemma 3.3, when the degree of the root is at least $2956$, then there are
also no $B_{3}$-branches attached to the root.

######  Corollary 5.3.

A minimal-ABC tree with the root vertex of degree at least $2956$ is comprised
only of a root and $D_{z}$\- and $D_{z+1}$-branches, where
$z\in\\{50,51,52\\}$.

This confirmed the conjectured structure of the minimal-ABC tree from [1]
depicted in Figure 3. More details about the structure of minimal-ABC trees,
when the degree of the root is at least $2956$, are presented in the following
theorem.

######  Theorem 5.4.

Let $v$ be the root of a minimal-ABC tree $G$.

  * •

If $2956\leq d(v)\leq 3241$, then $G$ must contain $D_{51}$-branches and in
addition

    * –

either $D_{52}$-branches,

    * –

or at most $123$ $D_{50}$-branches.

In particular, when $2956\leq d(v)\leq 3185$, $G$ contains at most $357$
$D_{52}$-branches.

  * •

If $d(v)\geq 3242$, then $G$ must contain $D_{52}$-branches and

    * –

either at most $718$ $D_{51}$-branches.

    * –

or at most $178$ $D_{53}$-branches.

In particular, when $d(v)\geq 3249$, $G$ contains at most $364$
$D_{51}$-branches.

###### Proof.

We partition our proof into two parts with respect to $d(v)$, namely the cases
when $2956\leq d(v)\leq 3241$ and $d(v)\geq 3242$.

Case 1: $2956\leq d(v)\leq 3241$.

We claim that $G$ must contain $D_{51}$-branches in this case. Otherwise, from
Corollary 5.3, $G$ contains a combination of $D_{52}$\- and $D_{53}$-branches,
or $G$ contains only $D_{50}$-branches. The latter is clearly impossible,
recall from Table 2, $n_{50}\leq 182$, and thus $d(v)=n_{50}\leq 182$ (since
there is no $B$-branch attached to $v$ from Lemma 3.3).

Assume that $G$ contains a combination of $D_{52}$\- and $D_{53}$-branches. By
virtue of the transformation $\mathcal{T}_{4}$ depicted in Figure 7, we can
show that $n_{52}\leq 357$. Observe that now there is no $B$-branch attached
to the root, instead of the term $(d(v)-x)(-f(d(v),4)+f(d(v)+7,4))$ in (19),
we have the term $(d(v)-x)(-f(d(v),z+1)+f(d(v)+7,z+1))$ with $z=52$. We can
rewrite (19) as:

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle\leq$ $\displaystyle-
xf(d(v),z+1)-x\,z\,f(z+1,4)-3f(4,2)-3f(2,1)$ (16)
$\displaystyle+n_{k}f(d(v)+7,k+1)+n_{k-1}f(d(v)+7,k)+kn_{k}f(k+1,4)$
$\displaystyle+(k-1)n_{k-1}f(k,4)+(d(v)-x)(-f(d(v),z+1)+f(d(v)+7,z+1)).\quad$

A straightforward verification shows that for $z=52$, $x=358$, $k=52$ (thus
$n_{51}=365$ and $n_{52}=0$), the expression (16) is negative for $2956\leq
d(v)\leq 3241$. Together with $n_{53}\leq 260$ from Table 1, we obtain
$d(v)=n_{52}+n_{53}\leq 357+260=617<2956$, a contradiction.

Besides the $D_{51}$-branches, $G$ can only contain $D_{50}$\- or
$D_{52}$-branches. Moreover, $n_{50}\leq 123$ by using the transformation
$\mathcal{T}_{5}$, more precisely, the right-hand side of (22) is negative
when $2956\leq d(v)\leq 3241$, $z=50$, $x=124$, $k=53$ ($n_{53}=117$ and
$n_{52}=0$). And $n_{52}\leq 357$ when $2956\leq d(v)\leq 3185$ from the
transformation $\mathcal{T}_{4}$ again, here the difference from (16) is that
we need to replace the term $(d(v)-x)(-f(d(v),z+1)+f(d(v)+7,z+1))$ by
$(d(v)-x)(-f(d(v),z)+f(d(v)+7,z))$ with $z=52$, i.e.,

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle\leq$
$\displaystyle-x\,f(d(v),z+1)-x\,z\,f(z+1,4)-3f(4,2)-3f(2,1)$ (17)
$\displaystyle+n_{k}f(d(v)+7,k+1)+n_{k-1}f(d(v)+7,k)+kn_{k}f(k+1,4)$
$\displaystyle+(k-1)n_{k-1}f(k,4)+(d(v)-x)(-f(d(v),z)+f(d(v)+7,z)).$

By the same setting that $z=52$, $x=358$, $k=52$ (thus $n_{51}=365$ and
$n_{52}=0$) as above, the right-hand side of (17) is negative for $2956\leq
d(v)\leq 3185$.

Case 2: $d(v)\geq 3242$.

From Corollary 5.3, the possible $D$-branches occurring in $G$ are $D_{50}$-,
$D_{51}$-, $D_{52}$-, $D_{53}$-branches. From Tables 1 and 2, $n_{50}\leq
182$, $n_{53}\leq 260$. By using the transformation $\mathcal{T}_{5}$, we have
$n_{51}\leq 718$, which is obtained from the fact that the right-hand side of
(22) is negative when $d(v)\geq 3242$, $z=51$, $x=719$, $k=52$ ($n_{52}=358$
and $n_{51}=354$). It is worth mentioning that the upper bound of $n_{51}$ can
be improved into $n_{51}\leq 364$ when $d(v)\geq 3249$, from Table 2. These
upper bounds imply that $d(v)<2956$ unless $D_{52}$-branches occur.

In addition to $D_{52}$-branches, $G$ can contain either $D_{51}$\- or
$D_{53}$-branches. We have known that $n_{51}\leq 718$. As to $n_{53}$, Table
1 reflects that $n_{53}\leq 260$, actually when we involve in the hypothesis
that $d(v)\geq 3242$, the upper bound would be improved into $n_{53}\leq 178$
by using the transformation $\mathcal{T}_{4}$, that is to say, the right-hand
side of (17) is negative when $d(v)\geq 3242$, $z=53$, $x=179$, $k=52$
($n_{52}=0$ and $n_{51}=186$). The detailed deduction about the negativity of
right-hand side of (17) when $z=53$ is similar to that in Appendix A.1. In a
rough aspect, the right-hand side of (20) in Appendix A.1 is negative when
$d(v)=700000$, so is $d(v)\geq 700000$ (since it decreases in $d(v)$), and for
$3242\leq d(v)<700000$, the right-hand side of (17) is negative from direct
calculations. ∎

###  5.1 The optimization function and
determining the parameters of the minimal-ABC trees

The obtained theoretical results have significantly reduced the search space.
By applying them the parameters that fully characterize the minimal-ABC trees
can be efficiently computed. Denote by $\mathcal{T}$ all trees of a given
order $n$ that are comprised of: a combination of $D_{z}$\- and
$D_{z+1}$-branches, $15\leq z\leq 131$; at most one $D_{z}^{**}$-,
$D_{k,1}^{2}$\- or $D_{k,2}^{2}$-branch; at most $4$ $B_{4}$-branches and at
most $919$ $B$-branches attached to the root vertex. 222Notice that we may
assume that the $D^{**}$-branch is of size $z$. Otherwise, we can apply the
switching transformation, switching one $B_{3}$-branch from a $D_{z}$-branch
(if it exist) with the $B_{3}^{**}$-branch. If the minimal ABC tree does not
contain $D_{z}$-branches, but only $D_{z+1}$-branches, then this case is
considered when we increase $z$ by one.

A minimal-ABC tree of order at least $1000$ is one of the trees from
$\mathcal{T}$ (the minimal-ABC trees of orders at most $1100$ were reported in
[42]). Let $T\in\mathcal{T}$. Then

$\displaystyle
ABC(T)=n_{z}f(d(v),z+1)+n_{z+1}f(d(v),z+2)+n_{z}zf(z+1,4)+n_{z+1}(z+1)f(z+2,4)$
$\displaystyle+6n_{z}z\frac{\sqrt{2}}{2}+6n_{z+1}(z+1)\frac{\sqrt{2}}{2}+b_{3}\left(n_{3}f(d(v),4)+6n_{3}\frac{\sqrt{2}}{2}\right)+b_{4}\left(n_{4}f(d(v),5)+8n_{4}\frac{\sqrt{2}}{2}\right)$
$\displaystyle+b_{1}\left(f(d(v),k_{1}+1)+(k_{1}-1)f(k_{1}+1,4)+f(k_{1}+1,3)+6(k_{1}-1)\frac{\sqrt{2}}{2}+4\frac{\sqrt{2}}{2}\right)$
$\displaystyle+b_{2}\left(f(d(v),k_{2}+1)+(k_{2}-2)f(k_{2}+1,4)+2f(k_{2}+1,3)+6(k_{2}-2)\frac{\sqrt{2}}{2}+2\cdot
4\cdot\frac{\sqrt{2}}{2}\right)$
$\displaystyle+b_{*}\left(f(d(v),z+1)+zf(z+1,4)+(6z+2)\frac{\sqrt{2}}{2}+f(4,3)\right),$

where $n_{z}$ and $n_{z+1}$ are, respectively, the numbers of $D_{z}$\- and
$D_{z+1}$-branches, $n_{3}$ and $n_{4}$ are, respectively, the numbers of
$B_{3}$\- and $B_{4}$-branches attached to the root, $k_{1}$ is the size of
the $D_{k,1}^{2}$-branch ($(k-1)$ $B_{3}$-branches and one $B_{2}$-branch,
which comprise a $D_{k,1}^{2}$-branch), $k_{2}$ is the size of the
$D_{k,2}^{2}$-branch ($(k-2)$ $B_{3}$-branches and two $B_{2}$-branches, which
comprise a $D_{k,2}^{2}$-branch), and parameters
$b_{*},b_{1},b_{2},b_{3},b_{4}\in\\{0,1\\}$ are related to the existences of
$D_{z}^{**}$-, $D_{k,1}^{2}$-, $D_{k,2}^{2}$-, $B_{3}$\- and $B_{4}$-branches
attached to the root vertex, respectively - for example $b_{*}=0/1$ means that
$T$ does not contain/ does contain $D_{z}^{**}$-branch.

The parameters of a minimal-ABC tree of order $n$ can be determined by solving
the following optimization problem:

$\displaystyle min_{T\in\mathcal{T}}ABC(T)$

subject to

  * (1)

$d(v)=n_{z}+n_{z+1}+b_{*}+b_{1}+b_{2}+b_{3}\cdot n_{3}+b_{4}\cdot n_{4}$

  * (2)

$n=1+n_{z}(7z+1)+n_{z+1}(7(z+1)+1)+b_{1}(7(k_{1}-1)+5+1)+b_{2}(7(k_{2}-2)+10+1)+b_{3}\cdot
n_{3}\cdot 7+b_{4}\cdot n_{4}\cdot 9+b_{*}\cdot(7z+4)$

  * (3)

$15\leq z\leq 131$ (by Lemmas 1.7 and 1.8)

  * (4)

$z-5\leq k_{1}\leq z$ (by Proposition 4.2)

  * (5)

$z-9\leq k_{2}\leq z$ (by Proposition 4.2)

  * (6)

$0\leq n_{4}\leq 4$ (by Theorem 1.4)

  * (7)

$0\leq n_{3}+n_{4}\leq 919$ (by Lemma 3.1)

  * (8)

$b_{*},b_{1},b_{2},b_{3},b_{4}\in\\{0,1\\}$

  * (9)

at most one of $b_{*},b_{1},b_{2},b_{4}$ can be $1$ (by Theorems 1.5 and 1.6).

With the growth of the order of the trees, the above optimization problem
becomes simpler.

When $d(v)\geq 1228$, by Theorem 5.1, it follows that $n_{4}=0$,
$b_{*}=b_{1}=b_{2}=b_{4}=0$, and $50\leq z\leq 52$. Further, when $d(v)\geq
2956$, by Corollary 5.3, it follows that $n_{3}=n_{4}=0$,
$b_{*}=b_{1}=b_{2}=b_{3}=b_{4}=0$ and $50\leq z\leq 52$. Moreover, by Theorem
5.4, when $d(v)\geq 3249$, we have $0\leq n_{51}\leq 364$ and $0\leq
n_{53}\leq 178$. That allows us to compute the parameters of the minimal-ABC
tree for an arbitrary $n$ in constant time.

We have implemented the solution to the above optimization problem in C++. The
minimal-ABC trees and their structures are given in Appendix A.12. The
minimal-ABC trees of orders up to $1100$ were already known [42].

The computational results lead to the following observations. All bounds are
sharp and are attained by some minimal-ABC tree.

######  Observation 5.1.

A minimal-ABC tree of order larger than $1072$ can contain at most two
$B_{4}$-branches.

######  Observation 5.2.

A minimal-ABC tree of order larger than $8507$ can contain at most one
$B_{4}$-branch.

######  Observation 5.3.

A minimal-ABC tree of order larger than $19040$ does not contain
$B_{4}$-branches. A minimal-ABC tree whose root vertex is of degree at least
$368$ does not contain $B_{4}$-branches attached to the root vertex.

######  Observation 5.4.

A minimal-ABC tree of order larger than $1017676$ does not contain
$B_{3}$-branches attached to the root vertex. A minimal-ABC tree whose root
vertex is of degree at least $2838$ does not contain $B_{3}$-branches attached
to the root vertex.

######  Observation 5.5.

A minimal-ABC tree may have at most $738$ $B_{3}$-branches attached to the
root vertex.

######  Observation 5.6.

A minimal-ABC tree of order larger than $999$ does not contain a
$B_{3}^{**}$-branch, and thus any such minimal-ABC tree cannot have a
$D_{k}^{**}$-branch.

######  Observation 5.7.

A minimal-ABC tree of order larger than $305$ does not contain more than one
$B_{2}$-branch, and thus any such minimal-ABC tree cannot have a
$D_{k,2}^{2}$-branch.

######  Observation 5.8.

A minimal-ABC tree of order larger than $6739$ does not contain a
$B_{2}$-branch, and therefore, it does not contain a $D_{k,1}^{2}$-branch.

######  Observation 5.9.

A minimal-ABC tree of order larger than $1142737$ does not contain a
$D_{50}$-branch. A minimal-ABC tree whose root vertex is of degree larger than
$3192$ does not contain $D_{50}$-branches.

For most of the above observations, we have related theoretical results. Some
of them are close to the optimal ones obtained by the computations. Anyway,
the theoretically proven bounds reduce enough the search space such that we
can compute the minimal-ABC trees up to some given order, forced by the
limitations of the numerical representations of the numbers (we can obtain
numerically consistent results for trees of orders up to $13290000000000000$).
However, formal proofs of some of the above observations, without the use of a
computer, could be done in the future, although that will not add any new
value regarding the understanding of the structure of the minimal-ABC trees.

Acknowledgements. This work was partially supported by the Slovenian research
agency ARRS (Program No. P1-0383), the bilateral cooperation between China and
Slovenia (Project No. Bi-CN-18-20-015), and the National Natural Science
Foundation of China (Grant No. 11701505).

## References

  * [1] M. B. Ahmadi, D. Dimitrov, I. Gutman, and S. A. Hosseini, Disproving a conjecture on trees with minimal atom-bond connectivity index, MATCH Commun. Math. Comput. Chem., 72 (2014), pp. 685–698.
  * [2] J. Chen and X. Guo, Extreme atom-bond connectivity index of graphs, MATCH Commun. Math. Comput. Chem., 65 (2011), pp. 713–722.
  * [3] J. Chen and X. Guo, The atom-bond connectivity index of chemical bicyclic graphs, Appl. Math. J. Chinese Univ., 27 (2012), pp. 243–252.
  * [4] J. Chen, J. Liu, and X. Guo, Some upper bounds for the atom-bond connectivity index of graphs, Appl. Math. Lett., 25 (2012), pp. 1077–1081.
  * [5] J. Chen, J. Liu, and Q. Li, Some upper bounds for the atom-bond connectivity index of graphs, Discrete Dyn. Nat. Soc., 25 (2013).
  * [6] R. Cruz and J. Rada, The path and the star as extremal values of vertex-degree-based topological indices among trees, MATCH Commun. Math. Comput. Chem., 82 (2019), pp. 715–732.
  * [7] K. C. Das, I. Gutman, and B. Furtula, On atom-bond connectivity index, Chem. Phys. Lett., 511 (2011), pp. 452–454.
  * [8] K. C. Das, M. A. Mohammed, I. Gutman, and K. A. Atan, Comparison between atom-bond connectivity indices of graphs, MATCH Commun. Math. Comput. Chem., 76 (2016), pp. 159–170.
  * [9] K. C. Das and N. Trinajstić, Comparison between first geometric-arithmetic index and atom-bond connectivity index, Chem. Phys. Lett., 497 (2010), pp. 149–151.
  * [10] D. Dimitrov, On structural properties of trees with minimal atom-bond connectivity index, Discrete Appl. Math., 172 (2014), pp. 28–44.
  * [11] D. Dimitrov, On structural properties of trees with minimal atom-bond connectivity index II: Bounds on $B_{1}$\- and $B_{2}$-branches, Discrete Appl. Math., 204 (2016), pp. 90–116.
  * [12] D. Dimitrov, Extremal trees with respect to the atom-bond connectivity index, in Bounds in Chemical Graph Theory - Mainstreams, Mathematical Chemistry Monographs, I. Gutman, B. Furtula, K. C. Das, and I. M. E. Milovanović, eds., vol. 20, University of Kragujevac and Faculty of Science Kragujevac, 2017, pp. 53–67.
  * [13] D. Dimitrov, On structural properties of trees with minimal atom-bond connectivity index IV: Solving a conjecture about the pendent paths of length three, Appl. Math. Comput., 313 (2017), pp. 418–430.
  * [14] D. Dimitrov and Z. Du, A solution of the conjecture about big vertices of minimal-ABC trees, Appl. Math. Comput., 397 (2021).
  * [15] D. Dimitrov, Z. Du, and C. M. da Fonseca, On structural properties of trees with minimal atom-bond connectivity index III: Trees with pendent paths of length three, Appl. Math. Comput., 282 (2016), pp. 276–290.
  * [16] D. Dimitrov, Z. Du, and C. M. da Fonseca, The minimal-ABC trees with $B_{1}$-branches, PLoS ONE, 13 (2018).
  * [17] D. Dimitrov, Z. Du, and C. M. da Fonseca, Some forbidden combinations of branches in minimal-ABC trees, Discrete Appl. Math., 236 (2018), pp. 165–182.
  * [18] D. Dimitrov, B. Ikica, and R. Škrekovski, Remarks on maximum atom-bond connectivity index with given graph parameters, Discrete Appl. Math., 222 (2017), pp. 222–226.
  * [19] D. Dimitrov and N. Milosavljević, Efficient computation of trees with minimal atom-bond connectivity index revisited, MATCH Commun. Math. Comput. Chem., 79 (2018), pp. 431–450.
  * [20] Z. Du, On the atom-bond connectivity index and radius of connected graphs, J. Inequal. Appl., (2015).
  * [21] Z. Du and C. M. da Fonseca, On a family of trees with minimal atom-bond connectivity index, Discrete Appl. Math., 202 (2016), pp. 37–49.
  * [22] Z. Du and D. Dimitrov, The minimal-ABC trees with $B_{1}$-branches II, IEEE Access, 6 (2018), pp. 66350–66366.
  * [23] Z. Du and D. Dimitrov, The minimal-ABC trees with $B_{2}$-branches, Comput. Appl. Math., 39 Art Nr. 85 (2020).
  * [24] E. Estrada, The ABC matrix, J. Math. Chem., 55 (2017), pp. 1021–1033.
  * [25] E. Estrada, Atom-bond connectivity and the energetic of branched alkanes, Chem. Phys. Lett., 463 (2008), pp. 422–425.
  * [26] E. Estrada, L. Torres, L. Rodríguez, and I. Gutman, An atom-bond connectivity index: Modelling the enthalpy of formation of alkanes, Indian J. Chem., 37 (1998), pp. 849–855.
  * [27] G. H. Fath-Tabar, B. Vaez-Zadeh, A. R. Ashrafi, and A. Graovac, Some inequalities for the atom-bond connectivity index of graph operations, Discrete Appl. Math., 159 (2011), pp. 1323–1330.
  * [28] B. Furtula, A. Graovac, and D. Vukičević, Atom-bond connectivity index of trees, Discrete Appl. Math., 157 (2009), pp. 2828–2835.
  * [29] B. Furtula, I. Gutman, M. Ivanović, and D. Vukičević, Computer search for trees with minimal ABC index, Appl. Math. Comput., 219 (2012), pp. 767–772.
  * [30] L. Gan, H. Hou, and B. Liu, Some results on atom-bond connectivity index of graphs, MATCH Commun. Math. Comput. Chem., 66 (2011), pp. 669–680.
  * [31] L. Gan, B. Liu, and Z. You, The ABC index of trees with given degree sequence, MATCH Commun. Math. Comput. Chem., 68 (2012), pp. 137–145.
  * [32] Y. Gao and Y. Shao, The smallest ABC index of trees with n pendent vertices, MATCH Commun. Math. Comput. Chem., 76 (2016), pp. 141–158.
  * [33] A. Graovac and M. Ghorbani, A new version of the atom-bond connectivity index, Acta Chim. Slov., 57 (2010), pp. 609–612.
  * [34] I. Gutman and B. Furtula, Trees with smallest atom-bond connectivity index, MATCH Commun. Math. Comput. Chem., 68 (2012), pp. 131–136.
  * [35] I. Gutman, B. Furtula, M. B. Ahmadi, S. A. Hosseini, P. S. Nowbandegani, and M. Zarrinderakht, The ABC index conundrum, Filomat, 27 (2013), pp. 1075–1083.
  * [36] I. Gutman, J. Tošović, S. Radenković, and S. Marković, On atom-bond connectivity index and its chemical applicability, Indian J. Chem., 51 (2012), pp. 690–694.
  * [37] S. A. Hosseini, B. Mohar, and M. B. Ahmadi, The evolution of the structure of ABC-minimal trees, to appear in J. Comb. Theory Ser. B.  https://doi.org/10.1016/j.jctb.2021.07.001.
  * [38] H. Hua, K. C. Das, and H. Wang, On atom–bond connectivity index of graphs, J. Math. Anal. Appl., 479 (2019), pp. 1099–1114.
  * [39] X. Ke, Atom-bond connectivity index of benzenoid systems and fluoranthene congeners, Polycycl. Aromat. Comp., 32 (2012), pp. 27–35.
  * [40] D. L. Kreher and D. R. Stinson, Combinatorial Algorithms: Generation, Enumeration, and Search, CRC Press, Boca Raton, 1998.
  * [41] W. Lin, J. Chen, C. Ma, Y. Zhang, J. Chen, D. Zhang, and F. Jia, On trees with minimal ABC index among trees with given number of leaves, MATCH Commun. Math. Comput. Chem., 76 (2016), pp. 131–140.
  * [42] W. Lin, J. Chen, Z. Wu, D. Dimitrov, and L. Huang, Computer search for large trees with minimal ABC index, Appl. Math. Comput., 338 (2018), pp. 221–230.
  * [43] W. Lin, T. Gao, Q. Chen, and X. Lin, On the minimal ABC index of connected graphs with given degree sequence, MATCH Commun. Math. Comput. Chem., 69 (2013), pp. 571–578.
  * [44] J. Rada and S. Bermudo, Is every graph the extremal value of a vertex-degree-based topological index?, MATCH Commun. Math. Comput. Chem., 81 (2019), pp. 315–323.
  * [45] R. Xing, B. Zhou, and F. Dong, On atom-bond connectivity index of connected graphs, Discrete Appl. Math., 159 (2011), pp. 1617–1630.
  * [46] R. Xing, B. Zhou, and Z. Du, Further results on atom-bond connectivity index of trees, Discrete Appl. Math., 158 (2011), pp. 1536–1545.
  * [47] J. Yang, F. Xia, and H. Cheng, The atom-bond connectivity index of benzenoid systems and phenylenes, Int. Math. Forum, 6 (2011), pp. 2001–2005.
  * [48] R. Zheng, J. Liu, J. Chen, and B. Liu, Bounds on the general atom-bond connectivity indices, MATCH Commun. Math. Comput. Chem., 83 (2020), pp. 143–166.
  * [49] L. Zhong and Q. Cui, On a relation between the atom-bond connectivity and the first geometric-arithmetic indices, Discrete Appl. Math., 185 (2015), pp. 249–253.

##  Appendix A Appendix

###  A.1 The size of $D_{z}$-branches–the negativity of right-hand side of (2)

The relations presented in (3) can be regarded as a system of two equations
with unknowns $n_{k}$ and $n_{k-1}$ when parameters $z$, $x$, $k$ are given.
The solution is

$\displaystyle n_{k}=x(z-k+1)-7k+6\quad\text{and}\quad n_{k-1}=x(k-z)+7k+1,$
(18)

which means that $n_{k}$ and $n_{k-1}$ are determined by the parameters $z$,
$x$, $k$. It can be shown that the right-hand side of (2) is negative for the
following values of the above parameters:

Table 1: Some values of the parameters for which the right-hand side of (2) is negative. $z$ | $x$ |  | $z$ | $x$ |
---|---|---|---|---|---
$53$ | $261$ | ($k=52$, $n_{51}=104$, $n_{52}=164$) | $54$ | $131$ | ($k=52$, $n_{51}=103$, $n_{52}=35$)
$55$ | $90$ | ($k=52$, $n_{51}=95$, $n_{52}=2$) | $56$ | $72$ | ($k=52$, $n_{51}=77$, $n_{52}=2$)
$57$ | $60$ | ($k=52$, $n_{51}=65$, $n_{52}=2$) | $58$ | $52$ | ($k=52$, $n_{51}=53$, $n_{52}=6$)
$59$ | $45$ | ($k=52$, $n_{51}=50$, $n_{52}=2$) | $60$ | $40$ | ($k=52$, $n_{51}=45$, $n_{52}=2$)
$61$ | $36$ | ($k=52$, $n_{51}=41$, $n_{52}=2$) | $62$ | $33$ | ($k=52$, $n_{51}=35$, $n_{52}=5$)
$63$ | $30$ | ($k=52$, $n_{51}=35$, $n_{52}=2$) | $64$ | $28$ | ($k=52$, $n_{51}=29$, $n_{52}=6$)
$65$ | $26$ | ($k=52$, $n_{51}=27$, $n_{52}=6$) | $66$ | $25$ | ($k=52$, $n_{51}=15$, $n_{52}=17$)
$67$ | $23$ | ($k=52$, $n_{51}=20$, $n_{52}=10$) | $68$ | $22$ | ($k=52$, $n_{51}=13$, $n_{52}=16$)
$69$ | $21$ | ($k=52$, $n_{51}=8$, $n_{52}=20$) | $70$ | $21$ | ($k=53$, $n_{52}=15$, $n_{53}=13$)
$71$ | $20$ | ($k=53$, $n_{52}=12$, $n_{53}=15$) | $72$ | $19$ | ($k=53$, $n_{52}=11$, $n_{53}=15$)
$73$ | $19$ | ($k=54$, $n_{53}=18$, $n_{54}=8$) | $74$ | $18$ | ($k=54$, $n_{53}=19$, $n_{54}=6$)
$75$ | $17$ | ($k=54$, $n_{53}=22$, $n_{54}=2$) | $76$ | $17$ | ($k=54$, $n_{53}=5$, $n_{54}=19$)
$77$ | $17$ | ($k=55$, $n_{54}=12$, $n_{55}=12$) | $78$ | $16$ | ($k=55$, $n_{54}=18$, $n_{55}=5$)
$79$ | $16$ | ($k=55$, $n_{54}=2$, $n_{55}=21$) | $80$ | $16$ | ($k=56$, $n_{55}=9$, $n_{56}=14$)
$81$ | $15$ | ($k=56$, $n_{55}=18$, $n_{56}=4$) | $82$ | $15$ | ($k=56$, $n_{55}=3$, $n_{56}=19$)
$83$ | $15$ | ($k=57$, $n_{56}=10$, $n_{57}=12$) | $84$ | $15$ | ($k=58$, $n_{57}=17$, $n_{58}=5$)
$85$ | $15$ | ($k=58$, $n_{57}=2$, $n_{58}=20$) | $86$ | $14$ | ($k=58$, $n_{57}=15$, $n_{58}=6$)
$87$ | $14$ | ($k=58$, $n_{57}=1$, $n_{58}=20$) | $88$ | $13$ | ($k=58$, $n_{57}=17$, $n_{58}=3$)
$89$ | $13$ | ($k=58$, $n_{57}=4$, $n_{58}=16$) | $90$ | $13$ | ($k=59$, $n_{58}=11$, $n_{59}=9$)
$91$ | $13$ | ($k=60$, $n_{59}=18$, $n_{60}=2$) | $92$ | $13$ | ($k=60$, $n_{59}=5$, $n_{60}=15$)
$93$ | $13$ | ($k=61$, $n_{60}=12$, $n_{61}=8$) | $94$ | $13$ | ($k=62$, $n_{61}=19$, $n_{62}=1$)
$95$ | $13$ | ($k=62$, $n_{61}=6$, $n_{62}=14$) | $96$ | $13$ | ($k=63$, $n_{62}=13$, $n_{63}=7$)
$97$ | $13$ | ($k=63$, $n_{62}=0$, $n_{63}=20$) | $98$ | $13$ | ($k=64$, $n_{63}=7$, $n_{64}=13$)
$99$ | $13$ | ($k=65$, $n_{64}=14$, $n_{65}=6$) | $100$ | $13$ | ($k=65$, $n_{64}=1$, $n_{65}=19$)
$101$ | $13$ | ($k=66$, $n_{65}=8$, $n_{66}=12$) | $102$ | $13$ | ($k=67$, $n_{66}=15$, $n_{67}=5$)
$103$ | $13$ | ($k=67$, $n_{66}=2$, $n_{67}=18$) | $104$ | $13$ | ($k=68$, $n_{67}=9$, $n_{68}=11$)
$105$ | $13$ | ($k=69$, $n_{68}=16$, $n_{69}=4$) | $106$ | $13$ | ($k=69$, $n_{68}=3$, $n_{69}=17$)
$107$ | $13$ | ($k=70$, $n_{69}=10$, $n_{70}=10$) | $108$ | $13$ | ($k=71$, $n_{70}=17$, $n_{71}=3$)
$109$ | $13$ | ($k=71$, $n_{70}=4$, $n_{71}=16$) | $110$ | $13$ | ($k=72$, $n_{71}=11$, $n_{72}=9$)
$111$ | $13$ | ($k=73$, $n_{72}=18$, $n_{73}=2$) | $112$ | $13$ | ($k=73$, $n_{72}=5$, $n_{73}=15$)
$113$ | $13$ | ($k=74$, $n_{73}=12$, $n_{74}=8$) | $114$ | $13$ | ($k=75$, $n_{74}=19$, $n_{75}=1$)
$115$ | $13$ | ($k=75$, $n_{74}=6$, $n_{75}=14$) | $116$ | $13$ | ($k=76$, $n_{75}=13$, $n_{76}=7$)
$117$ | $13$ | ($k=76$, $n_{75}=0$, $n_{76}=20$) | $118$ | $13$ | ($k=77$, $n_{76}=7$, $n_{77}=13$)
$119$ | $13$ | ($k=78$, $n_{77}=14$, $n_{78}=6$) | $120$ | $13$ | ($k=78$, $n_{77}=1$, $n_{78}=19$)
$121$ | $13$ | ($k=79$, $n_{78}=8$, $n_{79}=12$) | $122$ | $13$ | ($k=80$, $n_{79}=15$, $n_{80}=5$)
$123$ | $13$ | ($k=80$, $n_{79}=2$, $n_{80}=18$) | $124$ | $13$ | ($k=81$, $n_{80}=9$, $n_{81}=11$)
$125$ | $13$ | ($k=82$, $n_{81}=16$, $n_{82}=4$) | $126$ | $13$ | ($k=82$, $n_{81}=3$, $n_{82}=17$)
$127$ | $13$ | ($k=83$, $n_{82}=10$, $n_{83}=10$) | $128$ | $13$ | ($k=84$, $n_{83}=17$, $n_{84}=3$)
$129$ | $13$ | ($k=84$, $n_{83}=4$, $n_{84}=16$) | $130$ | $13$ | ($k=85$, $n_{84}=11$, $n_{85}=9$)
$131$ | $13$ | ($k=86$, $n_{85}=18$, $n_{86}=2$) |  |  |

By Proposition 1.1, $-f(d(v),d(v_{i}))+f(d(v)+7,d(v_{i}))$ decreases in
$d(v_{i})$. Thus, the right-hand side of (2) has its maximum value when
$d(v_{i})=4$, $i=1,\dots d(v)-x$, i.e.,

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle\leq$
$\displaystyle-x\,f(d(v),z+1)-x\,z\,f(z+1,4)-3f(4,2)-3f(2,1)+n_{k}f(d(v)+7,k+1)$
(19) $\displaystyle+n_{k-1}f(d(v)+7,k)+kn_{k}f(k+1,4)+(k-1)n_{k-1}f(k,4)$
$\displaystyle+(d(v)-x)(-f(d(v),4)+f(d(v)+7,4)).$

Next, we show that there exists an upper bound on (19) decreasing in $d(v)$.
Observe that the terms related to $d(v)$ in the right-hand side of (19) are

$\displaystyle-x\,f(d(v),z+1)+n_{k}f(d(v)+7,k+1)+n_{k-1}f(d(v)+7,k)+(d(v)-x)(-f(d(v),4)+f(d(v)+7,4))$
$\displaystyle=$
$\displaystyle(d(v)-x+7)f(d(v)+7,4)-(d(v)-x)f(d(v),4)+n_{k}(-f(d(v)+7,k)+f(d(v)+7,k+1))$
$\displaystyle+(x+7)(-f(d(v)+7,4)+f(d(v)+7,k))+x(-f(d(v),z+1)+f(d(v)+7,4)).$

It is not hard to verify that $(d(v)-x+7)f(d(v)+7,4)-(d(v)-x)f(d(v),4)$
decreases in $d(v)\geq x>0$, by verifying the negativity of its derivative.
From Propositions 1.1 and 1.2, we have

  * •

$-f(d(v)+7,k)+f(d(v)+7,k+1)$ decreases in $d(v)$;

  * •

$-f(d(v)+7,4)+f(d(v)+7,k)$ decreases in $d(v)$;

  * •

$-f(d(v),z+1)+f(d(v)+7,4)$ increases in $d(v)$, i.e.,

$\displaystyle-f(d(v),z+1)+f(d(v)+7,4)$ $\displaystyle\leq$
$\displaystyle\lim_{d(v)\rightarrow+\infty}(-f(d(v),z+1)+f(d(v)+7,4))$
$\displaystyle=$ $\displaystyle-\sqrt{\frac{1}{z+1}}+\sqrt{\frac{1}{4}}.$

Thus, the right-hand side of (19) has another (weaker) upper bound:

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle\leq$
$\displaystyle(d(v)-x+7)f(d(v)+7,4)-(d(v)-x)f(d(v),4)+n_{k}(-f(d(v)+7,k)$ (20)
$\displaystyle+f(d(v)+7,k+1))+(x+7)(-f(d(v)+7,4)+f(d(v)+7,k))$
$\displaystyle+x\left(-\sqrt{\frac{1}{z+1}}+\sqrt{\frac{1}{4}}\right)-x\,z\,f(z+1,4)-3f(4,2)-3f(2,1)$
$\displaystyle+kn_{k}f(k+1,4)+(k-1)n_{k-1}f(k,4),$

which decreases in $d(v)$.

Let us consider the case $z=53$ and $x=261$ as a representative (since it is
the worst case with the largest valid $x$) to illustrate how to show that the
right-hand side of (2) is negative. With the assumption that $z=53$ and
$x=261$, we set $k=52$, which implies that $n_{51}=104$ and $n_{52}=164$ from
(18). Now, let us substitute $z=53$, $x=261$, $k=52$, $n_{51}=104$,
$n_{52}=164$ into (20), we can see that the right-hand side of (20) is
negative when $d(v)=259226$, and so is it for $d(v)\geq 259226$. As to
$x=261\leq d(v)<259226$, we resort to the right-hand side of (19), which is
always negative by direct calculations. Thus, we have verified that a minimal-
ABC tree cannot contain (at least) $x=261$ $D_{z}$-branches with $z=53$.

Similarly, it can be verified that for the rest of the combinations of the
listed parameters in Table 1, the change of the ABC index is negative.

###  A.2 The size of $D_{z}$-branches–the negativity of right-hand side of (4)

The relations from (5) can be reformulated as

$\displaystyle n_{k}=x(z-k+1)+7k-6\quad\text{and}\quad n_{k-1}=x(k-z)-7k-1,$
(21)

which means that $n_{k}$ and $n_{k-1}$ are determined by the parameters $x$,
$z$, and $k$. It can be easily verified that for the following values of the
above parameters (including a lower bound of $d(v)$), the right-hand side of
(4) is negative:

Table 2:  Some values of the parameters for which the right-hand side of (4) is negative. $z$ | $x$ | $d(v)$ | $z$ | $x$ | $d(v)$
---|---|---|---|---|---
$51$ | $365$ | $\geq 3249$ | $50$ | $183$ | $\geq 1358$
($k=52$, $n_{51}=0$, $n_{52}=358$) | ($k=52$, $n_{51}=0$, $n_{52}=358$)
$49$ | $122$ | $\geq 825$ | $48$ | $92$ | $\geq 572$
($k=52$, $n_{51}=1$, $n_{52}=114$) | ($k=52$, $n_{51}=3$, $n_{52}=82$)
$47$ | $73$ | $\geq 430$ | $46$ | $61$ | $\geq 333$
($k=52$, $n_{51}=0$, $n_{52}=66$) | ($k=52$, $n_{51}=1$, $n_{52}=53$)
$45$ | $53$ | $\geq 263$ | $44$ | $46$ | $\geq 215$
($k=52$, $n_{51}=6$, $n_{52}=40$) | ($k=52$, $n_{51}=3$, $n_{52}=36$)
$43$ | $41$ | $\geq 177$ | $42$ | $37$ | $\geq 146$
($k=52$, $n_{51}=4$, $n_{52}=30$) | ($k=52$, $n_{51}=5$, $n_{52}=25$)
$41$ | $34$ | $\geq 120$ | $40$ | $31$ | $\geq 100$
($k=52$, $n_{51}=9$, $n_{52}=18$) | ($k=52$, $n_{51}=7$, $n_{52}=17$)
$39$ | $29$ | $\geq 80$ | $38$ | $27$ | $\geq 64$
($k=52$, $n_{51}=12$, $n_{52}=10$) | ($k=52$, $n_{51}=13$, $n_{52}=7$)
$37$ | $25$ | $\geq 47$ | $36$ | $23$ | $\geq z$
($k=52$, $n_{51}=10$, $n_{52}=8$) | ($k=52$, $n_{51}=3$, $n_{52}=13$)
$35$ | $22$ | $\geq z$ | $34$ | $21$ | $\geq z$
($k=52$, $n_{51}=9$, $n_{52}=6$) | ($k=52$, $n_{51}=13$, $n_{52}=1$)
$33$ | $20$ | $\geq z$ | $32$ | $19$ | $\geq z$
($k=51$, $n_{50}=2$, $n_{51}=11$) | ($k=51$, $n_{50}=3$, $n_{51}=9$)
$31$ | $18$ | $\geq z$ | $30$ | $18$ | $\geq z$
($k=51$, $n_{50}=2$, $n_{51}=9$) | ($k=50$, $n_{49}=9$, $n_{50}=2$)
$29$ | $17$ | $\geq z$ | $28$ | $16$ | $\geq z$
($k=50$, $n_{49}=6$, $n_{50}=4$) | ($k=50$, $n_{49}=1$, $n_{50}=8$)
$27$ | $16$ | $\geq z$ | $26$ | $15$ | $\geq z$
($k=49$, $n_{48}=8$, $n_{49}=1$) | ($k=49$, $n_{48}=1$, $n_{49}=7$)
$25$ | $15$ | $\geq z$ | $24$ | $15$ | $\geq z$
($k=48$, $n_{47}=8$, $n_{48}=0$) | ($k=46$, $n_{45}=7$, $n_{46}=1$)
$23$ | $15$ | $\geq z$ | $22$ | $15$ | $\geq z$
($k=44$, $n_{43}=6$, $n_{44}=2$) | ($k=42$, $n_{41}=5$, $n_{42}=3$)
$21$ | $15$ | $\geq z$ | $20$ | $15$ | $\geq z$
($k=40$, $n_{39}=4$, $n_{40}=4$) | ($k=38$, $n_{37}=3$, $n_{38}=5$)
$19$ | $15$ | $\geq z$ | $18$ | $15$ | $\geq z$
($k=36$, $n_{35}=2$, $n_{36}=6$) | ($k=34$, $n_{33}=1$, $n_{34}=7$)
$17$ | $15$ | $\geq z$ | $16$ | $15$ | $\geq z$
($k=32$, $n_{31}=0$, $n_{32}=8$) | ($k=31$, $n_{30}=7$, $n_{31}=1$)
$15$ | $14$ | $\geq z$ |  |  |
($k=31$, $n_{30}=6$, $n_{31}=1$) |

The above difference of $ABC(G^{\prime})-ABC(G)$, in the right-hand side of
(4), is bounded from above by

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle\leq$
$\displaystyle-x\,f(d(v),z+1)-x\,z\,f(z+1,4)+3f(4,2)+3f(2,1)$ (22)
$\displaystyle+n_{k}f(d(v)-7,k+1)+n_{k-1}f(d(v)-7,k)+kn_{k}f(k+1,4)$
$\displaystyle+(k-1)n_{k-1}f(k,4)+(d(v)-x)(-f(d(v),z+2)+f(d(v)-7,z+2)),\qquad\;$

by Proposition 1.2 and the fact that $d(v_{i})\leq z+2$ from Proposition 1.12,
$i=1,\dots,d(v)-x$. The terms related to $d(v)$ in the right-hand side of (22)
are

$\displaystyle-$ $\displaystyle
xf(d(v),z+1)+n_{k}f(d(v)-7,k+1)+n_{k-1}f(d(v)-7,k)+(d(v)-x)(-f(d(v),z+2)+f(d(v)-7,z+2)),$

which is equal to

$\displaystyle(d(v)-x-7)f(d(v)-7,z+2)-(d(v)-x)f(d(v),z+2)+n_{k}(-f(d(v)-7,k)+f(d(v)-7,k+1))$
$\displaystyle+x(-f(d(v),z+1)+f(d(v)-7,k))+7(-f(d(v)-7,k)+f(d(v)-7,z+2)).$

For each combination of $z$ and $x$ listed in Table 2, it is not hard to
verify that the first derivative of
$(d(v)-x-7)f(d(v)-7,z+2)-(d(v)-x)f(d(v),z+2)$ with respect to $d(v)$ is
positive, and thus this expression increases in $d(v)$, so

$\displaystyle(d(v)-x-7)f(d(v)-7,z+2)-(d(v)-x)f(d(v),z+2)$ $\displaystyle\leq$
$\displaystyle\lim_{d(v)\rightarrow+\infty}((d(v)-x-7)f(d(v)-7,z+2)-(d(v)-x)f(d(v),z+2))\quad=\quad-\frac{7}{\sqrt{z+2}}.$

By Propositions 1.1 and 1.2, we have

  * •

$-f(d(v)-7,k)+f(d(v)-7,k+1)$ decreases in $d(v)$;

  * •

$-f(d(v),z+1)+f(d(v)-7,k)$ decreases in $d(v)$, since $k\geq z+1$;

  * •

$-f(d(v)-7,k)+f(d(v)-7,z+2)$ decreases in $d(v)$ when $z+2>k$ (only when
$z=51$ and $k=52$), is equal to $0$ when $z+2=k$ (only when $z=50$ and
$k=52$), and increases in $d(v)$, so

$\displaystyle-f(d(v)-7,k)+f(d(v)-7,z+2)\;\;\leq\;\;\lim_{d(v)\rightarrow+\infty}(-f(d(v)-7,k)+f(d(v)-7,z+2))\;\;=\;\;-\sqrt{\frac{1}{k}}+\sqrt{\frac{1}{z+2}},\;\;$

when $z+2<k$ (i.e., $15\leq z\leq 49$).

Therefore, we get a weaker upper bound on $ABC(G^{\prime})-ABC(G)$ than the
right-hand side of (22):

  * •

when $z+2>k$ (more precisely, when $z=51$ and $k=52$),

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle\leq$
$\displaystyle-\frac{7}{\sqrt{z+2}}+n_{k}(-f(d(v)-7,k)+f(d(v)-7,k+1))$ (24)
$\displaystyle+x(-f(d(v),z+1)+f(d(v)-7,k))$
$\displaystyle+7\left(-f(d(v)-7,k)+f(d(v)-7,z+2)\right)-x\,z\,f(z+1,4)$
$\displaystyle+3f(4,2)+3f(2,1)+kn_{k}f(k+1,4)+(k-1)n_{k-1}f(k,4),$

and it decreases in $d(v)$.

  * •

When $z+2\leq k$ (i.e., $15\leq z\leq 50$),

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle\leq$
$\displaystyle-\frac{7}{\sqrt{z+2}}+n_{k}(-f(d(v)-7,k)+f(d(v)-7,k+1))$
$\displaystyle+x(-f(d(v),z+1)+f(d(v)-7,k))+7\left(-\sqrt{\frac{1}{k}}+\sqrt{\frac{1}{z+2}}\right)$
$\displaystyle-x\,z\,f(z+1,4)+3f(4,2)+3f(2,1)+kn_{k}f(k+1,4)$
$\displaystyle+(k-1)n_{k-1}f(k,4),$

and it decreases in $d(v)$, too.

We take the case $z=51$, $x=365$, and $d(v)\geq 3249$ as a representative to
illustrate how to show that the right-hand side of (4) is negative. Observe
that as previously we are considering the worst case with the largest valid
$x$. With the assumption that $z=51$, $x=365$, and $d(v)\geq 3249$, we set
$k=52$, which implies that $n_{51}=0$ and $n_{52}=358$ from (21). After
substituting $z=51$, $x=365$, $k=52$, $n_{51}=0$, $n_{52}=358$ into the right-
hand side of (24), we get that the right-hand side of (24) is negative when
$d(v)=3863$, and thus also for $d(v)\geq 3863$. When $3249\leq d(v)<3863$, we
resort to the right-hand side of (22), which is always negative by direct
calculations. Thus, we have verified that a minimal-ABC tree cannot contain
(at least) $x=365$ $D_{z}$-branches with $z=51$ when $d(v)\geq 3249$.

For the rest of the combinations of the listed parameters in Table 2, it can
be verified similarly that the change of the ABC index is negative.

###  A.3 The number of $B$-branches adjacent to the root–the negativity of
right-hand side of (6)

Since $d(v^{\prime})=d(v)-358$, by Proposition 1.2 it follows that
$-f(d(v),4)+f(d(v^{\prime}),4)<-f(d(v),5)+f(d(v^{\prime}),5)$. Thus, we may
assume that $n_{4}=4$ in right-hand side of (6), which is the worst case.

Assume that the maximal size of $D$-branches in $G$ is $k$, where $15\leq
k\leq 131$. Notice that the expression
$-f(d(v),d(v_{i}))+f(d(v^{\prime}),d(v_{i}))$ increases in $d(v_{i})$, in
which the maximal value for $d(v_{i})$ is $k+1$. Therefore,
$\sum_{i=1}^{d(v)-x}(-f(d(v),d(v_{i}))+f(d(v^{\prime}),d(v_{i})))$ is bounded
from above by $(d(v)-x)(-f(d(v),k+1)+f(d(v^{\prime}),k+1))$. So the right-hand
side of (6) has an upper bound:

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle\leq$
$\displaystyle(d(v)-x)(-f(d(v),k+1)+f(d(v^{\prime}),k+1))-f(d(v),4)+f(d(v^{\prime}),53)$
(25) $\displaystyle+6(-f(2,1)+f(d(v^{\prime}),53))+364(-f(d(v),4)+f(53,4))$
$\displaystyle+(x-369)(-f(d(v),4)+f(d(v^{\prime}),4))+4(-f(d(v),5)+f(d(v^{\prime}),5)).$

First, we claim that the right-hand side of (25) decreases in $x$. Because the
coefficients of $x$ in the right-hand side of (25) are

$(-f(d(v),4)+f(d(v^{\prime}),4))-(-f(d(v),k+1)+f(d(v^{\prime}),k+1)),$

which is negative from Proposition 1.2, it implies that the right-hand side of
(25) decreases in $x$.

Next, we get an upper bound on $ABC(G^{\prime})-ABC(G)$ which decreases in
$d(v)$. After rearranging the terms in the right-hand side of (25), we have

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle\leq$
$\displaystyle(d(v^{\prime})-x)f(d(v^{\prime}),k+1)-(d(v)-x)f(d(v),k+1)$
$\displaystyle+365(-f(d(v),4)+f(d(v^{\prime}),53))+358(-f(d(v^{\prime}),53)+f(d(v^{\prime}),k+1))$
$\displaystyle+(x-369)(-f(d(v),4)+f(d(v^{\prime}),4))+4(-f(d(v),5)+f(d(v^{\prime}),5))$
$\displaystyle-6f(2,1)+364f(53,4).$

It is not hard to check that
$(d(v^{\prime})-x)f(d(v^{\prime}),k+1)-(d(v)-x)f(d(v),k+1)$ increases in
$d(v)\geq x$, for $15\leq k\leq 131$ and $x\geq 400$, further

$\displaystyle(d(v^{\prime})-x)f(d(v^{\prime}),k+1)-(d(v)-x)f(d(v),k+1)$
$\displaystyle\leq$
$\displaystyle\lim_{d(v)\rightarrow+\infty}((d(v^{\prime})-x)f(d(v^{\prime}),k+1)-(d(v)-x)f(d(v),k+1))\quad=\quad-\frac{358}{\sqrt{k+1}}.$

And from Proposition 1.2, all the following terms decrease in $d(v)$:

  * •

$-f(d(v),4)+f(d(v^{\prime}),53)$,

  * •

$-f(d(v),4)+f(d(v^{\prime}),4)$,

  * •

$-f(d(v),5)+f(d(v^{\prime}),5)$.

Again by Propositions 1.1 and 1.2, the exclusive term
$-f(d(v^{\prime}),53)+f(d(v^{\prime}),k+1)$ decreases in $d(v)$ if $k>52$,
increases in $d(v)$ if $k<52$, and is equal to $0$ if $k=52$. Moreover, when
$k<52$,

$\displaystyle-f(d(v^{\prime}),53)+f(d(v^{\prime}),k+1)\quad\leq\quad\lim_{d(v)\rightarrow+\infty}(-f(d(v^{\prime}),53)+f(d(v^{\prime}),k+1))\quad=\quad-\frac{1}{\sqrt{53}}+\frac{1}{\sqrt{k+1}}.$

Thus, we obtain a weaker upper bound on $ABC(G^{\prime})-ABC(G)$: When $k\geq
52$,

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle\leq$
$\displaystyle-\frac{358}{\sqrt{k+1}}+365(-f(d(v),4)+f(d(v^{\prime}),53))$
(26)
$\displaystyle+358(-f(d(v^{\prime}),53)+f(d(v^{\prime}),k+1))+(x-369)(-f(d(v),4)+f(d(v^{\prime}),4))$
$\displaystyle+4(-f(d(v),5)+f(d(v^{\prime}),5))-6f(2,1)+364f(53,4),$

which decreases in $d(v)$, and when $k<52$,

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle\leq$
$\displaystyle-\frac{358}{\sqrt{k+1}}+365(-f(d(v),4)+f(d(v^{\prime}),53))+358\left(-\frac{1}{\sqrt{53}}+\frac{1}{\sqrt{k+1}}\right)$
(27)
$\displaystyle+(x-369)(-f(d(v),4)+f(d(v^{\prime}),4))+4(-f(d(v),5)+f(d(v^{\prime}),5))$
$\displaystyle-6f(2,1)+364f(53,4)$ $\displaystyle=$ $\displaystyle
365(-f(d(v),4)+f(d(v^{\prime}),53))-\frac{358}{\sqrt{53}}+(x-369)(-f(d(v),4)+f(d(v^{\prime}),4))$
$\displaystyle+4(-f(d(v),5)+f(d(v^{\prime}),5))-6f(2,1)+364f(53,4),$

which also decreases in $d(v)$.

Set $d(v)=5300$, $52\leq k\leq 131$ and $x=400$ in the right-hand side of
(26), and $d(v)=3400$, $15\leq k\leq 51$ and $x=400$ in the right-hand side of
(27), the corresponding upper bound on $ABC(G^{\prime})-ABC(G)$ is always
negative, so are when $d(v)\geq 5300$ and $d(v)\geq 3400$, respectively. It
also implies that the right-hand side of (25) is negative for:

  * •

$d(v)\geq 5300$, $52\leq k\leq 131$ and $x\geq 400$,

  * •

$d(v)\geq 3400$, $15\leq k\leq 51$ and $x\geq 400$.

When $k=52$, we assume that there are only $D$-branches of size $52$ (which is
the worst case). For $x\leq d(v)<5300$ and $x=917$, by direct calculations we
obtain that the right-hand side of (25) is negative.

Similarly as for $k=52$, in the cases $k=51,50$, we may assume that there are
only $D$-branches of size $51$ and $D$-branches of size $50$, respectively.
Then we obtain in those cases that the right-hand side of (25) is negative for
$x=909$ and $x=901$, respectively, and $x\leq d(v)<3400$.

As to the remaining cases with small $d(v)$, in order to get more precise
results, we partition our proofs into two parts: each $D$-branch is a
$D_{z}$-branch for some $z$; there exists some $D$-branch containing $B_{2}$-,
or $B_{3}^{**}$-branch.

Case 1: Each $D$-branch is a $D_{z}$-branch for some $z$.

In this case, besides $D_{k}$-branches, it can only contain
$D_{k-1}$-branches, by Proposition 1.12. From Lemmas 2.1 and 2.2 (Tables 1 and
2), we can find the upper bound on the number of $D_{k}$-branches, denoted
here by $n_{k}^{max}$ (e.g., $n_{53}^{max}=260$, the value of the
corresponding $x$ in Table 1 minus $1$). It is worth mentioning that
$n_{52}^{max}$ does not exist.

Let us introduce a refined version of (25), by noting that the number of
$D_{k}$-branches is bounded from above by $n_{k}^{max}$ (see Tables 1 and 2),
unless $k=52$. Thus, when $k\in\\{15,\dots,131\\}\setminus\\{52,53\\}$,

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle=$
$\displaystyle(d(v)-x-n_{k}-n_{k-1})(-f(d(v),4)+f(d(v^{\prime}),4))$ (28)
$\displaystyle+n_{k-1}(-f(d(v),k)+f(d(v^{\prime}),k))+n_{k}(-f(d(v),k+1)+f(d(v^{\prime}),k+1))$
$\displaystyle-f(d(v),4)+f(d(v^{\prime}),53)+6(-f(2,1)+f(d(v^{\prime}),53))$
$\displaystyle+364(-f(d(v),4)+f(53,4))+(x-369)(-f(d(v),4)+f(d(v^{\prime}),4))$
$\displaystyle+4(-f(d(v),5)+f(d(v^{\prime}),5))$ $\displaystyle=$
$\displaystyle(d(v)-n_{k}-n_{k-1})(-f(d(v),4)+f(d(v^{\prime}),4))$
$\displaystyle+n_{k-1}(-f(d(v),k)+f(d(v^{\prime}),k))+n_{k}(-f(d(v),k+1)+f(d(v^{\prime}),k+1))$
$\displaystyle-f(d(v),4)+f(d(v^{\prime}),53)+6(-f(2,1)+f(d(v^{\prime}),53))$
$\displaystyle+364(-f(d(v),4)+f(53,4))-369(-f(d(v),4)+f(d(v^{\prime}),4))$
$\displaystyle+4(-f(d(v),5)+f(d(v^{\prime}),5)),$

where $n_{i}$ is the number of $D_{i}$-branches, $0\leq n_{i}\leq
n_{i}^{max}$, $i\in\\{15,\dots,131\\}\setminus 52$. In particular, when
$k=53$,

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle\leq$
$\displaystyle(d(v)-x-n_{k})(-f(d(v),k)+f(d(v^{\prime}),k))$ (29)
$\displaystyle+n_{k}(-f(d(v),k+1)+f(d(v^{\prime}),k+1))-f(d(v),4)+f(d(v^{\prime}),53)$
$\displaystyle+6(-f(2,1)+f(d(v^{\prime}),53))+364(-f(d(v),4)+f(53,4))$
$\displaystyle+(x-369)(-f(d(v),4)+f(d(v^{\prime}),4))+4(-f(d(v),5)+f(d(v^{\prime}),5))$
$\displaystyle=$
$\displaystyle(d(v)-x-n_{53})(-f(d(v),53)+f(d(v^{\prime}),53))$
$\displaystyle+n_{53}(-f(d(v),54)+f(d(v^{\prime}),54))-f(d(v),4)+f(d(v^{\prime}),53)$
$\displaystyle+6(-f(2,1)+f(d(v^{\prime}),53))+364(-f(d(v),4)+f(53,4))$
$\displaystyle+(x-369)(-f(d(v),4)+f(d(v^{\prime}),4))+4(-f(d(v),5)+f(d(v^{\prime}),5)).\quad\quad\quad$

Let us consider the case when $k=53$, i.e., $G$ contains $D_{53}$-branches,
possibly together with $D_{52}$-branches. With the constraints $x+n_{53}\leq
d(v)<5300$ and $0\leq n_{53}\leq n_{53}^{max}=260$ (Table 1), set $x=920$, it
can be verified by direct calculations that the right-hand side of (29) is
negative. And with $x=919$, it is possible that the change is positive. It
means that the smallest value of $x$ for which we obtain the negative value of
(29) is $920$.

Now, it remains to show that we obtain a negative change of the ABC index for
$920\leq x+n_{k}+n_{k-1}\leq d(v)<5300$ when $54\leq k\leq 131$, and for
$920\leq x+n_{k}+n_{k-1}\leq d(v)<3400$ when $15\leq k\leq 49$. Here we always
use the right-hand side of (28).

When $k=54$, i.e., $G$ may contain $D_{54}$-branches and $D_{53}$-branches.
For $0\leq n_{54}\leq 130$, $0\leq n_{53}\leq 260$ (Table 1), and $x=883$,
$x+n_{54}+n_{53}\leq d(v)<5300$, it can be verified by direct calculations
that the right-hand side of (28) is negative. Similarly, as in the case
$k=54$, we can argue for the case $55\leq k\leq 131$. The corresponding values
of the maximum numbers of $B$-branches attached to the root are given in Table
3.

Table 3:  The possible combinations of $D_{k}$\- and $D_{k-1}$-branches, $53\leq k\leq 131$, and the corresponding upper bounds on the numbers of $B$-branches are presented. By obtaining the above results, the occurrence of $D_{k}$-branches is necessary, while the $D_{k-1}$-branches may or may not occur in a minimal-ABC tree. combination | upper | combination | upper | combination | upper
---|---|---|---|---|---
| bound |  | bound |  | bound
$D_{52}$ and $D_{53}$ | $919$ |  $D_{53}$ and $D_{54}$ | $882$ |  $D_{54}$ and $D_{55}$ | $798$
$D_{55}$ and $D_{56}$ | $749$ |  $D_{56}$ and $D_{57}$ | $717$ |  $D_{57}$ and $D_{58}$ | $693$
$D_{58}$ and $D_{59}$ | $672$ |  $D_{59}$ and $D_{60}$ | $654$ |  $D_{60}$ and $D_{61}$ | $639$
$D_{61}$ and $D_{62}$ | $627$ |  $D_{62}$ and $D_{63}$ | $615$ |  $D_{63}$ and $D_{64}$ | $605$
$D_{64}$ and $D_{65}$ | $597$ |  $D_{65}$ and $D_{66}$ | $591$ |  $D_{66}$ and $D_{67}$ | $584$
$D_{67}$ and $D_{68}$ | $577$ |  $D_{68}$ and $D_{69}$ | $573$ |  $D_{69}$ and $D_{70}$ | $571$
$D_{70}$ and $D_{71}$ | $569$ |  $D_{71}$ and $D_{72}$ | $564$ |  $D_{72}$ and $D_{73}$ | $562$
$D_{73}$-and $D_{74}$ | $560$ |  $D_{74}$ and $D_{75}$ | $554$ |  $D_{75}$ and $D_{76}$ | $552$
$D_{76}$ and $D_{77}$ | $553$ |  $D_{77}$ and $D_{78}$ | $550$ |  $D_{78}$ and $D_{79}$ | $547$
$D_{79}$ and $D_{80}$ | $548$ |  $D_{80}$ and $D_{81}$ | $545$ |  $D_{81}$ and $D_{82}$ | $542$
$D_{82}$ and $D_{83}$ | $543$ |  $D_{83}$ and $D_{84}$ | $544$ |  $D_{84}$ and $D_{85}$ | $545$
$D_{85}$\- and $D_{86}$ | $541$ |  $D_{86}$ and $D_{87}$ | $538$ |  $D_{87}$ and $D_{88}$ | $535$
$D_{88}$ and $D_{89}$ | $531$ |  $D_{89}$ and $D_{90}$ | $532$ |  $D_{90}$ and $D_{91}$ | $533$
$D_{91}$ and $D_{92}$ | $533$ |  $D_{92}$ and $D_{93}$ | $534$ |  $D_{93}$ and $D_{94}$ | $535$
$D_{94}$ and $D_{95}$ | $535$ |  $D_{95}$ and $D_{96}$ | $536$ |  $D_{96}$ and $D_{97}$ | $536$
$D_{97}$ and $D_{98}$ | $537$ |  $D_{98}$ and $D_{99}$ | $538$ |  $D_{99}$ and $D_{100}$ | $538$
$D_{100}$ and $D_{101}$ | $539$ |  $D_{101}$ and $D_{102}$ | $539$ |  $D_{102}$ and $D_{103}$ | $540$
$D_{103}$ and $D_{104}$ | $540$ |  $D_{104}$ and $D_{105}$ | $541$ |  $D_{105}$ and $D_{106}$ | $541$
$D_{106}$ and $D_{107}$ | $542$ |  $D_{107}$ and $D_{108}$ | $543$ |  $D_{108}$ and $D_{109}$ | $543$
$D_{109}$ and $D_{110}$ | $544$ |  $D_{110}$ and $D_{111}$ | $544$ |  $D_{111}$ and $D_{112}$ | $545$
$D_{112}$ and $D_{113}$ | $545$ |  $D_{113}$ and $D_{114}$ | $546$ |  $D_{114}$ and $D_{115}$ | $546$
$D_{115}$ and $D_{116}$ | $547$ |  $D_{116}$ and $D_{117}$ | $547$ |  $D_{117}$ and $D_{118}$ | $548$
$D_{118}$ and $D_{119}$ | $548$ |  $D_{119}$ and $D_{120}$ | $549$ |  $D_{120}$ and $D_{121}$ | $549$
$D_{121}$ and $D_{122}$ | $550$ |  $D_{122}$ and $D_{123}$ | $550$ |  $D_{123}$ and $D_{124}$ | $551$
$D_{124}$ and $D_{125}$ | $551$ |  $D_{125}$ and $D_{126}$ | $552$ |  $D_{126}$ and $D_{127}$ | $552$
$D_{127}$ and $D_{128}$ | $553$ |  $D_{128}$ and $D_{129}$ | $553$ |  $D_{129}$ and $D_{130}$ | $553$
$D_{130}$ and $D_{131}$ | $554$ |  |  |  |

For the cases $15\leq k\leq 49$, we proceed as in the cases $k=49$ and $k=48$,
which we elaborate next. When $k=49$, recall that $0\leq n_{49}\leq
n_{49}^{max}=121$ when $d(v)\geq 825$, $0\leq n_{48}\leq n_{48}^{max}=91$ when
$d(v)\geq 572$ (Table 2), the right-hand side of (28) is negative from direct
calculations, for $x+n_{49}+n_{48}\leq d(v)<3400$ and $x=825$. When $k=48$,
with the following constraints: $0\leq n_{48}\leq n_{48}^{max}=91$ when
$d(v)\geq 572$, $0\leq n_{47}\leq n_{47}^{max}=72$ when $d(v)\geq 430$ (Table
2), and $x=724$, $x+n_{48}+n_{47}\leq d(v)<3400$, it can be verified by direct
calculations that the right-hand side of (28) is negative. The corresponding
values of the maximum numbers of $B$-branches attached to the root, when
$15\leq k\leq 52$, are given in Table 4.

Table 4:  The possible combinations of $D_{k}$\- and $D_{k-1}$-branches, $15\leq k\leq 52$, and the corresponding upper bounds on the numbers of $B$-branches are presented. By obtaining the above results, the occurrence of $D_{k}$-branches is necessary, while the $D_{k-1}$-branches may or may not occur in a minimal-ABC tree.  combination | upper | combination | upper | combination | upper
---|---|---|---|---|---
| bound |  | bound |  | bound
$D_{51}$ and $D_{52}$ | $916$ |  $D_{50}$ and $D_{51}$ | $908$ |  $D_{49}$ and $D_{50}$ | $900$
$D_{48}$ and $D_{49}$ | $824$ |  $D_{47}$ and $D_{48}$ | $723$ |  $D_{46}$ and $D_{47}$ | $688$
$D_{45}$ and $D_{46}$ | $661$ |  $D_{44}$ and $D_{45}$ | $638$ |  $D_{43}$ and $D_{44}$ | $618$
$D_{42}$ and $D_{43}$ | $601$ |  $D_{41}$ and $D_{42}$ | $587$ |  $D_{40}$ and $D_{41}$ | $574$
$D_{39}$ and $D_{40}$ | $563$ |  $D_{38}$ and $D_{39}$ | $553$ |  $D_{37}$ and $D_{38}$ | $543$
$D_{36}$ and $D_{37}$ | $533$ |  $D_{35}$ and $D_{36}$ | $525$ |  $D_{34}$ and $D_{35}$ | $519$
$D_{33}$ and $D_{34}$ | $513$ |  $D_{32}$ and $D_{33}$ | $507$ |  $D_{31}$ and $D_{32}$ | $500$
$D_{30}$ and $D_{31}$ | $496$ |  $D_{29}$ and $D_{30}$ | $492$ |  $D_{28}$ and $D_{29}$ | $486$
$D_{27}$ and $D_{28}$ | $482$ |  $D_{26}$ and $D_{27}$ | $478$ |  $D_{25}$ and $D_{26}$ | $474$
$D_{24}$ and $D_{25}$ | $472$ |  $D_{23}$ and $D_{24}$ | $469$ |  $D_{22}$ and $D_{23}$ | $467$
$D_{21}$ and $D_{22}$ | $465$ |  $D_{20}$ and $D_{21}$ | $462$ |  $D_{19}$ and $D_{20}$ | $460$
$D_{18}$ and $D_{19}$ | $457$ |  $D_{17}$ and $D_{18}$ | $454$ |  $D_{16}$ and $D_{17}$ | $451$
$D_{15}$ and $D_{16}$ | $449$ | $D_{15}$ | $426$ |  |

Case 2: There exists some $D$-branch containing $B_{2}$-, or
$B_{3}^{**}$-branch.

In this case, there is exactly one $D$-branch containing one or two
$B_{2}$-branches, or one $D$-branch containing a $B_{3}^{**}$-branch, other
$D$-branches are $D_{z}$-branches for some $z$. And $n_{4}=0$, from Theorems
1.5 and 1.6. As above, we can get a upper bound of right-hand side of (6),
which can be regarded as a revised version of right-hand sides of (28) and
(29): When $k\in\\{15,\dots,131\\}\setminus\\{52,53\\}$,

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle\leq$
$\displaystyle(d(v)-x-1-n_{k}-n_{k-1})(-f(d(v),4)+f(d(v^{\prime}),4))-f(d(v),k+1)$
(30)
$\displaystyle+f(d(v^{\prime}),k+1)+n_{k-1}(-f(d(v),k)+f(d(v^{\prime}),k))$
$\displaystyle+n_{k}(-f(d(v),k+1)+f(d(v^{\prime}),k+1))-f(d(v),4)+f(d(v^{\prime}),53)$
$\displaystyle+6(-f(2,1)+f(d(v^{\prime}),53))+364(-f(d(v),4)+f(53,4))$
$\displaystyle+(x-365)(-f(d(v),4)+f(d(v^{\prime}),4))$ $\displaystyle=$
$\displaystyle(d(v)-1-n_{k}-n_{k-1})(-f(d(v),4)+f(d(v^{\prime}),4))-f(d(v),k+1)$
$\displaystyle+f(d(v^{\prime}),k+1))+n_{k-1}(-f(d(v),k)+f(d(v^{\prime}),k))$
$\displaystyle+n_{k}(-f(d(v),k+1)+f(d(v^{\prime}),k+1))-f(d(v),4)+f(d(v^{\prime}),53)$
$\displaystyle+6(-f(2,1)+f(d(v^{\prime}),53))+364(-f(d(v),4)+f(53,4))$
$\displaystyle-365(-f(d(v),4)+f(d(v^{\prime}),4)),$

where $n_{i}$ is the number of $D_{i}$-branches, $0\leq n_{i}\leq
n_{i}^{max}$, $i\in\\{15,\dots,131\\}\setminus 52$. In particular, when
$k=53$,

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle\leq$
$\displaystyle(d(v)-x-1-n_{k})(-f(d(v),k)+f(d(v^{\prime}),k))-f(d(v),k+1)$
(31)
$\displaystyle+f(d(v^{\prime}),k+1)+n_{k}(-f(d(v),k+1)+f(d(v^{\prime}),k+1))-f(d(v),4)$
$\displaystyle+f(d(v^{\prime}),53)+6(-f(2,1)+f(d(v^{\prime}),53))+364(-f(d(v),4)+f(53,4))$
$\displaystyle+(x-365)(-f(d(v),4)+f(d(v^{\prime}),4))$ $\displaystyle=$
$\displaystyle(d(v)-x-1-n_{53})(-f(d(v),53)+f(d(v^{\prime}),53))$
$\displaystyle+(n_{53}+1)(-f(d(v),54)+f(d(v^{\prime}),54))-f(d(v),4)+f(d(v^{\prime}),53)$
$\displaystyle+6(-f(2,1)+f(d(v^{\prime}),53))+364(-f(d(v),4)+f(53,4))$
$\displaystyle+(x-365)(-f(d(v),4)+f(d(v^{\prime}),4)).$

Analogous to the arguments mentioning in Case $1$, we can get the
corresponding values of the maximum numbers of $B$-branches attached to the
root, which is listed in Tables 5 and 6.

Table 5:  The corresponding upper bounds on the numbers of $B$-branches, when the maximal size of $D$-branches in $G$ is $k$, $53\leq k\leq 131$, and $G$ contains some $B_{2}$-, or $B_{3}^{**}$-branch. $k$ | upper bound | $k$ | upper bound | $k$ | upper bound
---|---|---|---|---|---
$53$ | $919$ | $54$ | $882$ | $55$ | $798$
$56$ | $749$ | $57$ | $718$ | $58$ | $694$
$59$ | $673$ | $60$ | $655$ | $61$ | $640$
$62$ | $628$ | $63$ | $617$ | $64$ | $607$
$65$ | $599$ | $66$ | $593$ | $67$ | $586$
$68$ | $579$ | $69$ | $575$ | $70$ | $573$
$71$ | $571$ | $72$ | $566$ | $73$ | $564$
$74$ | $562$ | $75$ | $557$ | $76$ | $554$
$77$ | $555$ | $78$ | $553$ | $79$ | $550$
$80$ | $551$ | $81$ | $548$ | $82$ | $545$
$83$ | $546$ | $84$ | $547$ | $85$ | $548$
$86$ | $544$ | $87$ | $541$ | $88$ | $538$
$89$ | $535$ | $90$ | $535$ | $91$ | $536$
$92$ | $537$ | $93$ | $537$ | $94$ | $538$
$95$ | $538$ | $96$ | $539$ | $97$ | $540$
$98$ | $540$ | $99$ | $541$ | $100$ | $542$
$101$ | $542$ | $102$ | $543$ | $103$ | $543$
$104$ | $544$ | $105$ | $544$ | $106$ | $545$
$107$ | $546$ | $108$ | $546$ | $109$ | $547$
$110$ | $547$ | $111$ | $548$ | $112$ | $548$
$113$ | $549$ | $114$ | $549$ | $115$ | $550$
$116$ | $550$ | $117$ | $551$ | $118$ | $551$
$119$ | $552$ | $120$ | $553$ | $121$ | $553$
$122$ | $554$ | $123$ | $554$ | $124$ | $554$
$125$ | $555$ | $126$ | $555$ | $127$ | $556$
$128$ | $556$ | $129$ | $557$ | $130$ | $557$
$131$ | $558$ |  |  |  |
Table 6:  The corresponding upper bounds on the numbers of $B$-branches, when the maximal size of $D$-branches in $G$ is $k$, $15\leq k\leq 52$, and $G$ contains some $B_{2}$-, or $B_{3}^{**}$-branch.  $k$ | upper bound | $k$ | upper bound | $k$ | upper bound
---|---|---|---|---|---
$52$ | $916$ | $51$ | $908$ | $50$ | $900$
$49$ | $824$ | $48$ | $724$ | $47$ | $688$
$46$ | $661$ | $45$ | $639$ | $44$ | $618$
$43$ | $602$ | $42$ | $588$ | $41$ | $575$
$40$ | $564$ | $39$ | $554$ | $38$ | $544$
$37$ | $534$ | $36$ | $526$ | $35$ | $520$
$34$ | $514$ | $33$ | $508$ | $32$ | $501$
$31$ | $497$ | $30$ | $493$ | $29$ | $487$
$28$ | $483$ | $27$ | $479$ | $26$ | $475$
$25$ | $472$ | $24$ | $470$ | $23$ | $468$
$22$ | $465$ | $21$ | $463$ | $20$ | $460$
$19$ | $457$ | $18$ | $454$ | $17$ | $451$
$16$ | $448$ | $15$ | $426$ |  |

###  A.4 The existence of $B_{4}$-branches–the negativity of right-hand side
of (7)

Let $n_{z}$ be the number of $D_{z}$-branches adjacent to the root vertex $v$,
for $49\leq z\leq 54$. Further evaluating the right-hand side of (7), we get
the following upper bound on $ABC(G^{\prime})-ABC(G)$: If $G$ contains a
combination of $D_{z}$\- and $D_{z+1}$-branches, then

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle\leq$
$\displaystyle-(2z-3)f(d(v),z+1)-(2z-3)z\,f(z+1,4)-f(d(v),5)-f(4,2)$ (32)
$\displaystyle-f(2,1)+(2z-1)f(d(v)+1,z)+(2z-1)(z-1)f(z,4)$
$\displaystyle+n_{3}(-f(d(v),4)+f(d(v)+1,4))+(n_{4}-1)(-f(d(v),5)+f(d(v)+1,5))$
$\displaystyle+(d(v)-2z+3-n_{3}-n_{4})(-f(d(v),z+1)+f(d(v)+1,z+1)),$

and if $G$ contains a combination of $D_{z-1}$\- and $D_{z}$-branches, then

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle\leq$
$\displaystyle-(2z-3)f(d(v),z+1)-(2z-3)z\,f(z+1,4)-f(d(v),5)-f(4,2)$ (33)
$\displaystyle-f(2,1)+(2z-1)f(d(v)+1,z)+(2z-1)(z-1)f(z,4)$
$\displaystyle+n_{3}(-f(d(v),4)+f(d(v)+1,4))+(n_{4}-1)(-f(d(v),5)+f(d(v)+1,5))$
$\displaystyle+(d(v)-2z+3-n_{3}-n_{4})(-f(d(v),z)+f(d(v)+1,z)).$

Recall from Tables 3 and 4, $n_{3}+n_{4}$ is bounded from above, say
$n_{3}+n_{4}\leq M_{z,z+1}$ when $G$ contains a combination of $D_{z}$\- and
$D_{z+1}$-branches (e.g., $M_{52,53}=919$). Observe that the coefficient of
$n_{3}$ in both (32) and (33) is positive, i.e.,

$\displaystyle-f(d(v),4)+f(d(v)+1,4)$ $\displaystyle>$
$\displaystyle-f(d(v),z)+f(d(v)+1,z)$ $\displaystyle>$
$\displaystyle-f(d(v),z+1)+f(d(v)+1,z+1)$

from Proposition 1.1, which implies that both inequalities increase in
$n_{3}$. Substitute $n_{3}=M_{z,z+1}-n_{4}$ in (32) and
$n_{3}=M_{z-1,z}-n_{4}$ in (33) (the upper bounds of $n_{3}$), we get: If $G$
contains a combination of $D_{z}$\- and $D_{z+1}$-branches, then

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle\leq$
$\displaystyle-(2z-3)f(d(v),z+1)-(2z-3)z\,f(z+1,4)-f(d(v),5)-f(4,2)$ (34)
$\displaystyle-f(2,1)+(2z-1)f(d(v)+1,z)+(2z-1)(z-1)f(z,4)$
$\displaystyle+(M_{z,z+1}-n_{4})(-f(d(v),4)+f(d(v)+1,4))$
$\displaystyle+(n_{4}-1)(-f(d(v),5)+f(d(v)+1,5))$
$\displaystyle+(d(v)-2z+3-M_{z,z+1})(-f(d(v),z+1)+f(d(v)+1,z+1)),$

and if $G$ contains a combination of $D_{z-1}$\- and $D_{z}$-branches, then

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle\leq$
$\displaystyle-(2z-3)f(d(v),z+1)-(2z-3)z\,f(z+1,4)-f(d(v),5)-f(4,2)$ (35)
$\displaystyle-f(2,1)+(2z-1)f(d(v)+1,z)+(2z-1)(z-1)f(z,4)$
$\displaystyle+(M_{z-1,z}-n_{4})(-f(d(v),4)+f(d(v)+1,4))$
$\displaystyle+(n_{4}-1)(-f(d(v),5)+f(d(v)+1,5))$
$\displaystyle+(d(v)-2z+3-M_{z-1,z})(-f(d(v),z)+f(d(v)+1,z)).$

Further, the coefficient of $n_{4}$ in both (34) and (35) is negative, i.e.,

$-f(d(v),5)+f(d(v)+1,5)<-f(d(v),4)+f(d(v)+1,4)$

from Proposition 1.1, which implies that both inequalities decrease in
$n_{4}$. Set $n_{4}=1$ (the lower bound of $n_{4}$), it follows that: If $G$
contains a combination of $D_{z}$\- and $D_{z+1}$-branches, then

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle\leq$
$\displaystyle-(2z-3)f(d(v),z+1)-(2z-3)z\,f(z+1,4)-f(d(v),5)-f(4,2)$ (36)
$\displaystyle-f(2,1)+(2z-1)f(d(v)+1,z)+(2z-1)(z-1)f(z,4)$
$\displaystyle+(M_{z,z+1}-1)(-f(d(v),4)+f(d(v)+1,4))$
$\displaystyle+(d(v)-2z+3-M_{z,z+1})(-f(d(v),z+1)+f(d(v)+1,z+1)),$

and if $G$ contains a combination of $D_{z-1}$\- and $D_{z}$-branches, then

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle\leq$
$\displaystyle-(2z-3)f(d(v),z+1)-(2z-3)z\,f(z+1,4)-f(d(v),5)-f(4,2)$ (37)
$\displaystyle-f(2,1)+(2z-1)f(d(v)+1,z)+(2z-1)(z-1)f(z,4)$
$\displaystyle+(M_{z-1,z}-1)(-f(d(v),4)+f(d(v)+1,4))$
$\displaystyle+(d(v)-2z+3-M_{z-1,z})(-f(d(v),z)+f(d(v)+1,z)).$

In the sequel, we consider the five possible cases separately.

$\bullet$ $G$ contains a combination of $D_{53}$\- and $D_{54}$-branches.

In this case it holds that $n_{3}+n_{4}\leq 882$ (see Table 3), i.e.,
$M_{53,54}=882$. It holds also that $n_{53}\leq 260$ and $n_{54}\leq 130$ (see
Table 1). It implies that $d(v)\leq 882+260+130=1272$. A straightforward
verification shows that the right-hand side of (36) when $z=53$, and the
right-hand side of (37) when $z=54$, are negative for $1228\leq d(v)\leq
1272$.

$\bullet$ $G$ contains a combination of $D_{52}$\- and $D_{53}$-branches.

Here, we have $n_{3}+n_{4}\leq 919$ (see Table 3), i.e., $M_{52,53}=919$,
$n_{53}\leq 260$ (from Table 1).

If $n_{52}<2\cdot 52-3=101$, then it must hold that $n_{53}\geq 2\cdot
53-3=103$. Then, we choose $z=53$, and note that $d(v)\leq 919+100+260=1279$.
A straightforward verification shows that the right-hand side of (37) is
negative for $1228\leq d(v)\leq 1279$.

If $n_{52}\geq 101$, then we choose $z=52$. From (36), the change of the ABC
index in this case is

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle\leq$
$\displaystyle-101f(d(v),53)-5252f(53,4)-f(d(v),5)-f(4,2)-f(2,1)$ (38)
$\displaystyle+103f(d(v)+1,52)+5253f(52,4)+918(-f(d(v),4)+f(d(v)+1,4))$
$\displaystyle+(d(v)-1020)(-f(d(v),53)+f(d(v)+1,53)).$

At this stage, we consider the terms in right-hand side of (38) related to
$d(v)$, which are

$\displaystyle-101f(d(v),53)-f(d(v),5)+103f(d(v)+1,52)+918(-f(d(v),4)+f(d(v)+1,4))$
$\displaystyle+(d(v)-1020)(-f(d(v),53)+f(d(v)+1,53))$ $\displaystyle=$
$\displaystyle 102(-f(d(v),53)+f(d(v)+1,52))+918(-f(d(v),4)+f(d(v)+1,4))$
$\displaystyle+(d(v)-1020)f(d(v)+1,53)-(d(v)-1021)f(d(v),53)+f(d(v)+1,52)-f(d(v),5)$
$\displaystyle<$ $\displaystyle
102(-f(d(v),53)+f(d(v)+1,52))+(d(v)-1020)f(d(v)+1,53)-(d(v)-1021)f(d(v),53)$
$\displaystyle+f(d(v)+1,52)-f(d(v),5).$

By Proposition 1.1, we have that $-f(d(v),53)+f(d(v)+1,52)$ increases in
$d(v)$, and thus

$\displaystyle-f(d(v),53)+f(d(v)+1,52)$ $\displaystyle\leq$
$\displaystyle\lim_{d(v)\rightarrow+\infty}(-f(d(v),53)+f(d(v)+1,52))\quad=\quad-\sqrt{\frac{1}{53}}+\sqrt{\frac{1}{52}}.$

It is also not hard to verify that both
$(d(v)-1020)f(d(v)+1,53)-(d(v)-1021)f(d(v),53)$ and $f(d(v)+1,52)-f(d(v),5)$
decrease in $d(v)\geq 3$. Thus, we get a weaker upper bound than that in (38):

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle<$ $\displaystyle
102\left(-\sqrt{\frac{1}{53}}+\sqrt{\frac{1}{52}}\right)+(d(v)-1020)f(d(v)+1,53)-(d(v)-1021)f(d(v),53)$
$\displaystyle+f(d(v)+1,52)-f(d(v),5)-5252f(53,4)-2f(2,1)+5253f(52,4),$

which decreases in $d(v)$. In particular, when $d(v)=1228$, the right-hand
side of above inequality is equal to $-0.00201013$. Consequently, we can
conclude that for $d(v)\geq 1228$, we can always get a negative change after
applying the transformation $\mathcal{T}_{7}$.

$\bullet$ $G$ contains a combination of $D_{51}$\- and $D_{52}$-branches.

Here, it holds that $n_{3}+n_{4}\leq 916$ (see Table 4), i.e.,
$M_{51,52}=916$, and $n_{51}\leq 364$, when $d(v)\geq 3249$ (see Table 2).

We consider first the case $z=51$. In this case, we may assume that
$n_{52}<2\cdot 52-3=101$. When $d(v)\geq 3249$, $n_{51}\leq 364$, so $d(v)\leq
916+364+100=1380$, a contradiction. When $d(v)<3249$, the right-hand side of
(36) is negative for $1228\leq d(v)<3249$. When $z=52$ ($n_{52}\geq 101$), the
deduction is very similar to the previous case that $G$ contains a combination
of $D_{52}$\- and $D_{53}$-branches. Therefore, we omit the repetition of the
same arguments here.

$\bullet$ $G$ contains a combination of $D_{50}$\- and $D_{51}$-branches.

In this case, it holds that $n_{3}+n_{4}\leq 908$ (see Table 4), i.e.,
$M_{50,51}=908$, $n_{50}\leq 182$ when $d(v)\geq 1358$, and $n_{51}\leq 364$
when $d(v)\geq 3249$ (see Table 2).

If $d(v)\geq 3249$, then we have $d(v)\leq 908+182+364=1454$, which is a
contradiction. Thus $1228\leq d(v)<3249$.

If $z=51$, then the right-hand side of (37) is always negative from direct
calculations, for $1228\leq d(v)<3249$. Next suppose that $z=50$. Assume that
$n_{51}<2\cdot 51-3=99$. Note that $d(v)<1358$, otherwise, $n_{50}\leq 182$,
and thus $d(v)\leq 908+182+98=1188$, a contradiction. Moreover, $n_{50}\geq
222$, otherwise, $d(v)\leq 908+221+98=1227$, a contradiction again.

Here we consider in addition again the transformation $\mathcal{T}_{5}$, to
show that particular configurations are impossible. Adapting to the notation
and possible configurations used here, we have the following upper bound on
the change of the ABC index after applying $\mathcal{T}_{5}$:

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle\leq$
$\displaystyle-x\,f(d(v),z+1)-x\,z\,f(z+1,4)$ (39)
$\displaystyle+3f(4,2)+3f(2,1)+n_{k}f(d(v)-7,k+1)+n_{k-1}f(d(v)-7,k)$
$\displaystyle+k\,n_{k}f(k+1,4)+(k-1)n_{k-1}f(k,4)$
$\displaystyle+(d(v)-x-n_{3}-n_{4})(-f(d(v),z+2)+f(d(v)-7,z+2))$
$\displaystyle+n_{3}(-f(d(v),4)+f(d(v)-7,4))+n_{4}(-f(d(v),5)+f(d(v)-7,5)).\qquad\quad$

It is easy to see that the right-hand side of (39) decreases in $n_{3}$ and
$n_{4}$, respectively (just by noting that the coefficients about $n_{3}$ and
$n_{4}$ are both negative, from Proposition 1.2). So the worst case is when
$n_{3}=0$ and $n_{4}=1$ (the possible minimum values of $n_{3}$ and $n_{4}$).
Here, as in the Appendix A.2 (Table 2), we set $z=50$, $x=222$, $k=52$ (so
$n_{52}=136$ and $n_{51}=79$). Together with $n_{3}=0$ and $n_{4}=1$, one can
check the negativity of right-hand side of (39) directly, for $1228\leq
d(v)<1358$.

$\bullet$ $G$ contains a combination of $D_{49}$\- and $D_{50}$-branches.

Here it holds that $n_{3}+n_{4}\leq 900$ (see Table 4), i.e., $M_{49,50}=900$.
We have also that $n_{49}\leq 121$ when $d(v)\geq 825$, and $n_{50}\leq 182$
when $d(v)\geq 1358$ (see Table 2). Thus, when $d(v)\geq 1358$, then $d(v)\leq
900+121+182=1203$, which is a contradiction to the assumption that $d(v)\geq
1358$. Thus $1228\leq d(v)<1358$.

If $n_{50}<2\cdot 50-3=97$, then $d(v)\leq 900+121+96=1117$, a contradiction.
So we must have $n_{50}\geq 97$, i.e., $z=50$.

We claim that $n_{49}\leq 94$. Otherwise, in the right-hand side of (39), set
$z=49$, $x=95$, $k=53$ (so $n_{53}=80$ and $n_{52}=8$), together with
$n_{3}=0$ and $n_{4}=1$, one can find that the right-hand side of (39) is
negative from direct calculations, for $1228\leq d(v)<1358$. Now from
$n_{49}\leq 94$, we further have $n_{50}\geq 234$, otherwise, $d(v)\leq
900+94+233=1227$, a contradiction. In last case, we have shown that when
$n_{50}\geq 222$, the right-hand side of (39) would be negative for $1228\leq
d(v)<1358$. Applying it here, we can also deduce a negative change of ABC
index (since $n_{50}\geq 234>222$).

###  A.5 $B$-branches attached to the root–the negativity of right-hand side
of (8)

From Proposition 1.2, $-f(d(v),d(v_{i}))+f(d(v)-x,d(v_{i}))$ increases in
$d(v_{i})$, thus the worst case is when $d(v_{i})$ is chosen as large as
possible. Now we get further upper bounds on $ABC(G^{\prime})-ABC(G)$: If $G$
contains $D$-branches of size $z+1$, in addition to $D_{z}$-branches, then

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle\leq$ $\displaystyle
x(-f(d(v),z+1)+f(d(v)-x,z+2))+xz(-f(z+1,4)+f(z+2,4))$ (40)
$\displaystyle+x(-f(d(v),4)+f(z+2,4))$
$\displaystyle+(d(v)-2x)(-f(d(v),z+2)+f(d(v)-x,z+2)),$

otherwise,

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle\leq$ $\displaystyle
x(-f(d(v),z+1)+f(d(v)-x,z+2))+xz(-f(z+1,4)+f(z+2,4))$ (41)
$\displaystyle+x(-f(d(v),4)+f(z+2,4))$
$\displaystyle+(d(v)-2x)(-f(d(v),z+1)+f(d(v)-x,z+1)),$

in either case, $1\leq x\leq 919$, from Lemma 3.1.

If there is no $D_{52}$-branch in $G$, then no matter $z=50,51$ or $53$, a
direct check would show that the right-hand side of (40) or (41) is always
negative, since $d(v)$ is bounded (from Tables 1 and 2). In the remaining
cases, $D_{52}$-branches must occur, so we assume that $z=52$ in the
following. More precisely, we may assume that $G$ contains at least $x$
$D_{52}$-branches, where $1\leq x\leq 919$.

First assume that there are $D$-branches of size $53$ in $G$. Set $z=52$ in
(40), it leads to

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle\leq$ $\displaystyle
x(-f(d(v),53)+f(d(v)-x,54))+52x(-f(53,4)+f(54,4))$
$\displaystyle+x(-f(d(v),4)+f(54,4))+(d(v)-2x)(-f(d(v),54)+f(d(v)-x,54)).$

Recall that there can be at most $260$ $D_{53}$-branches (Table 1), and at
most one $D_{53}^{**}$-branch, thus a more precise version of above estimation
of the difference $ABC(G^{\prime})-ABC(G)$ should be

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle\leq$ $\displaystyle
x(-f(d(v),53)+f(d(v)-x,54))+52x(-f(53,4)+f(54,4))$ (42)
$\displaystyle+x(-f(d(v),4)+f(54,4))+261(-f(d(v),54)+f(d(v)-x,54))$
$\displaystyle+(d(v)-2x-261)(-f(d(v),53)+f(d(v)-x,53)).$

The terms in the right-hand side of (42) related to $d(v)$ are

$\displaystyle
x(-f(d(v),53)+f(d(v)-x,54))-x\,f(d(v),4)+261(-f(d(v),54)+f(d(v)-x,54))$
$\displaystyle+(d(v)-2x-261)(-f(d(v),53)+f(d(v)-x,53))$ $\displaystyle=$
$\displaystyle
x(-f(d(v),53)+f(d(v)-x,54))+261(-f(d(v),54)+f(d(v)-x,54))+x(-f(d(v),4)+f(d(v),53))$
$\displaystyle-(d(v)-x-261)f(d(v),53)+(d(v)-2x-261)f(d(v)-x,53).$

By Proposition 1.2, we have the following observations:

  * •

$-f(d(v),53)+f(d(v)-x,54)$ decreases in $d(v)$;

  * •

$-f(d(v),54)+f(d(v)-x,54)$ decreases in $d(v)$;

  * •

$-f(d(v),4)+f(d(v),53)$ decreases in $d(v)$.

It is not hard to verify that
$-(d(v)-x-261)f(d(v),53)+(d(v)-2x-261)f(d(v)-x,53)$ increases in $d(v)$, and
thus

$\displaystyle-(d(v)-x-261)f(d(v),53)+(d(v)-2x-261)f(d(v)-x,53)$
$\displaystyle\leq$
$\displaystyle\lim_{d(v)\rightarrow+\infty}(-(d(v)-x-261)f(d(v),53)+(d(v)-2x-261)f(d(v)-x,53))$
$\displaystyle=$ $\displaystyle-\frac{x}{\sqrt{53}}.$

Now, we get another upper bound on $ABC(G^{\prime})-ABC(G)$:

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle\leq$ $\displaystyle
x(-f(d(v),53)+f(d(v)-x,54))+261(-f(d(v),54)+f(d(v)-x,54))$ (43)
$\displaystyle+x(-f(d(v),4)+f(d(v),53))-\frac{x}{\sqrt{53}}$
$\displaystyle+52x(-f(53,4)+f(54,4))+x\,f(54,4),$

which decreases in $d(v)$. When $d(v)=4199$, thus so is for $d(v)\geq 4199$,
the right-hand side of (43) is always negative for $1\leq x\leq 919$. As to
$2956\leq d(v)<4199$, we resort to the right-hand side of (42), which is
always negative for $1\leq x\leq 919$.

Next assume that there is no $D$-branch of size $53$. In this case, we use
(41) by setting $z=52$, i.e.,

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle\leq$ $\displaystyle
x(-f(d(v),53)+f(d(v)-x,54))+52x(-f(53,4)+f(54,4))$ (44)
$\displaystyle+x(-f(d(v),4)+f(54,4))$
$\displaystyle+(d(v)-2x)(-f(d(v),53)+f(d(v)-x,53)).$

As above, we can get

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle\leq$ $\displaystyle
x(-f(d(v),53)+f(d(v)-x,54))+x(-f(d(v),4)+f(d(v),53))$ (45)
$\displaystyle-\frac{x}{\sqrt{53}}+52x(-f(53,4)+f(54,4))+x\,f(54,4),$

which decreases in $d(v)$. For $d(v)\geq 3990$, the right-hand side of (45) is
always negative for $1\leq x\leq 919$ (actually we need only to check the case
when $d(v)=3990$). For the remaining case $2956\leq d(v)<3990$, we use the
right-hand side of (44), which is again always negative for $1\leq x\leq 919$.

###  A.6 The upper bound of size of $D_{z,1}^{2}$-branches–the negativity of
right-hand side of (9)

Clearly, every neighbor of $v$ in $\bar{G}$ is of degree at least $4$, thus

$\sum_{xv\in
E(\bar{G})}(-f(d(v),d(x))+f(d(v)+3,d(x)))\leq(d(v)-1)(-f(d(v),4)+f(d(v)+3,4)),$

by Proposition 1.1. Thus, we get

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle\leq$
$\displaystyle(d(v)-1)(-f(d(v),4)+f(d(v)+3,4))-f(d(v),z+1)$ (46)
$\displaystyle+2f\left(d(v)+3,\frac{z-1}{2}\right)-f(z+1,3)+2f(d(v)+3,5)-(z-1)f(z+1,4)$
$\displaystyle+(z-3)f\left(\frac{z-1}{2},4\right)$ $\displaystyle=$
$\displaystyle-(d(v)-1)f(d(v),4)+(d(v)+2)f(d(v)+3,4)$
$\displaystyle+2(-f(d(v)+3,4)+f(d(v)+3,5))-f(d(v)+3,4)$
$\displaystyle+f\left(d(v)+3,\frac{z-1}{2}\right)-f(d(v),z+1)+f\left(d(v)+3,\frac{z-1}{2}\right)$
$\displaystyle-f(z+1,3)-(z-1)f(z+1,4)+(z-3)f\left(\frac{z-1}{2},4\right).$

Let us focus on the terms related to $d(v)$ on the right-hand side of (46):

  * •

It is not hard to verify that $-(d(v)-1)f(d(v),4)+(d(v)+2)f(d(v)+3,4)$
decreases in $d(v)$.

  * •

Both $-f(d(v)+3,4)+f(d(v)+3,5)$ and
$-f(d(v)+3,4)+f\left(d(v)+3,\frac{z-1}{2}\right)$ decrease in $d(v)$ by
Proposition 1.2.

  * •

$-f(d(v),z+1)+f\left(d(v)+3,\frac{z-1}{2}\right)$ increases in $d(v)$ by
Proposition 1.1, which implies that

$\displaystyle-f(d(v),z+1)+f\left(d(v)+3,\frac{z-1}{2}\right)$
$\displaystyle\leq$
$\displaystyle\lim_{d(v)\rightarrow+\infty}\left(-f(d(v),z+1)+f\left(d(v)+3,\frac{z-1}{2}\right)\right)\quad=\quad-\sqrt{\frac{1}{z+1}}+\sqrt{\frac{1}{\frac{z-1}{2}}}.$

Therefore, a (weaker) upper bound on $ABC(G^{\prime})-ABC(G)$ follows:

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle\leq$
$\displaystyle-(d(v)-1)f(d(v),4)+(d(v)+2)f(d(v)+3,4)$ (47)
$\displaystyle+2(-f(d(v)+3,4)+f(d(v)+3,5))$
$\displaystyle-f(d(v)+3,4)+f\left(d(v)+3,\frac{z-1}{2}\right)-\sqrt{\frac{1}{z+1}}+\sqrt{\frac{1}{\frac{z-1}{2}}}$
$\displaystyle-f(z+1,3)-(z-1)f(z+1,4)+(z-3)f\left(\frac{z-1}{2},4\right),$

which decreases in $d(v)\geq z+1$.

Setting $d(v)=z+1$ in the right-hand side of (47), it leads to

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle\leq$
$\displaystyle-z\,f(z+1,4)+(z+3)f(z+4,4)+2(-f(z+4,4)+f(z+4,5))$ (48)
$\displaystyle-f(z+4,4)+f\left(z+4,\frac{z-1}{2}\right)-\sqrt{\frac{1}{z+1}}+\sqrt{\frac{1}{\frac{z-1}{2}}}$
$\displaystyle-f(z+1,3)-(z-1)f(z+1,4)+(z-3)f\left(\frac{z-1}{2},4\right).$

The right-hand side of (48) is negative when $113\leq z\leq 131$. When $99\leq
z\leq 111$ ($z$ is odd), we set $d(v)=173$ in (47), and then the right-hand
side is negative for $99\leq z\leq 111$. For the remaining cases $99\leq z\leq
111$ and $z+1\leq d(v)\leq 172$, we resort to the right-hand side of (46),
which can be also verified that is negative.

###  A.7 The existence of $D_{z,2}^{2}$-branches–the negativity of right-hand
side of (12)

For each $y$ such that $yv\in E(\bar{G})$, by Proposition 1.1,
$-f(d(v),d(y))+f(d(v)+2,d(y))$ decreases in $d(y)$. Thus, the worst case is
when $d(y)$ as small as possible, i.e., $d(y)=4$. Now we get an upper bound on
$ABC(G^{\prime})-ABC(G)$:

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle\leq$
$\displaystyle(d(v)-x-1)(-f(d(v),4)+f(d(v)+2,4))-x\,f(d(v),z+1)$ (49)
$\displaystyle-x\,z\,f(z+1,4)-f(d(v),k+1)-(k-2)f(k+1,4)-2f(k+1,3)$
$\displaystyle+(x+2)f(d(v)+2,z)+(x+2)(z-1)f(z,4)+f(d(v)+2,5)$ $\displaystyle=$
$\displaystyle-(d(v)-x-1)f(d(v),4)+(d(v)-x+1)f(d(v)+2,4)$
$\displaystyle+2(-f(d(v)+2,4)+f(d(v),z+1))-f(d(v),k+1)+f(d(v)+2,5)$
$\displaystyle+(x+2)(-f(d(v),z+1)+f(d(v)+2,z))-x\,z\,f(z+1,4)$
$\displaystyle-(k-2)f(k+1,4)-2f(k+1,3)+(x+2)(z-1)f(z,4).$

It is easy to verify that $-(d(v)-x-1)f(d(v),4)+(d(v)-x+1)f(d(v)+2,4)$
decreases in $d(v)$, for each fixed positive $x$. By Propositions 1.1 and 1.2,

  * •

$-f(d(v)+2,4)+f(d(v),z+1)$ decreases in $d(v)$;

  * •

$-f(d(v),k+1)+f(d(v)+2,5)$ increases in $d(v)$, and thus,

$\displaystyle-f(d(v),k+1)+f(d(v)+2,5)$ $\displaystyle\leq$
$\displaystyle\lim_{d(v)\rightarrow+\infty}(-f(d(v),k+1)+f(d(v)+2,5))\quad=\quad-\sqrt{\frac{1}{k+1}}+\sqrt{\frac{1}{5}};$

  * •

$-f(d(v),z+1)+f(d(v)+2,z)$ increases in $d(v)$, and therefore,

$\displaystyle-f(d(v),z+1)+f(d(v)+2,z)$ $\displaystyle\leq$
$\displaystyle\lim_{d(v)\rightarrow+\infty}(-f(d(v),z+1)+f(d(v)+2,z))\quad=\quad-\sqrt{\frac{1}{z+1}}+\sqrt{\frac{1}{z}}.$

In conclusion, it leads to another (weaker) upper bound on
$ABC(G^{\prime})-ABC(G)$:

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle\leq$
$\displaystyle-(d(v)-x-1)f(d(v),4)+(d(v)-x+1)f(d(v)+2,4)$
$\displaystyle+2(-f(d(v)+2,4)+f(d(v),z+1))-\sqrt{\frac{1}{k+1}}+\sqrt{\frac{1}{5}}$
$\displaystyle+(x+2)\left(-\sqrt{\frac{1}{z+1}}+\sqrt{\frac{1}{z}}\right)-x\,z\,f(z+1,4)-(k-2)f(k+1,4)$
$\displaystyle-2f(k+1,3)+(x+2)(z-1)f(z,4),$

which decreases in $d(v)\geq 146$.

When $d(v)=2400$, and thus $d(v)\geq 2400$, the right-hand side of the above
inequality is negative, for any combination of $x,k,z$ satisfying
$z\in[43,56]$, $k\in[34,50]$ and $x=2z-k$ (where $x,k,z$ are all bounded).
With the same constraints about $x,k,z$, when $146\leq d(v)<2400$, the right-
hand side of (49) is negative again.

###  A.8 The existence of $D_{z,1}^{2}$-branches–the negativity of right-hand
side of (13)

In the same manner as in Appendix A.7, we get also here the following upper
bound on $ABC(G^{\prime})-ABC(G)$ after applying transformation
$\mathcal{T}_{12}$:

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle\leq$
$\displaystyle-(d(v)-x-1)f(d(v),4)+(d(v)-x+4)f(d(v)+5,4)$ (50)
$\displaystyle+5(-f(d(v)+5,4)+f(d(v),k+1))-x\,z\,f(z+1,4)-(k-1)f(k+1,4)$
$\displaystyle+6(-f(d(v),k+1)+f(d(v),z+1))+(x+6)(-f(d(v),z+1)$
$\displaystyle+(x+6)(-f(d(v),z+1)+f(d(v)+5,z))-f(k+1,3)$
$\displaystyle-2f(3,2)-2f(2,1)+(x+6)(z-1)f(z,4),\qquad$

and further get another (weaker) upper bound which decreases in $d(v)\geq
x+1$:

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle\leq$
$\displaystyle-(d(v)-x-1)f(d(v),4)+(d(v)-x+4)f(d(v)+5,4)$ (51)
$\displaystyle+5(-f(d(v)+5,4)+f(d(v),k+1))-x\,z\,f(z+1,4)-(k-1)f(k+1,4)$
$\displaystyle+6(-f(d(v),k+1)+f(d(v),z+1))+(x+6)\left(-\sqrt{\frac{1}{z+1}}+\sqrt{\frac{1}{z}}\right)$
$\displaystyle-f(k+1,3)-2f(3,2)-2f(2,1)+(x+6)(z-1)f(z,4).$

Substituting $d(v)=4100$ into the right-hand side of (51), it can be verified
that the right-hand side of (51), for each $z\in\\{51,52\\}$ with constraints
$k\in[z-5,z]$ and $x=6z-k-5$, is negative. Due to the monotonicity on $d(v)$,
it follows that it is also negative for $d(v)\geq 4100$. For the remaining
part $x+1\leq d(v)<4100$, by direct calculations, the right-hand side of (50)
is negative under the same constraints on $x$, $k$, and $z$.

###  A.9 The upper bound of size of $D_{z}^{**}$-branches–the negativity of
right-hand side of (14)

Observe that $d(x)\geq 4$ for each $x$ with $xv\in E(\bar{G})$, and thus

$\sum_{xv\in
E(\bar{G})}(-f(d(v),d(x))+f(d(v)+2,d(x)))\leq(d(v)-1)(-f(d(v),4)+f(d(v)+2,4)),\qquad$

by Proposition 1.1. So we have the following (weaker) upper bound on
$ABC(G^{\prime})-ABC(G)$:

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle\leq$
$\displaystyle(d(v)-1)(-f(d(v),4)+f(d(v)+2,4))-f(d(v),z+1)$ (52)
$\displaystyle+2f\left(d(v)+2,\frac{z+1}{2}\right)-z\cdot
f(z+1,4)+(z-1)f\left(\frac{z+1}{2},4\right)$
$\displaystyle-f(4,3)+f(d(v)+2,5)$ $\displaystyle=$
$\displaystyle-(d(v)-1)f(d(v),4)+(d(v)+1)f(d(v)+2,4)$
$\displaystyle+2\left(-f(d(v)+2,4)+f\left(d(v)+2,\frac{z+1}{2}\right)\right)-f(d(v),z+1)$
$\displaystyle+f(d(v)+2,5)-z\,f(z+1,4)+(z-1)f\left(\frac{z+1}{2},4\right)-f(4,3).$

As to the terms related to $d(v)$ in the right-hand side of (52), we have the
following observations:

  * •

It is not hard to verify that $-(d(v)-1)f(d(v),4)+(d(v)+1)f(d(v)+2,4)$
decreases in $d(v)$;

  * •

$-f(d(v)+2,4)+f\left(d(v)+2,\frac{z+1}{2}\right)$ decreases in $d(v)$, by
Proposition 1.2;

  * •

$-f(d(v),z+1)+f(d(v)+2,5)$ increases in $d(v)$, by Proposition 1.1, i.e.,

$\displaystyle-f(d(v),z+1)+f(d(v)+2,5)$ $\displaystyle\leq$
$\displaystyle\lim_{d(v)\rightarrow+\infty}(-f(d(v),z+1)+f(d(v)+2,5))$
$\displaystyle=$ $\displaystyle-\sqrt{\frac{1}{z+1}}+\sqrt{\frac{1}{5}}.$

Therefore, we obtain one more weaker upper bound on $ABC(G^{\prime})-ABC(G)$:

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle\leq$
$\displaystyle-(d(v)-1)f(d(v),4)+(d(v)+1)f(d(v)+2,4)$ (53)
$\displaystyle+2\left(-f(d(v)+2,4)+f\left(d(v)+2,\frac{z+1}{2}\right)\right)$
$\displaystyle-\sqrt{\frac{1}{z+1}}+\sqrt{\frac{1}{5}}-z\,f(z+1,4)+(z-1)f\left(\frac{z+1}{2},4\right)-f(4,3),\qquad$

which decreases in $d(v)\geq z+1$. After setting $d(v)=z+1$ in the right-hand
side of (53), we have

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle\leq$
$\displaystyle-z\,f(z+1,4)+(z+2)f(z+3,4)+2\left(-f(z+3,4)+f\left(z+3,\frac{z+1}{2}\right)\right)$
$\displaystyle-\sqrt{\frac{1}{z+1}}+\sqrt{\frac{1}{5}}-z\,f(z+1,4)+(z-1)f\left(\frac{z+1}{2},4\right)-f(4,3),$

in which the right-hand side is always negative for $117\leq z\leq 131$. As to
$75\leq z\leq 115$ ($z$ is odd), set $d(v)=264$ in the right-hand side of
(53), the right-hand side would be again always negative for $75\leq z\leq
115$. For the remaining parts when $75\leq z\leq 115$ and $z+1\leq d(v)\leq
263$, we resort to the right-hand side of (52), which is always negative from
direct calculations.

###  A.10 The existence of $D_{z}^{**}$-branches–the negativity of right-hand
side of (15)

Similarly as in Appendix A.7, we get a new upper bound on
$ABC(G^{\prime})-ABC(G)$:

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle\leq$
$\displaystyle-(d(v)-x-1)f(d(v),4)+(d(v)-x+1)f(d(v)+2,4)$ (54)
$\displaystyle+(-f(d(v)+2,4)+f(d(v),z+1))+(-f(d(v)+2,4)+f(d(v)+2,k))$
$\displaystyle+(-f(d(v),k+1)+f(d(v)+2,5))$
$\displaystyle+(x+1)(-f(d(v),z+1)+f(d(v)+2,z))-x\,z\,f(z+1,4)$
$\displaystyle-k\,f(k+1,4)-f(4,3)+(x+1)(z-1)f(z,4)+(k-1)f(k,4).$

Further we obtain

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle\leq$
$\displaystyle-(d(v)-x-1)f(d(v),4)+(d(v)-x+1)f(d(v)+2,4)$ (55)
$\displaystyle+(-f(d(v)+2,4)+f(d(v),z+1))+(-f(d(v)+2,4)+f(d(v)+2,k))$
$\displaystyle+\left(-\sqrt{\frac{1}{k+1}}+\sqrt{\frac{1}{5}}\right)+(x+1)\left(-\sqrt{\frac{1}{z+1}}+\sqrt{\frac{1}{z}}\right)-x\,z\,f(z+1,4)$
$\displaystyle-k\,f(k+1,4)-f(4,3)+(x+1)(z-1)f(z,4)+(k-1)f(k,4),$

decreasing in $d(v)$. After substituting $d(v)$ by $556$ into the right-hand
side of (55), a straightforward verification shows that the right-hand side of
(55) is negative for each $z\in[46,57]$, $k\in[\max\\{47,z-1\\},z+1]$ and
$x=z-1$. Since the right-hand side of (55) decreases in $d(v)\geq x+1$, it
follows that it is negative for any $d(v)\geq 556$ under the above mentioned
constraints. When $x+1\leq d(v)<556$, we resort to the right-hand side of
(54), which can be shown that is negative by direct calculations.

###  A.11 All $B_{4}$-branches are adjacent to the root vertex–the negativity
of right-hand side of (1)

Here we use again the techniques in Appendix A.7. Then an upper bound on the
change of the ABC index comes:

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle\leq$
$\displaystyle-(d(v)+x-5)f(d(v),16)+(d(v)+2x-5)f(d(v)+x,16)$ (56)
$\displaystyle+(4-x)(-f(d(v),5)+f(d(v)+x,5))$
$\displaystyle+x(-f(d(v)+x,16)+f(d(v)+x,5))$
$\displaystyle+(z-x)(-f(z+1,4)+f(z+1-x,4))$
$\displaystyle+(-f(d(v),z+1)+f(d(v)+x,z-x+1))-x\,f(z+1,5).$

Aiming to obtain a (weaker) upper bound which decreases in $d(v)$, we get:

$\displaystyle ABC(G^{\prime})-ABC(G)$ $\displaystyle\leq$
$\displaystyle-(d(v)+x-5)f(d(v),16)+(d(v)+2x-5)f(d(v)+x,16)$ (57)
$\displaystyle+x\left(-\sqrt{\frac{1}{16}}+\sqrt{\frac{1}{5}}\right)+(z-x)(-f(z+1,4)+f(z+1-x,4))$
$\displaystyle+\left(-\sqrt{\frac{1}{z+1}}+\sqrt{\frac{1}{z-x+1}}\right)-x\,f(z+1,5).$

By direct calculations, we deduce that the right-hand side of (57) is negative
for $d(v)\geq 300$ (actually set $d(v)=300$ is enough due to the monotonicity
on $d(v)$), $1\leq x\leq 4$ and $15\leq z\leq 215$. For the remaining part
$z+1\leq d(v)<300$, $1\leq x\leq 4$ and $15\leq z\leq 215$, the right-hand
side of (56) could help us, which is negative from direct calculations again.

###  A.12 Minimal-ABC trees

In this section, we present the structures of the minimal-ABC trees. The exact
parameters are given only for trees of smaller orders. The parameters for an
arbitrary tree can be determined as it was elaborated in Section 5.1. For
example, it can be obtained that:

  * •

When $n=5047$, then $z=50$, $n_{z}=7$, $n_{z+1}=4$, $n_{3}=164$, and
$n_{4}=1$;

  * •

When $n=6956$, then $z=49$, $n_{z}=1$, $n_{z+1}=15$, $n_{3}=191$, and
$n_{4}=1$;

  * •

When $n=16443$, then $z=49$, $n_{z}=0$, $n_{z+1}=41$, and $n_{3}=293$;

  * •

When $n=1014814$, then $z=51$, $n_{z}=2594$, $n_{z+1}=236$, and $n_{3}=3$;

  * •

When $n=1142741$, then $z=51$, $n_{z}=3035$, $n_{z+1}=154$;

  * •

When $n=1257073$, then $z=51$, $n_{z}=259$, $n_{z+1}=3190$;

  * •

When $n=13290000000000000$, then $z=51$, $n_{z}=178$,
$n_{z+1}=36410958903935$.

Figure 19: Minimal-ABC trees with $n$ vertices, where $n\equiv 0\pmod{7}$.
Figure 20: Minimal-ABC trees with $n$ vertices, where $n\equiv 0\pmod{7}$.
Figure 21: Minimal-ABC trees with $n$ vertices, where $n\equiv 1\pmod{7}$.
Figure 22: Minimal-ABC trees with $n$ vertices, where $n\equiv 1\pmod{7}$.
Figure 23: Minimal-ABC trees with $n$ vertices, where $n\equiv 2\pmod{7}$.
Figure 24: Minimal-ABC trees with $n$ vertices, where $n\equiv 2\pmod{7}$.
Figure 25: Minimal-ABC trees with $n$ vertices, where $n\equiv 3\pmod{7}$.
Figure 26: Minimal-ABC trees with $n$ vertices, where $n\equiv 3\pmod{7}$.
Figure 27: Minimal-ABC trees with $n$ vertices, where $n\equiv 4\pmod{7}$.
Figure 28: Minimal-ABC trees with $n$ vertices, where $n\equiv 4\pmod{7}$.
Figure 29: Minimal-ABC trees with $n$ vertices, where $n\equiv 5\pmod{7}$.
Figure 30: Minimal-ABC trees with $n$ vertices, where $n\equiv 5\pmod{7}$.
Figure 31: Minimal-ABC trees with $n$ vertices, where $n\equiv 6\pmod{7}$.
Figure 32: Minimal-ABC trees with $n$ vertices, where $n\equiv 6\pmod{7}$.