The structure of graphs with given number of blocks and the maximum Wiener index

Abstract

The Wiener index (the distance) of a connected graph is the sum of distances between all pairs of vertices. In this paper, we study the maximum possible value of this invariant among graphs on n vertices with fixed number of blocks p. It is known that among graphs on n vertices that have just one block, the n-cycle has the largest Wiener index. And the n-path, which has $n-1$ blocks, has the maximum Wiener index in the class of graphs on n vertices. We show that among all graphs on n vertices which have $p\ge 2$ blocks, the maximum Wiener index is attained by a graph composed of two cycles joined by a path (here we admit that one or both cycles can be replaced by a single edge, as in the case $p=n-1$ for example).

1 Introduction

Let G be a simple graph. By V(G) and E(G) we denote the vertex set and the edge set of G, respectively. Let u and v be two vertices of G. The length of a shortest $u{-}v$ path is denoted by $d_G(u,v)$, or simply by d(u, v) if no confusion is likely, and is called the distance from u to v in G. The Wiener index is defined as the sum of the distances between all (unordered) pairs of vertices of G,

$$\begin{aligned} W(G)=\sum _{\{u,v\}\subseteq V(G)} d(u,v). \end{aligned}$$

The transmission of a vertex v is the sum of the distances from v to other vertices of G, i.e., $w_G(v)=\sum _{u\in V(G)} d_G(u,v)$. Then the Wiener index of G equals $\frac{1}{2}\sum _{u\in G} w_G (u)$.

The Wiener index was introduced by Wiener (1947), thus it is one of the oldest topological descriptors. At first it was used for predicting the boiling points of paraffins, later some other applications of the Wiener index were revealed. Many years later it was studied also from a purely graph-theoretical point of view. But mathematicians studied the Wiener index under different names, such as the gross status (Harary 1959), the distance of a graph (Entringer et al. 1976) and the transmission (Šoltés 1991). More details can be found in some of the many surveys, see e.g. Dobrynin et al. (2001), Knor and Škrekovski (2014), Knor et al. (2016) and Xu et al. (2014).

Let G be a connected graph. A vertex v is a cut-vertex if we obtain a disconnected graph after removing v and its adjacent edges from G. G is 2-connected if for every two vertices, say u and v, there is a cycle containing both u and v in G. A block is a maximal subgraph of G which does not have cut-vertices. Observe that a block is either an edge or a 2-connected subgraph of G. By connected union of blocks we mean a connected subgraph of G which is a union of several (at least one) blocks.

If G is a connected graph and v is a cut-vertex that partitions G into subgraphs $G_1$ and $G_2$, i.e., $G=G_1\cup G_2$ and $G_1\cap G_2 = \{v\}$, then we write $G=G_1\circ _{v}G_2$, or simply $G=G_1\circ G_2$. By $C_n$, $P_n$ and $K_n$ we denote a cycle, path and a complete graph, respectively, on n vertices. Our main result is the following statement.

Theorem 1.1

Let n and p be numbers such that $n>p>1$. Among all graphs on n vertices with p blocks, the maximum Wiener index is attained by the graph $H_a\circ _u P_{p-1}\circ _v H'_b$, where $|V(H_a)|=a$, $|V(H'_b)|=b$, $a,b\ge 2$, $a+b+p=n+3$, $H_a$ ($H'_b$) is a complete graph if $a=2$ (if $b=2$) or a cycle otherwise, and u and v are distinct endvertices of $P_{p-1}$.

Hence, if $p=n-1$ then the extremal graph is $P_n$, otherwise it is $C_a\circ _u P_p$ or $C_a\circ _u P_{p-1}\circ _v C_b$. The proof of Theorem 1.1 is rather technical. Therefore, the exact values of a and b will be determined in a forthcoming paper (Bessy et al. 2019). Let $W_n(p)$ be the maximum Wiener index of a graph which has n vertices and p blocks. In Bessy et al. (2019) we study $W_n(p)$ and we determine its minimum values.

Now, we introduce notations and definitions which we use throughout the paper. If $G,G_0,G_1,\dots$ are graphs, we denote by $n,n_0,n_1,\dots$, respectively, their numbers of vertices. For $v\in V(G)$, by $e_G(v)$ we denote the eccentricity of v in G, i.e., the maximal distance from v in G.

A graph is non-separable if it is connected and has no cut-vertices (i.e. either it is 2-connected or it is $K_2$). A block of G is a maximal non-separable subgraph of G. Two blocks sharing a common vertex are said to be adjacent. We refer to Bondy and Murty (2008) concerning the structure of blocks in a connected graph. In particular, it is known that the bipartite graph built on the set of blocks of G and the set of cut-vertices of G by linking a block to the cut-vertices it contains, is a tree. This tree is called the blocks-tree of G.

Let H be a subgraph of G, such that H is a connected union of several (at least one) blocks of G. An attachment vertex of H is a vertex of H which has a neighbour in $G{\setminus } H$. The subgraph H is terminal if H contains exactly one attachment vertex. It is traversal if it contains exactly two attachment vertices.

Let G be a connected graph on n vertices. The distance vector of a vertex v is the $e_G(v)$-dimensional vector ${{\varvec{d}}}_G(v)$ given by ${{\varvec{d}}}_G(v)_i=|\{x\in G\,:\ d_G(v,x)=i\}|$. If ${{\varvec{v}}}$ is a vector with coordinates ${{\varvec{v}}}_i$, then $\langle {{\varvec{v}}}\rangle$ is the value $\sum _{i} i {{\varvec{v}}}_i$. Observe that $\langle {{\varvec{d}}}_G(v) \rangle =w_G(v)$.

Now we define $\mathbf{2}_n$. If n is even, the vector $\mathbf{2}_n$ has dimension n / 2 and contains the value 2 in each coordinate except for the last one which is 1. If n is odd, $\mathbf{2}_n$ has dimension $(n-1)/2$ and each of its coordinates has value 2. For example $\mathbf{2}_7=(2,2,2)$ and $\mathbf{2}_6=(2,2,1)$. Observe that the vectors ${{\varvec{d}}}_{C_n}(x)$ and $\mathbf{2}_n$ are the same for every vertex x of the cycle $C_n$. Hence we obtain $w_{C_n}(x)=\frac{n^2}{4}$ if n is even and $w_{C_n}(x)=\frac{n^2-1}{4}$ if n is odd. Also observe that if G is a 2-connected graph, then the distance vector of every vertex v of G satisfies ${{\varvec{d}}}_G(v)_i\ge 2$ for every $i<e_G(v)$, and so $w_G(v)\le \langle \mathbf{2}_n\rangle$. Moreover, if G is different from a cycle then it has a vertex u, such that ${{\varvec{d}}}_G(u)_1\ge 3$, which means that $w_G(u)<\langle \mathbf{2}_n\rangle$. So we get the following classical result.

Proposition 1.2

Let G be a 2-connected graph on n vertices and let $v\in V(G)$. Then

$$\begin{aligned} w_G(v)\le {\left\{ \begin{array}{ll} \frac{n^2}{4} &{} \quad \text{ if } \text{ n } \text{ is } \text{ even; }\\ \frac{n^2-1}{4} &{} \quad \text{ if } \text{ n } \text{ is } \text{ odd. } \end{array}\right. } \end{aligned}$$

Moreover, if G is $C_n$ then equality holds for every vertex $v\in V(C_n)$. Further, the cycle $C_n$ is the unique graph which has the maximal Wiener index over the class of 2-connected graphs on n vertices, and

$$\begin{aligned} W(C_n)= {\left\{ \begin{array}{ll} \frac{n^3}{8} &{} \quad \text{ if } \text{ n } \text{ is } \text{ even; }\\ \frac{n^3-n}{8} &{} \quad \text{ if } \text{ n } \text{ is } \text{ odd. } \end{array}\right. } \end{aligned}$$

We use also the following obvious statement.

Proposition 1.3

Let v be an endvertex of $P_n$. Then

$$\begin{aligned} w_{P_n}(v)=\left( {\begin{array}{c}n\\ 2\end{array}}\right) \qquad \text{ and }\qquad W(P_n)=\left( {\begin{array}{c}n+1\\ 3\end{array}}\right) . \end{aligned}$$

2 Proof of Theorem 1.1

In this section we prove Theorem 1.1 using a couple of auxiliary results. The first two propositions will be useful to calculate Wiener index of a graph composed of two or more subgraphs joined by cut-vertices. The proofs are straightforward, so we omit them. Recall that the number of vertices of $G_i$ is denoted by $n_i$.

Proposition 2.1

Let $G=G_1\circ _vG_2$. We have

$$\begin{aligned} W(G) = W(G_1) + W(G_2) + w_{G_1}(v)\cdot (n_2-1) + w_{G_2}(v)\cdot (n_1-1). \end{aligned}$$

Observe that the subgraphs $G_1$ and $G_2$ in the previous proposition do not need to be blocks. In fact, each of these graphs is either a block or a connected union of blocks of G. Using an inductive argument we can get the following generalization of Proposition 2.1.

Proposition 2.2

Let $G_1,G_2,\dots ,G_{\ell }$ be blocks or connected unions of blocks of G, such that $E(G_1),E(G_2),\dots ,E(G_{\ell })$ is an edge decomposition of E(G). Denote by $v_{i,j}$ the attachment vertex of $G_i$ which separates $G_i$ from $G_j$. Then

$$\begin{aligned} W(G)&=\sum _{i=1}^{\ell } W(G_i)+\sum _{1\le i<j\le \ell } \left( w_{G_i}(v_{i,j})\cdot (n_j{-}1)\right. \,\nonumber \\&\quad \left. + w_{G_j}(v_{j,i})\cdot (n_i{-}1) +d_G(v_{i,j},v_{j,i})\cdot (n_i{-}1)\cdot (n_j{-}1)\right) . \end{aligned}$$

(1)

Observe that the last term in the second sum of Proposition 2.2 is 0 if $G_i$ and $G_j$ are adjacent blocks. We remark that Proposition 2.2 holds even in the case when some of the $G_i$ are “trivial”, i.e., if they consist of a single vertex, since then all the terms containing $W(G_i)$, $(n_i-1)$, or $w_{G_i}(v_{i,j})$ are zeros.

Now we show that terminal blocks are cycles or edges in extremal graphs.

Lemma 2.3

Let B be a terminal block of G such that B is not a cycle and $|V(B)|\ge 3$. Let $G'$ be the graph obtained from G by replacing B by a cycle on |V(B)| vertices. Then $W(G')>W(G)$.

Proof

Denote by v the attachment vertex of B in G. Further, denote by $G_1$ the block B and denote by $G_2$ the subgraph of G such that $G_1\circ _v G_2=G$. By Proposition 2.1 we have (recall that $n_i=|V(G_i)|$)

$$\begin{aligned} W(G)&=W(B)+W(G_2)+w_B(v)\cdot (n_2-1)+w_{G_2}(v)\cdot (n_1-1)\\ W(G')&=W(C_{n_1})+W(G_2)+w_{C_{n_1}}(v)\cdot (n_2-1)+w_{G_2}(v)\cdot (n_1-1) \end{aligned}$$

and so

$$\begin{aligned} W(G')-W(G)=W(C_{n_1})-W(B)+\big (w_{C_{n_1}}(v)-w_B(v)\big )\cdot (n_2-1). \end{aligned}$$

Since B is not a cycle, we have $W(C_{n_1})-W(B)>0$ by Proposition 1.2. Moreover, by Proposition 1.2 we have also $w_{C_{n_1}}(v)=\langle \mathbf{2}_{n_1}\rangle \ge \langle {{\varvec{d}}}_B(v)\rangle =w_B(v)$. Hence we obtain $W(G')>W(G)$. $\square$

In a cycle $C_n$, two vertices u and v are opposite (or antipodal) if they satisfy $d_{C_n}(u,v)=\max \{d_{C_n}(x,y):x,y\in C_n\}=\lfloor \frac{n}{2}\rfloor$. In $K_2$, two vertices are opposite if they are different.

Lemma 2.4

Let B be a traversal block of G with $|V(B)|=n_0\ge 3$, and let $v_1$ and $v_2$ be the two attachment vertices of B. Let $C_{n_0}$ be a cycle in which $v_1$ and $v_2$ are opposite and let $G'$ be obtained from G by replacing B by $C_{n_0}$. If B is not a cycle or if B is a cycle and $v_1$ and $v_2$ are not opposite in B, then $W(G')>W(G)$.

Proof

Denote by $G_1$ and $G_2$ the subgraphs of G attached to B at $v_1$ and $v_2$, respectively, such that $E(G)=E(G_1)\cup E(B)\cup E(G_2)$. By Proposition 2.2 we have

$$\begin{aligned} W(G')-W(G)&=\big (W(C_{n_0})-W(B)\big ) +\big (w_{C_{n_0}}(v_1)-w_B(v_1)\big )\cdot (n_1-1)\\&\quad +\,\big (w_{C_{n_0}}(v_2)-w_B(v_2)\big )\cdot (n_2-1)\\&\quad +\,\big (d_{C_{n_0}}(v_1,v_2)-d_B(v_1,v_2)\big )\cdot (n_1-1)\cdot (n_2-1). \end{aligned}$$

By Proposition 1.2 we have $W(C_{n_0})-W(B)\ge 0$ and equality holds if and only if B is a cycle. By Proposition 1.2 we have also $w_{C_{n_0}}(v_1)-w_B(v_1)\ge 0$ and $w_{C_{n_0}}(v_2)-w_B(v_2)\ge 0$. Finally, since every vertex v in a 2-connected graph H satisfies $e_H(v)\le \big \lfloor \frac{|V(H)|}{2}\big \rfloor$ (recall that for every $i<e_H(v)$ we have ${{\varvec{d}}}_H(v)_i\ge 2$), we have $d_B(v_1,v_2)\le \lfloor \frac{n_0}{2}\rfloor =d_{C_{n_0}}(v_1,v_2)$. Hence, all the terms on the right hand side of the equality for $W(G')-W(G)$ are nonnegative and they are all zeros if and only if $B=C_{n_0}$ and $d_B(v_1,v_2)=\lfloor \frac{n_0}{2}\rfloor$. $\square$

By Lemma 2.3, a terminal block is either $K_2$ or a cycle. Next lemma gives a condition for extremal graphs.

Lemma 2.5

Let G be a graph with at least 3 blocks and let $G_1$ and $G_2$ be two terminal blocks of G with attachment vertices $v_1$ and $v_2$, respectively. Let $u_i$ be a vertex opposite to $v_i$ in $G_i$ for $i\in \{1,2\}$. Denote by $G'$ (resp. $G''$) a graph obtained from G by removing the block $G_1$ (resp. $G_2$) and attaching it to $u_2$ (resp. $u_1$). Suppose that $W(G)\ge W(G')$ and $W(G)\ge W(G'')$. Then $d_{G}(u_1,u_2)\ge \frac{n-1}{2}$.

Proof

Let $G_0$ be the graph obtained from G by removing the blocks $G_1$ and $G_2$, such that $E(G)=E(G_1)\cup E(G_0)\cup E(G_2)$. Observe that $G_0$ does not need to be a single block, but it is a connected union of blocks. Anyway, $G=G_1\circ _{v_1}G_0\circ _{v_2}G_2$, $G'=G_0\circ _{v_2}G_2\circ _{u_2}G_1$ and $G''=G_2\circ _{u_1}G_1\circ _{v_1}G_0$. By Proposition 2.2 we have

$$\begin{aligned} W(G)-W(G')=&\,\big (w_{G_2}(v_2)-w_{G_2}(u_2)\big )\cdot (n_1-1) +\big (w_{G_0}(v_1)-w_{G_0}(v_2)\big )\cdot (n_1-1)\\&+d_{G_0}(v_1,v_2)\cdot (n_1-1)\cdot (n_2-1) {-}d_{G_2}(v_2,u_2)\cdot (n_1-1)\cdot (n_0-1) \end{aligned}$$

where $w_{G_2}(v_2)=w_{G_2}(u_2)$. Since $W(G)\ge W(G')$ and $n_1\ge 2$, we get

$$\begin{aligned} w_{G_0}(v_1)-w_{G_0}(v_2) +d_{G_0}(v_1,v_2)\cdot (n_2-1) -d_{G_2}(v_2,u_2)\cdot (n_0-1)\ge 0. \end{aligned}$$

Analogously, from $W(G)-W(G'')\ge 0$ we get

$$\begin{aligned} w_{G_0}(v_2)-w_{G_0}(v_1) +d_{G_0}(v_1,v_2)\cdot (n_1-1) -d_{G_1}(v_1,u_1)\cdot (n_0-1)\ge 0 \end{aligned}$$

and summing the last two inequalities we obtain

$$\begin{aligned} d_G(v_1,v_2)\cdot (n_1+n_2-2) -\big (d_{G_2}(v_2,u_2)+d_{G_1}(v_1,u_1)\big )\cdot (n_0-1)\ge 0. \end{aligned}$$

Now since $v_i$ and $u_i$ are opposite in $G_i$ for $i\in \{1, 2\}$, we have

$$\begin{aligned} d_G(v_1,u_1)+d_G(v_2,u_2) =\Big \lfloor \frac{n_1}{2}\Big \rfloor +\Big \lfloor \frac{n_2}{2}\Big \rfloor \ge \frac{n_1-1}{2}+\frac{n_2-1}{2}=\frac{n_1+n_2-2}{2}. \end{aligned}$$

Thus we obtain $d_G(v_1,v_2)\ge (n_0-1)/2$ and consequently

$$\begin{aligned} d_G(u_1,u_2)&=d_G(u_1,v_1)+d_G(v_1,v_2)+d_G(v_2,u_2)\\&\ge \frac{n_1-1}{2}+\frac{n_0-1}{2}+\frac{n_2-1}{2} =\frac{n-1}{2} \end{aligned}$$

since $n=n_1+n_0+n_2-2$. $\square$

Let $n=tk+1$. Take k paths of length t (i.e. on $t+1$ vertices), on each path choose one endvertex, and identify these endvertices. We denote by $R^k_n$ the resulting graph. Observe that $R^k_n$ has n vertices and is homeomorphic to the star $K_{1,k}$. In Knor and Škrekovski (2019, Theorem 3) we have the following statement.

Theorem 2.6

Let G be a connected graph on n vertices. Then for every k-tuple $u_1,u_2,\dots ,u_k$ of its vertices, $3\le k<n$, there are two, say $u_i$ and $u_j$ where $1\le i<j\le k$, such that

$$\begin{aligned} d_G(u_i,u_j)\le \frac{2n-2}{k}. \end{aligned}$$

Moreover, if

$$\begin{aligned} \min _{1\le i<j\le k} d_G(u_i,u_j)=\frac{2n-2}{k} \end{aligned}$$

then $n\equiv 1\pmod k$, the graph is $R^k_n$ and $u_1,u_2,\dots ,u_k$ are the endvertices of $R^k_n$.

Using Theorem 2.6 and Lemma 2.5 we prove the following statement.

Lemma 2.7

Let $n>p$. Let G be a graph on n vertices with p blocks which has the maximum Wiener index. Then G has at most three terminal blocks.

Proof

By way of contradiction, suppose that G has at least four terminal blocks, say $B_1$, $B_2$, $B_3$ and $B_4$. By Lemma 2.3 we know that each of these blocks is either a cycle or $K_2$. Let $v_i$ be the unique attachment vertex of $B_i$ and let $u_i$ be a vertex opposite to $v_i$ in $B_i$, $1\le i\le 4$. Denote

$$\begin{aligned} d=\min _{1\le i<j\le 4} d_G(u_i,u_j) \end{aligned}$$

and assume that this minimum is attained by the pair $u_1,u_2$. By Theorem 2.6 we know that $d\le \frac{n-1}{2}$. We distinguish two cases.

Case 1:$d<\frac{n-1}{2}$. Denote $G_1=B_1$ and $G_2=B_2$. Now construct $G'$ and $G''$ by reattaching of $G_1$ and $G_2$ as in Lemma 2.5. Since $d_G(u_1,u_2)=d<\frac{n-1}{2}$, either $W(G)<W(G')$ or $W(G)<W(G'')$. Since all G, $G'$ and $G''$ have n vertices and p blocks, we get a contradiction.

Case 2:$d=\frac{n-1}{2}$. By Theorem 2.6, in this case G is $R^4_n$, and so $p=n-1$. It is well-known that among trees on n vertices, $P_n$ is the unique graph with the maximum Wiener index. So $W(P_n)>W(R^4_n)$, a contradiction. $\square$

Now we prove some results useful for sequences of traversal blocks. The following theorem was proved in Gutman et al. (2014).

Theorem 2.8

For every $n\notin \{7,9\}$, the graph $C_{n-2}\circ C_3$ has the maximal Wiener index among the graphs from the family $\{C_{n-r+1}\circ C_r : r\ge 3,\ n-r\ge 2\}$. Moreover for $n=7$ and $n=9$, it holds $W(C_4\circ C_4)> W(C_5\circ C_3)$ and $W(C_6\circ C_4)> W(C_7\circ C_3)> W(C_5\circ C_5)$.

We extend Lemma 2.8 to blocks of size 2.

Lemma 2.9

For every $n\ge 4$, among the graphs on n vertices with exactly two blocks, the maximal Wiener index is attained by $C_{n-1}\circ K_2$.

Proof

For $n=4$ the graph $C_3\circ K_2$ is the unique graph with two blocks, thus it has the largest Wiener index. For $n\ge 5$, $n\notin \{7,9\}$, it is enough to show that $W(C_{n-1}\circ K_2)>W(C_{n-2}\circ C_3)$, by Theorem 2.8.

Using Proposition 2.1 we get the Wiener index of $G=C_{n-1}\circ _v K_2$.

$$\begin{aligned} W(G)&=W(C_{n-1})+W(K_2)+w_{C_{n-1}}(v)\cdot 1+w_{K_2}(v)\cdot (n-2)\\&=\tfrac{n-1}{2} \langle \mathbf{2}_{n-1}\rangle +1 +\langle \mathbf{2}_{n-1}\rangle \cdot 1+1\cdot (n-2). \end{aligned}$$

In $G'=C_{n-2}\circ _u C_{3}$ we can also use Proposition 2.1 to evaluate the Wiener index.

$$\begin{aligned} W(G')&=W(C_{n-2})+W(C_3)+w_{C_{n-2}}(u)\cdot 2+w_{C_3}(u)\cdot (n-3)\\&=\tfrac{n-2}{2} \langle \mathbf{2}_{n-2}\rangle +3 +\langle \mathbf{2}_{n-2}\rangle \cdot 2+2\cdot (n-3). \end{aligned}$$

Hence, using Proposition 1.2 we get

$$\begin{aligned} W(G)-W(G')&=\tfrac{n+1}{2}\langle \mathbf{2}_{n-1}\rangle -\tfrac{n+2}{2}\langle \mathbf{2}_{n-2}\rangle -n+2\\&= {\left\{ \begin{array}{ll} \frac{(n-2)(n-4)}{8} &{}\quad \text{ if } \text{ n } \text{ is } \text{ even; }\\ \frac{(n-1)(n-3)}{8}+1 &{}\quad \text{ if } \text{ n } \text{ is } \text{ odd. } \end{array}\right. } \end{aligned}$$

Since $n\ge 5$, in both cases we get $W(G)>W(G')$.

By Theorem 2.8, for $n=7$ and $n=9$ it suffices to show that $W(C_{n-1}\circ K_2)>W(C_{n-3}\circ C_4)$. Direct computation gives $W(C_4\circ C_4)=40$, $W(C_6\circ K_2)=42$, $W(C_6\circ C_4)=82$ and $W(C_8\circ K_2)=88$, which completes the proof. $\square$

Using Lemma 2.9 we prove the following statement. Here we allow the smaller end-block to be just a single vertex, i.e. $|V(G_0)|=1$, see below. For technical reasons, we denote $K_2$ by $C_2$. Observe that if $u\in V(K_2)$ then $w_{K_2}(u)=1=\frac{|V(K_2)|^2}{4}$ and $W(K_2)=1=\frac{|V(K_2)|^3}{8}$. Hence, this notation is in a correspondence with Proposition 1.2.

Lemma 2.10

Let $G=G_0\circ _{v_1} G_1\circ _v G_2\circ _{v_2} G_3$, where $G_1$ and $G_2$ are $C_{n_1}$ and $C_{n_2}$, respectively, $v_1$ and v are antipodal in $G_1$, and v and $v_2$ are antipodal in $G_2$. Let $k=n_1+n_2-1$, $n_0\le n_3$ and $n_3\ge 2$. Then G has maximal Wiener index if and only if

• 1. $n_1=k-1$ and $n_2=2$, or

• 2. $n_1=2$, $n_2=k-1$ and $n_0=n_3$.

Proof

Let $G'=G_0\circ _{v_1} C_{n_1+n_2-2}\circ _u C_2\circ _{v_2} G_3$, where u is antipodal to $v_1$ in $C_{n_1+n_2-2}$ and u is antipodal to (i.e., different from) $v_2$ in $C_2$ ($=K_2$). Denote $H=C_{n_1}\circ C_{n_2}$ and $H'=C_{n_1+n_2-2}\circ C_2$. By Proposition 2.2 we have

$$\begin{aligned} W(G')-W(G)&=\big (W(H')-W(H)\big )+ \big (w_{H'}(v_1)-w_H(v_1)\big )\cdot (n_0-1)\\&\quad +\big (w_{H'}(v_2)-w_H(v_2)\big )\cdot (n_3-1)\\&\quad +\big (d_{H'}(v_1,v_2)-d_H(v_1,v_2)\big )\cdot (n_0-1)\cdot (n_3-1). \end{aligned}$$

By Lemma 2.9 we have $W(H')-W(H)\ge 0$ and equality holds if and only if $H=H'$ (i.e., if $n_1=2$ or if $n_2=2$). Further, $d_{H'}(v_1,v_2)=\lfloor \frac{n_1+n_2-2}{2}\rfloor +\lfloor \frac{2}{2}\rfloor \ge \lfloor \frac{n_1}{2}\rfloor +\lfloor \frac{n_2}{2}\rfloor =d_H(v_1,v_2)$, and so the last term is nonnegative as well. Let

$$\begin{aligned} \Delta =\big (w_{H'}(v_1)-w_H(v_1)\big )\cdot (n_0-1) +\big (w_{H'}(v_2)-w_H(v_2)\big )\cdot (n_3-1). \end{aligned}$$

We show that $\Delta \ge 0$.

If k is even, we have $w_{H'}(v_1)=\langle {{\varvec{d}}}_{H'}(v_1)\rangle =\langle (2,2,\ldots ,2,1)\rangle$, and $w_{H'}(v_2)=\langle {{\varvec{d}}}_{H'}(v_2)\rangle =\langle (1,2,2,\ldots ,2)\rangle$, where these vectors both have dimension k / 2. If k is odd, we get $w_{H'}(v_1)=\langle {{\varvec{d}}}_{H'}(v_1)\rangle =\langle (2,2,\ldots ,2,1,1)\rangle$, and $w_{H'}(v_2)=\langle {{\varvec{d}}}_{H'}(v_2)\rangle =\langle (1,2,2,\ldots ,2,1)\rangle$, where both these vectors have dimension $(k+1)/2$. To compute $w_{H}(v_1)$, $w_{H}(v_2)$ and $\Delta$ we distinguish four cases according to the parity of k and $n_1$.

Case 1:Bothkand$n_1$are even. Then $n_2$ is odd and $w_H(v_1)=\langle {{\varvec{d}}}_H(v_1)\rangle =\langle (2,\ldots ,2,1,2,\ldots ,2)\rangle$, where ${{\varvec{d}}}_H(v_1)$ is a vector of dimension k / 2, such that the $\frac{n_1}{2}$-th coordinate is 1, i.e., ${{\varvec{d}}}_H(v_1)_{n_1/2}=1$, and $w_H(v_2)=\langle {{\varvec{d}}}_H(v_2)\rangle =\langle (2,\ldots ,2,1)\rangle$, where ${{\varvec{d}}}_H(v_2)$ is also a vector of dimension k / 2. So

$$\begin{aligned} \Delta = \big (\tfrac{n_1}{2}-\tfrac{k}{2}\big )(n_0-1)+\big (-1+\tfrac{k}{2}\big )(n_3-1) =\tfrac{n_1-k}{2}\cdot (n_0-1)+\tfrac{k-2}{2}\cdot (n_3-1). \end{aligned}$$

This is nonnegative since $n_0\le n_3$ and $k-2\ge k-n_1$. Moreover, $\Delta =0$ if and only if $n_0=n_3$ and $n_1=2$.

Case 2:kis even and$n_1$is odd. Then $n_2$ is even and $w_H(v_1)=\langle {{\varvec{d}}}_H(v_1)\rangle =\langle (2,\ldots ,2,1)\rangle$, where ${{\varvec{d}}}_H(v_1)$ is a vector of dimension k / 2, and $w_H(v_2)=\langle {{\varvec{d}}}_H(v_2)\rangle =\langle (2,\ldots ,2,1,2,\ldots ,2)\rangle$, where ${{\varvec{d}}}_H(v_2)$ is also a vector of dimension k / 2, in which ${{\varvec{d}}}_H(v_2)_{n_2/2}=1$. So

$$\begin{aligned} \Delta = 0\cdot (n_0-1)+\big (-1+\tfrac{n_2}{2}\big )(n_3-1) =\tfrac{n_2-2}{2}\cdot (n_3-1). \end{aligned}$$

This is nonnegative since $n_2-2\ge 0$. Moreover, $\Delta =0$ if and only if $n_2=2$, since $n_3\ge 2$.

Case 3:kis odd and$n_1$is even. Then $n_2$ is even and $w_H(v_1)=\langle {{\varvec{d}}}_H(v_1)\rangle =\langle (2,\ldots ,2,1,2,\ldots ,2,1)\rangle$, where ${{\varvec{d}}}_H(v_1)$ is a vector of dimension $(k+1)/2$, such that ${{\varvec{d}}}_H(v_1)_{n_1/2}=1$ and $w_H(v_2)=\langle {{\varvec{d}}}_H(v_2)\rangle =\langle (2,\ldots ,2,1,2,\ldots ,2,1)\rangle$, where ${{\varvec{d}}}_H(v_2)$ is also a vector of dimension $(k+1)/2$, in which ${{\varvec{d}}}_H(v_2)_{n_2/2}=1$. Since $k-1-n_1=n_2-2$, we have

$$\begin{aligned} \Delta =\big (\tfrac{n_1}{2}-\tfrac{k-1}{2}\big )(n_0-1)+\big (-1+\tfrac{n_2}{2}\big )(n_3-1) =\tfrac{n_2-2}{2}\cdot (n_3-n_0). \end{aligned}$$

This is nonnegative since $n_2\ge 2$ and $n_3\ge n_0$. Moreover $\Delta =0$ if and only if $n_2=2$ or $n_3=n_0$.

Case 4:Bothkand$n_1$are odd. Then $n_2$ is odd and $w_H(v_1)=\langle {{\varvec{d}}}_H(v_1)\rangle =w_H(v_2)=\langle {{\varvec{d}}}_H(v_2)\rangle =\langle (2,\ldots ,2)\rangle$, where both these vectors are of dimension $(k-1)/2$. So

$$\begin{aligned} \Delta {=}\big (\tfrac{-(k-1)}{2}{+}\tfrac{k+1}{2}\big )(n_0-1)+\big (-1{+}\tfrac{k+1}{2}\big )(n_3-1) {=}(n_0-1){+}\tfrac{k-1}{2}\cdot (n_3-1){>}0. \end{aligned}$$

Now combining these cases with Lemma 2.9, which states that $W(H')\ge W(H)$ and the equality holds if and only if $H=H'$ (see Case 3), yields the result. $\square$

In the following lemma we consider chains of traversal blocks.

Lemma 2.11

Let $n>p$. Let G be a graph on n vertices with p blocks which has the maximum Wiener index. Moreover, suppose that $G=H_0\circ _{v_1}H_1\circ _{v_2}\dots \circ _{v_{\ell -1}}H_{\ell -1}\circ _{v_{\ell }}H_{\ell }$, where $\ell \ge 2$, all $H_0,\dots ,H_{\ell -1}$ are blocks and $H_{\ell }$ is a connected union of blocks. Then $|V(H_1)|=\dots =|V(H_{\ell -2})|=2$. Moreover, if $H_{\ell }$ is a terminal block or if $|V(H_0\circ \dots \circ H_{\ell -2})|\le |V(H_{\ell })|$, then $|V(H_{\ell -1})|=2$ as well.

Proof

Since $H_0$ is a terminal block and $H_1,\dots ,H_{\ell -1}$ are traversal, each of these blocks is either a cycle or $K_2$, by Lemmas 2.3 and 2.4. Moreover, by Lemma 2.4 we know that the attachment vertices $v_i$ and $v_{i+1}$ are opposite on $H_i$, $1\le i\le \ell -1$.

Suppose that among $H_1,\dots ,H_{\ell -2}$ there is a cycle on at least 3 vertices, say $H_i$. By Lemma 2.10 both $H_{i-1}$ and $H_{i+1}$ must be isomorphic to $K_2$. Denote $t_1=|V(H_0\circ \dots \circ H_{i-1})|$ and $t_2=|V(H_{i+1}\circ \dots \circ H_{\ell })|$. We distinguish two cases.

Case 1:$t_1\le t_2$. Denote $G_0=H_0\circ \dots \circ H_{i-2}$, $G_1=H_{i-1}$, $G_2=H_i$ and $G_3=H_{i+1}\circ \dots \circ H_{\ell }$. (Observe that if $i=1$ then $G_0$ is trivial consisting of a single vertex.) Then $n_0=t_1-1<t_2=n_3$. Hence, by Lemma 2.10 we have $n_2=2$, a contradiction.

Case 2:$t_1>t_2$. Denote $G_0=H_{\ell }\circ \dots \circ H_{i+2}$, $G_1=H_{i+1}$, $G_2=H_i$ and $G_3=H_{i-1}\circ \dots \circ H_0$. Then $n_0=t_2-1<t_1=n_3$. Hence, by Lemma 2.10 we have $n_2=2$, a contradiction.

Now we consider $H_{\ell -1}$. If $|V(H_0\circ \dots \circ H_{\ell -2})|\le |V(H_{\ell })|$, then denote $G_0=H_0\circ \dots \circ H_{\ell -3}$, $G_1=H_{\ell -2}$, $G_2=H_{\ell -1}$ and $G_3=H_{\ell }$. (Observe that if $\ell =2$ then $G_0$ is trivial.) Since $n_0<n_3$, by Lemma 2.10 we have $n_2=2$.

If $H_{\ell }$ is a terminal block and $\ell \ge 3$, then relabelling the blocks (reversing their order) we can prove that $|V(H_{\ell -1})|=2$.

Finally, if $H_{\ell }$ is a terminal block, $\ell =2$ and $|V(H_0)|>|V(H_2)|$, then let $G_0$ be trivial, $G_1=H_2$, $G_2=H_1$ and $G_3=H_0$. Then $n_0<n_3$, and so $n_2=2$ by Lemma 2.10. $\square$

By $\Theta _{a,b,c}$ we denote a graph consisting of two vertices, which are connected by three internally vertex-disjoint paths of lengths a, b and c. Observe that $\Theta _{a,b,c}$ has $a+b+c-1$ vertices. In Knor and Škrekovski (2019, Lemma 5) we have the following statement.

Theorem 2.12

Let G be a 2-connected graph on n vertices, having three vertices $v_1$, $v_2$ and $v_3$ such that

$$\begin{aligned} D=\sum _{1\le i<j\le 3}d_G(v_i,v_j) \end{aligned}$$

is maximum possible. Then $D\le n+1$ and the equality is attained only if G is $\Theta _{a,b,c}$, where all a, b and c are even.

Observe that if n is even then $D<n+1$ by Theorem 2.12. Using this statement we prove the following lemma.

Lemma 2.13

Let $n>p$. Let G be a graph on n vertices with p blocks which has the maximum Wiener index. Then G has exactly two terminal blocks.

Proof

By Lemma 2.7, G has at most three terminal blocks. By way of contradiction, suppose that G has exactly three terminal blocks. Then its blocks-tree has one vertex of degree 3, three vertices of degree 1 corresponding to terminal blocks, and all the remaining vertices have degree 2. The vertex of degree 3 corresponds either to a block or to a cut-vertex. To simplify the reasoning, in the latter case we consider the cut-vertex as a trivial block.

Hence, G consists of a block $G_0$ with three vertices $v_1$, $v_2$ and $v_3$ in which there are attached connected unions of blocks $G_1$, $G_2$ and $G_3$, respectively (obviously, the vertices $v_1$, $v_2$ and $v_3$ are not necessarily disjoint). We assume that $n_1\ge n_2\ge n_3$. By Lemma 2.11, since $n_1\ge n_i$ for $i\in \{2, 3\}$, we have $G_i=C_{k_i}\circ _{u_i} P_{t_i}$, where $u_i$ is one endvertex of the path $P_{t_i}$ and $v_i$ is another one, and $k_i+t_i-1=n_i$. Observe that $G_1$ may consist of two cycles connected by a path, but we do not need to consider the structure of $G_1$. The structure of G is visualized on Fig. 1.

Fig. 1

Graphs G and $G'$ in the proof of Lemma 2.13

Now we construct $G'$ on n vertices with p blocks, so that $G'$ will have just two terminal blocks and $W(G')>W(G)$. First, if $n_0\ge 3$, then let $G'_0$ be a cycle on $n_0$ vertices in which $v_1$ is opposite to z. If $n_0\le 2$, then $G_0$ is a cut vertex since the case $G_0=K_2$ is impossible. So set $G_0'=G_0$ and $z=v_1$ if $n_0=1$. Let z and y be the two endvertices of $P_{t_2+t_3}$. Then $G'=C_{k_2+k_3-2}\circ _y P_{t_2+t_3}\circ _z G'_0\circ _{v_1}G_1$, see Fig. 1. Observe that the graphs G and $G'$ have the same number of blocks and they have also the same number of vertices.

Since $G'$ is simpler than G, we calculate $W(G')$ exactly. However, for W(G) we use just an upper bound W. Below we show that $W(G')-W>0$. Since $W(G)\le W$, this implies that also $W(G')-W(G)>0$.

By Proposition 1.3, $w_{P_a}(x)=\frac{a^2-a}{2}$ if x is an endvertex of a path of length a. But if x is a vertex of $C_a$ then $w_{C_a}(x)=\frac{a^2}{4}$ if a is even and $W_{C_a}(x)=\frac{a^2-1}{4}$ if a is odd, see Proposition 1.2. Therefore, we distinguish two cases according to the parity of $k_2+k_3-2$. If $k_2+k_3-2$ is odd, then exactly one of $k_2$ and $k_3$ is odd as well. Since we do not use the inequality $n_2\ge n_3$ in the proof, without loss of generality we may assume that $k_2$ is even and $k_3$ is odd in this case. If $k_2+k_3-2$ is even, then either both $k_2$ and $k_3$ are even or both are odd. However, since it suffices to find an upper bound W on W(G) such that $W(G')-W>0$, we use the upper bounds $\frac{k_2^2}{4}$ and $\frac{k_3^2}{4}$ for $w_{C_{k_1}}(u_1)$ and $w_{C_{k_2}}(u_2)$, respectively, in this case.

Now we bound $W(G')-W(G)$ using Proposition 2.2. The graph G is composed of six parts $C_{k_2}$, $P_{t_2}$, $C_{k_3}$, $P_{t_3}$, $G_0$ and $G_1$, see Fig. 1. Therefore we have 6 terms in the first sum of (1), $2\left( {\begin{array}{c}6\\ 2\end{array}}\right)$ terms due to the first two products in the second sum of (1) and $\left( {\begin{array}{c}6\\ 2\end{array}}\right) -5$ terms due to the third product in the second sum of (1). This yields 46 terms due to G. The graph $G'$ is composed of four parts $C_{k_2+k_3-2}$, $P_{t_2+t_3}$, $G_0'$ and $G_1$, see Fig. 1. Therefore we have 19 terms due to $G'$ in (1). Since there are too many terms, we divide them into several groups and we show that the sum of terms in each group is nonnegative.

• 1. First consider the terms containing$w_{G_1}(v_1)$. These terms occur in the first two products of the second sum of (1). In W(G) these terms are $(k_2-1)w_{G_1}(v_1)$, $(t_2-1)w_{G_1}(v_1)$, $(k_3-1)w_{G_1}(v_1)$, $(t_3-1)w_{G_1}(v_1)$ and $(n_0-1)w_{G_1}(v_1)$. Observe that they sum to $(n-n_1)w_{G_1}(v_1)$. Since in $W(G')$ the three terms $(k_2+k_3-3)w_{G_1}(v_1)$, $(t_2+t_3-1)w_{G_1}(v_1)$ and $(n_0-1)w_{G_1}(v_1)$ containing $w_{G_1}(v_1)$ sum again to $(n-n_1)w_{G_1}(v_1)$, these terms contribute 0 to $W(G')-W(G)$.

• 2. Now consider the terms containing$w_{G_0}(v_1)$,$w_{G_0}(v_2)$,$w_{G_0}(v_3)$,$w_{G'_0}(v_1)$, and $w_{G'_0}(z)$. Since $w_{G'_0}(v_1)=w_{G'_0}(z)$, in $W(G')$ these terms sum to $(n-n_0)w_{G'_0}(v_1)$. By Proposition 1.2, we have $w_{G_0}(v_i)\le w_{G'_0}(v_1)$, $1\le i\le 3$. Hence, the upper bound for the contribution of considered terms to W(G) is also $(n-n_0)w_{G'_0}(v_1)$. Consequently, these terms contribute at least 0 to $W(G')-W(G)$.

• 3. Now consider the terms containing$(n_0-1)$which were not considered in the groups 1. and 2. above, together with the terms containing distances in$G_0$and$G'_0$. We start with the case when $k_2+k_3-2$ is even.

First consider the terms containing $(n_0-1)$. Their contribution to $W(G')-W(G)$ is at least [the fractions correspond to $w_H(x)$’s, while the non-fractions correspond to the last term in (1)].

$$\begin{aligned}&(n_0-1)\Big [\tfrac{(k_2+k_3-2)^2}{4}+\tfrac{(t_2+t_3)^2-(t_2+t_3)}{2} +(k_2+k_3-3)(t_2+t_3-1)\nonumber \\&\qquad -\tfrac{k_2^2}{4}-\tfrac{k_3^2}{4}-\tfrac{t_2^2-t_2}{2}-\tfrac{t_3^2-t_3}{2} -(k_2-1)(t_2-1)-(k_3-1)(t_3-1)\Big ]\nonumber \\&\quad =(n_0-1)\big [\tfrac{1}{2}(k_2-2)(k_3-2)+(k_2-2)t_3+(k_3-2)t_2+t_2t_3\big ]. \end{aligned}$$

(2)

Since $n_0\ge 1$, $k_2\ge 2$, $k_3\ge 2$, $t_2\ge 1$ and $t_3\ge 1$, the expression (2) is nonnegative.

Now consider the terms containing distances in $G_0$ and $G_0'$. In W(G) these terms sum to $(n_1-1)(n_2-1)d_{G_0}(v_1,v_2)$, $(n_1-1)(n_3-1)d_{G_0}(v_1,v_3)$ and $(n_2-1)(n_3-1)d_{G_0}(v_2,v_3)$. By Theorem 2.12 we have $d_{G_0}(v_1,v_2)+d_{G_0}(v_1,v_3)+d_{G_0}(v_2,v_3)\le n_0+1$. Since $n_1\ge n_2$ and $n_1\ge n_3$, we obtain the biggest contribution if $d_{G_0}(v_1,v_2)$ and $d_{G_0}(v_1,v_3)$ are maximum possible, namely $\lfloor \frac{n_0}{2}\rfloor$. Then $d_{G_0}(v_2,v_3)\le 2$. Hence, the contribution of these terms to W(G) is at most

$$\begin{aligned} \big \lfloor \tfrac{n_0}{2}\big \rfloor \big [(n_1-1)(n_2-1)+(n_1-1)(n_3-1)\big ] +2(n_2-1)(n_3-1), \end{aligned}$$

while the contribution of the terms containing $d_{G'_0}(v_1,z)$ to $W(G')$ is

$$\begin{aligned} d_{G'_0}(v_1,z)(n_1-1)(n_2+n_3-2) =\big \lfloor \tfrac{n_0}{2}\big \rfloor (n_1-1)(n_2+n_3-2). \end{aligned}$$

Consequently, the contribution of these terms to $W(G')-W(G)$ is at least

$$\begin{aligned} -2(n_2-1)(n_3-1)= -2\big [(k_2-2)(k_3-2)+(k_2-2)t_3+(k_3-2)t_2+t_2t_3\big ]. \end{aligned}$$

(3)

Our aim is to show that the sum of the right-hand sides of (2) and (3) is nonnegative. We consider five cases.

Case 1:$n_0\ge 5$. Since the expression in brackets containing $k_2$, $k_3$, $t_2$ and $t_3$ in (2) is nonnegative, it suffices to show nonnegativity of the sum of (2) and (3) for $n_0=5$. Since this sum is

$$\begin{aligned} 2(k_2-2)t_3+2(k_3-2)t_2+2t_2t_3>0, \end{aligned}$$

the contribution of selected terms is nonnegative in this case.

Case 2:$n_0=1$. In this case the considered distances in $G_0$ and $G'_0$ are 0 as well as $(n_0-1)$. Hence, the contribution of selected terms is 0 in this case.

Case 3:$n_0=2$. This case is impossible, since if $G_0=K_2$ then the vertex of degree 3 in the blocks-tree is a cut-vertex.

Case 4:$n_0=3$. In this case we have $d_{G_0}(v_i,v_j)=1$, $1\le i<j\le 3$, and also $d_{G'_0}(v_1,z)=1$. Hence, the contribution of the terms based on distances is

$$\begin{aligned} -1\big [(k_2-2)(k_3-2)+(k_2-2)t_3+(k_3-2)t_2+t_2t_3\big ] \end{aligned}$$

and the total contribution of considered terms is

$$\begin{aligned} (k_2-2)t_3+(k_3-2)t_2+t_2t_3>0. \end{aligned}$$

Case 5:$n_0=4$. By Theorem 2.12 we have $d_{G_0}(v_1,v_2)+d_{G_0}(v_1,v_3)+d_{G_0}(v_2,v_3)\le n_0 = 4$. In this case, the sum of the terms containing distances in $G_0$ and $G'_0$ is non-negative. So the considered terms contribute to $W(G')-W(G)$ by at least

$$\begin{aligned} (n_0-1)\big [\tfrac{1}{2}(k_2-2)(k_3-2)+(k_2-2)t_3+(k_3-2)t_2+t_2t_3\big ]>0. \end{aligned}$$

Summing up, the contribution of considered terms to $W(G')-W(G)$ is at least 0 if $k_2+k_3-2$ is even. If $k_2+k_3-2$ is odd, the only changes consist in replacing $\frac{(k_2+k_3-2)^2}{4}$ and $\frac{k_2^2}{4}$ by $\frac{(k_2+k_3-2)^2-1}{4}$ and $\frac{k_2^2-1}{4}$, respectively. Hence, we obtain exactly the same expressions as in the even case.

• 4. Now we consider the terms containing$(n_1-1)$, which were not considered before. Again, we start with the case when $k_2+k_3-2$ is even. The contribution of the terms containing $(n_1-1)$ is at least [compare with (2)]

  $$\begin{aligned}&(n_1-1)\Big [\tfrac{(k_2+k_3-2)^2}{4}+\tfrac{(t_2+t_3)^2-(t_2+t_3)}{2} +(k_2+k_3-3)(t_2+t_3-1)\\&\qquad -\tfrac{k_2^2}{4}-\tfrac{k_3^2}{4}-\tfrac{t_2^2-t_2}{2}-\tfrac{t_3^2-t_3}{2} -(k_2-1)(t_2-1)-(k_3-1)(t_3-1)\big ]\\&\quad =(n_1-1)\big [\tfrac{1}{2}(k_2-2)(k_3-2)+(k_2-2)t_3+(k_3-2)t_2+t_2t_3\big ]. \end{aligned}$$

Since the expression in brackets containing $k_2$, $k_3$, $t_2$ and $t_3$ is nonnegative, we can replace $(n_1-1)$ by a value which is not larger than $(n_1-1)$ and we will not increase the contribution of considered terms. Since $(n_1-1)\ge (n_i-1)=(k_i+t_i-2)$, $2\le i\le 3$, we get $(n_1-1)\ge \frac{1}{2}(k_2+k_3+t_2+t_3-4)$. Hence, the contribution of considered terms is at least

$$\begin{aligned} \tfrac{1}{2}(k_2+k_3+t_2+t_3-4)\big [\tfrac{1}{2}(k_2-2)(k_3-2)+(k_2-2)t_3+(k_3-2)t_2+t_2t_3\big ]\nonumber \\ \end{aligned}$$

(4)

if $k_2+k_3-2$ is even. If $k_2+k_3-2$ is odd, we obtain the very same expression.

• 5. Finally, we consider the remaining terms, i.e., the terms which were not considered in the groups 1.–4. above. Then we include the terms from (4) and we show that their sum is positive. Again, we start with the case when $k_2 + k_3 - 2$ is even.

Since $W(G'_0)-W(G_0)\ge 0$, the terms from the first sum of Proposition 2.2 contribute to $W(G')-W(G)$ by at least

$$\begin{aligned} \tfrac{(k_2+k_3-2)^3}{8}+\tfrac{(t_2+t_3)^3-(t_2+t_3)}{6} -\tfrac{k_2^3}{8}-\tfrac{k_3^3}{8}-\tfrac{t_2^3-t_2}{6}-\tfrac{t_3^3-t_3}{6}. \end{aligned}$$

(5)

The terms from the second sum of (1) contribute to $W(G')-W(G)$ by at least

$$\begin{aligned}&\tfrac{(k_2+k_3-2)^2}{4}(t_2+t_3-1)+\tfrac{(t_2+t_3)^2-(t_2+t_3)}{2}(k_2+k_3-3)\nonumber \\&\quad -\,\tfrac{k_2^2}{4}(k_3+t_2+t_3-3)-\tfrac{k_3^2}{4}(k_2+t_2+t_3-3) -\tfrac{t_2^2-t_2}{2}(k_2+k_3+t_3-3)\nonumber \\&\quad -\,\tfrac{t_3^2-t_3}{2}(k_2+k_3+t_2-3)-(k_2-1)(k_3-1)(t_2+t_3-2)\nonumber \\&\quad -\,(k_2-1)(t_3-1)(t_2-1)-(k_3-1)(t_2-1)(t_3-1). \end{aligned}$$

(6)

And summing (4), (5) and (6) we get

$$\begin{aligned}&\Big (\tfrac{k_3-2}{4}+\tfrac{t_3-1}{2}+\tfrac{1}{2}\Big )(k_2-2)^2 +\Big (\tfrac{k_2-2}{4}+\tfrac{t_2-1}{2}+\tfrac{1}{2}\Big )(k_3-2)^2\nonumber \\&\quad +\,\Big (\tfrac{k_3-2}{4}+\tfrac{t_3-1}{2}\Big )(t_2-1)^2 +\Big (\tfrac{k_2-2}{4}+\tfrac{t_2-1}{2}\Big )(t_3-1)^2\nonumber \\&\quad +\,\Big (\tfrac{k_3^2-4}{8}+\tfrac{k_3t_3}{4}+t_2t_3\Big )(k_2-2) +\Big (\tfrac{k_2^2-4}{8}+\tfrac{k_2t_2}{4}+t_2t_3\Big )(k_3-2)\nonumber \\&\quad +\,\big (t_2^2-1\big )\tfrac{k_3}{4}+\big (t_3^2-1\big )\tfrac{k_2}{4} +2(t_2-1)(t_3-1)+\tfrac{t_2}{2}+\tfrac{t_3}{2} \end{aligned}$$

(7)

which is positive since all the terms are nonnegative while the last two are at least $\frac{1}{2}$ each.

Now consider the case when $k_2+k_3-2$ is odd. Then (4) is without a change, (5) is increased by $-\frac{k_2+k_3-2}{8}+\frac{k_3}{8}=\frac{2-k_2}{8}$ and (6) is increased by $-\frac{1}{4}(t_2+t_3-1)+\frac{1}{4}(k_2+t_2+t_3-3)=\frac{k_2-2}{4}$. So the sum of considered terms is exactly as in (7) plus a nonnegative term $\frac{k_2-2}{8}$.

Since all the groups of terms are nonnegative and the last one is positive, the lemma is proved. $\square$

Now combining Lemmas 2.11 and 2.13 we obtain Theorem 1.1.