# Spectral extrema of $K_{s,t}$-minor free graphs–On a conjecture of M.
Tait111Supported by the National Natural Science Foundation of China (Nos.
11971445, 11771141 and 12011530064).

Mingqing Zhaia , Huiqiu Linb
a School of Mathematics and Finance, Chuzhou University, Chuzhou, Anhui
239012, China
b Department of Mathematics, East China University of Science
and Technology, Shanghai 200237, China Corresponding author. E-mail addresses:
<EMAIL_ADDRESS>(M. Zhai<EMAIL_ADDRESS>(H. Lin).

Abstract

Minors play an important role in extremal graph theory and spectral extremal
graph theory. Tait [The Colin de Verdière parameter, excluded minors, and the
spectral radius, J. Combin. Theory Ser. A 166 (2019) 42–58] determined the
maximum spectral radius and characterized the unique extremal graph for
$K_{r}$-minor free graphs of sufficiently large order $n$, he also made great
progress on $K_{s,t}$-minor free graphs and posed a conjecture: Let $2\leq
s\leq t$ and $n-s+1=pt+q$, where $n$ is sufficiently large and $1\leq q\leq
t.$ Then $K_{s-1}\nabla(pK_{t}\cup K_{q})$ is the unique extremal graph with
the maximum spectral radius over all $n$-vertex $K_{s,t}$-minor free graphs.
In this paper, Tait’s conjecture is completely solved. We also determine the
maximum spectral radius and its extremal graphs for $n$-vertex $K_{1,t}$-minor
free graphs. To prove our results, some spectral and structural tools, such
as, local edge maximality, local degree sequence majorization, double
eigenvectors transformation, are used to deduce structural properties of
extremal graphs.

Keywords: $K_{s,t}$; minor; spectral radius; extremal graph; majorization

AMS Classification: 05C50; 05C35

##  1 Introduction

Given a graph $H$, a graph is said to be _$H$ -free_ if it does not contain
$H$ as a subgraph. The classic _Turán’s problem_ asks what is the maximum size
of an $H$-free graph of order $n$, where the maximum size is known as the
_Turán number_ of $H$ and denoted by $ex(n,H)$. The study of Turán’s problem
can be dated back at least to Mantel [22] in 1907, who showed that
$ex(n,K_{3})\leq\lfloor n^{2}/4\rfloor$. Mantel’s theorem was extended by
Turán’s theorem in 1941 [33]. Since then, Turán’s problem and many kinds of
its variations have been paid much attention and a considerable number of
influential results in extremal graph theory have been obtained (see for
example, a survey, [14]). In contrast, the spectral extremal problem asks:
given a graph $H$, what is the maximum spectral radius of an $H$-free graph of
order $n$? In the past decades much research has been done on spectral
extremal graph theory, see $K_{r}$ [2, 36], $K_{s,t}$ [1, 29], $M_{k}$ [13],
$C_{k,q}$ [21], $P_{k}$ [27], $F_{k}$ [6], $W_{2k+1}$ [5],
$\bigcup_{i=1}^{k}S_{a_{i}}$ [7], $\bigcup_{i=1}^{k}P_{a_{i}}$ [8], $C_{4}$
[28, 40], $C_{6}$ [38], consecutive cycles [15, 19, 25, 23, 39] and a survey
[26].

Given two graphs $H$ and $G$, $H$ is a _minor_ of $G$ if $H$ can be obtained
from a subgraph of $G$ by contracting edges. A graph is said to be _H-minor
free_ , if it does not contain $H$ as a minor. Let $A(G)$ be the adjacency
matrix of $G$ and $\rho(G)$ be its spectral radius. Recently, Nikiforov [24]
and Tait [31, 32] studied the following spectral extremal problem.

######  Problem 1.1.

Given a graph $H$ or a family $\mathbb{H}$, what is the maximum spectral
radius of an $H$-minor ($\mathbb{H}$-minor) free graph of order $n$?

Problem 1.1 was initially paid attention in 1990. Cvetković and Rowlinson [10]
conjectured that $\rho(G)\leq\rho(K_{1}\nabla P_{n-1})$ for any outerplanar
graph $G$ with equality if and only if $G\cong K_{1}\nabla P_{n-1}$. Boots and
Royle [3] and independently Cao and Vince [4] conjectured that
$\rho(G)\leq\rho(K_{2}\nabla P_{n-2})$ for any planar graph $G$ of order
$n\geq 9$ with equality if and only if $G\cong K_{2}\nabla P_{n-2}$.
Subsequently, many scholars contributed to these two conjectures (see [4, 16,
17, 30]). Ellingham and Zha [12] showed that $\rho(G)\leq 2+\sqrt{2n-6}$ for a
planar graph $G$. Dvořák and Mohar [42] proved that
$\rho(G)\leq\sqrt{8\Delta-16}+3.47$ for a planar graph $G$ with maximum degree
$\Delta$. In 2017, Tait and Tobin [31] confirmed these two old conjectures for
sufficiently large $n$. Recently, Lin and Ning [20] confirmed Cvetković-
Rowlinson conjecture completely. In 2004, Hong [18] proved that
$K_{3}\nabla(n-3)K_{1}$ uniquely attains the maximum spectral radius over all
$K_{5}$-minor free graphs. Tait [32] extended Hong’s result to $K_{r}$-minor
free graphs by showing the unique extremal graph is
$K_{r-2}\nabla(n-r+2)K_{1}$. In 2017, Nikiforov [24] contributed to
$K_{2,t}$-minor free graphs, and the result was extended to $K_{s,t}$-minor
free graphs by Tait as shown in the following theorem.

######  Theorem 1.1.

[32] Let $2\leq s\leq t$, $n$ be large enough and $G$ be an $n$-vertex
$K_{s,t}$-minor free graph. Then

$\rho(G)\leq\frac{1}{2}\left(s+t-3+\sqrt{(s+t-3)^{2}+4(s-1)(n-s+1)-4(s-2)(t-1)}\right),$

with equality if and only if $t\mid n-s+1$ and $G\cong
K_{s-1}\nabla\frac{n-s+1}{t}K_{t}$.

It should be noted that, if $t\nmid n-s+1$ then the maximum spectral radius
together with its extremal graph is still unknown for $K_{s,t}$-minor free
graphs. To this end, Tait posed the following conjecture.

######  Conjecture 1.1.

[32] Let $2\leq s\leq t$, $n$ be large enough and $n-s+1=pt+q$, where $1\leq
q\leq t$. Then, the maximum spectral radius of $n$-vertex $K_{s,t}$-minor free
graphs is attained by the join of $K_{s-1}$ with $p$ copies of $K_{t}$ and a
copy of $K_{q}$.

Up to now, Conjecture 1.1 has been confirmed for $s+t=4$ [28, 40]; $s+t=5$
[24]; $s+t=6$ [35]; and $q=t$ (see Theorem 1.1). For a graph $G$, let
$\overline{G}$ be its complement and $S^{k}(G)$ be a graph obtained by
subdividing $k$ times of an edge $uv$ with the minimum degree sum
$d_{G}(u)+d_{G}(v)$. Let $H^{\star}$ be the Petersen graph, and $H_{s,t}$ be a
star forest of order $t+1$, precisely, the disjoint union of
$\lfloor\frac{t+1}{s+1}\rfloor$ stars in which all but at most one are
isomorphic to $K_{1,s}$. In this paper, Conjecture 1.1 is solved.

######  Theorem 1.2.

Let $2\leq s\leq t$, $n-s+1=pt+q$ and $\beta=\lfloor\frac{t+1}{s+1}\rfloor$,
where $n$ is large enough and $1\leq q\leq t$. Let $G^{\star}$ attain the
maximum spectral radius over all $n$-vertex $K_{s,t}$-minor free graphs. Then

$G^{\star}\cong\left\\{\begin{aligned}
&K_{s-1}\nabla\left((p-1)K_{t}\cup\overline{H^{\star}}\right)&&\hbox{if $q=2$,
$t=8$ and $\beta=1$};\\\ &K_{s-1}\nabla\left((p-1)K_{t}\cup
S^{1}\left(\overline{H_{s,t}}\right)\right)&&\hbox{if $q=\beta=2$};\\\
&K_{s-1}\nabla\left((p-q)K_{t}\cup q\overline{H_{s,t}}\right)&&\hbox{if $q\leq
2(\beta-1)$ except $q=\beta=2$};\\\ &K_{s-1}\nabla\left(pK_{t}\cup
K_{q}\right)&&\hbox{otherwise}.\end{aligned}\right.$

It remains $K_{1,t}$-minor free graphs. Let us first consider connected case.
A nice result, due to Ding, Johnson and Seymour [11], determined the maximum
size and constructed its extremal graphs for connected $K_{1,t}$-minor free
graphs. However, it seems difficult to completely characterize the extremal
graphs. Inspired by Ding, Johnson and Seymour, we obtain the following
spectral extremal result.

######  Theorem 1.3.

Let $t\geq 3$, and $G^{*}$ attain the maximum spectral radius over all
$n$-vertex connected $K_{1,t}$-minor free graphs. Then

$G^{*}\cong\left\\{\begin{aligned} &\overline{H_{1,t}}&&\hbox{if $n=t+1$};\\\
&S^{n-t}(K_{t})&&\hbox{if $n\geq t+2$.}\end{aligned}\right.$

By the connected case in Theorem 1.3, we further solve general case.

######  Theorem 1.4.

Let $n\geq t\geq 1$, and $G$ be an $n$-vertex $K_{1,t}$-minor free graph. Then
$\rho(G)\leq t-1$, with equality if and only if $G$ contains a component
either isomorphic to $K_{t}$, or isomorphic to $K_{t+1}$ by deleting
$\frac{t+1}{2}$ independent edges.

Combining with above results, the spectral extremal problem on $K_{s,t}$-minor
free graphs is completely solved for large enough $n$. To prove our results,
we use some spectral and structural tools, such as, local edge maximality (see
Lemma 2.3), local degree sequence majorization (see Lemma 2.7) and double
eigenvectors transformation to deduce structural properties of extremal
graphs.

##  2 Preliminaries

As usual, $V(G)$ is the vertex set and $E(G)$ is the edge set of a graph $G$.
The number of vertices and edges of $G$ are called its _order_ and _size_ ,
and denoted by $|G|$ and $e(G)$, respectively. Given $u\in V(G)$ and a
subgraph $H\subseteq G$ (possibly $u\notin V(H)$), $N_{V(H)}(u)$ is the set of
neighbors of $u$ in $V(H)$ and $d_{V(H)}(u)$ is its cardinality. If $u\in
V(H)$, we also use $N_{H}(u)$ and $d_{H}(u)$ for convenience. If $S\subseteq
V(G)$, then $G[S]$ and $G-S$ stand for the subgraphs of $G$ induced by $S$ and
$V(G)\setminus S$, respectively. If $S\subseteq E(G)$, then $G-S$ denotes the
subgraph obtained from deleting all edges in $S$. If $A,B\subseteq V(G)$, then
$e_{G}(A,B)$ denotes the number of edges with one endpoint in $A$ and the
other in $B$, and particularly, $e_{G}(A,A)$ is simplified by $e_{G}(A)$.

Throughout this section, let $s,t,n$ be integers with $2\leq s\leq t$ and $n$
sufficiently large, $G^{\star}$ be the extremal graph with the maximum
spectral radius $\rho$ over all $n$-vertex $K_{s,t}$-minor free graphs, and
$X=(x_{1},x_{2},\ldots,x_{n})^{T}$ be the Perron vector of $G^{\star}$. Now
let us introduce some important lemmas. The first is due to Chudnovsky, Reed
and Seymour.

######  Lemma 2.1.

[11, 9] Let $t\geq 3$ and $n\geq t+2$. If $G$ is an $n$-vertex connected graph
with no $K_{1,t}$-minor, then $e(G)\leq{t\choose 2}+n-t$, and this is best
possible for all $n,t$.

For $s=2$, Nikiforov [24] proved that $G^{\star}$ contains a dominating
vertex. Tait showed the following result for general $s$. This gives a very
important information for $G^{\star}$.

######  Lemma 2.2.

[32] $G^{\star}$ contains a clique dominating set $K$ with $|K|=s-1$.

By Lemma 2.2, we can observe that $G^{\star}$ is $K_{s,t}$-minor free if and
only if $G^{\star}-K$ satisfies the following property: $K_{a,b}$-minor free
for all positive integers $a,b$ with $a+b=t+1$ and $1\leq
a\leq\min\\{s,\lfloor\frac{t+1}{2}\rfloor\\}$. For convenience, we call it
_$(s,t)$ -property_.

Many known results indicate that an extremal graph with the maximum size
usually is not an extremal graph with the maximum spectral radius. This
observation also happens on $K_{s,t}$-minor free graphs for general $s$ and
$t$. However, the following lemma implies that $G^{\star}$ has a _local edge
maximality_.

######  Lemma 2.3.

Let $H$ be a disjoint union of several components of $G^{\star}-K$ such that
$|H|\leq N$ (a constant). If $H^{\prime}$ also has $(s,t)$-property with
$V(H^{\prime})=V(H)$, then $e(H^{\prime})\leq e(H)$.

###### Proof.

For convenience, let

$X_{0}=\sum_{v\in K}x_{v},~{}~{}~{}x_{1}=\max_{v\in
V(H)}x_{v}~{}~{}~{}\hbox{and}~{}~{}~{}x_{2}=\min_{v\in V(H)}x_{v}.$

Since $H$ has $(s,t)$-property, then $H$ is $K_{1,t}$-minor free and hence
$\Delta(H)<t$. So, $\rho x_{1}<X_{0}+tx_{1}$ and $\rho x_{2}\geq X_{0}$. It
follows that

$\displaystyle
x_{1}<\frac{X_{0}}{\rho-t}~{}~{}~{}\hbox{and}~{}~{}~{}x_{2}\geq\frac{X_{0}}{\rho}.$
(1)

We now give a claim, which will be frequently used in the subsequent proof.

######  Claim 2.1.

Let $a,b$ be two constants with $a>b$. Then $ax_{2}>bx_{1}$ and
$ax_{2}^{2}>bx_{1}^{2}$.

###### Proof.

By Lemma 2.2, $\Delta(G^{\star})=n-1$ and thus
$\rho\geq\rho(K_{1,n-1})=\sqrt{n-1}.$ Since $n$ is large enough and $a,b,t$
are constants, we can easily have

$ax_{2}-bx_{1}>X_{0}\left(\frac{a}{\rho}-\frac{b}{\rho-t}\right)>0,$

and similarly, $ax_{2}^{2}>bx_{1}^{2}$. ∎

Let $G^{\prime}=G^{\star}-E(H)+E(H^{\prime})$ and
$\rho^{\prime}=\rho(G^{\prime})$. Then $G^{\prime}$ is also $K_{s,t}$-minor
free. By the way of contradiction, assume that $e(H^{\prime})\geq e(H)+1$.
Then by Claim 2.1,

$\displaystyle\rho^{\prime}-\rho$ $\displaystyle\geq$ $\displaystyle
X^{T}(A(G^{\prime})-A(G^{\star}))X=2\sum\limits_{uv\in
E(H^{\prime})}x_{u}x_{v}-2\sum\limits_{uv\in E(H)}x_{u}x_{v}$
$\displaystyle\geq$ $\displaystyle 2e(H^{\prime})x_{2}^{2}-2e(H)x_{1}^{2}$
$\displaystyle>$ $\displaystyle 0,$

a contradiction with the maximality of $\rho(G^{\star})$. So
$e(H^{\prime})\leq e(H)$. ∎

For a graph $H$ and two vertices $u,v\in V(H)$ (possibly, $uv\notin E(H)$), we
use $d_{H}(uv)$ to denote $d_{H}(u)+d_{H}(v)$ for convenience.

######  Lemma 2.4.

Let $H$ be a disjoint union of several components of $G^{\star}-K$ such that
$|H|\leq N$ (a constant), If $H^{\prime}$ also has $(s,t)$-property with
$V(H^{\prime})=V(H)$ and $e(H^{\prime})=e(H)$, then

$\sum\limits_{uv\in E(H^{\prime})}d_{H}(uv)\leq\sum\limits_{uv\in
E(H)}d_{H}(uv),$

and if equality holds, then

$\sum\limits_{uv\in E(H^{\prime})}d_{H^{\prime}}(uv)\leq\sum\limits_{uv\in
E(H)}d_{H}(uv).$

###### Proof.

Let $G^{\prime}=G^{\star}-E(H)+E(H^{\prime})$ and
$\rho^{\prime}=\rho(G^{\prime})$. Then $\rho\geq\rho^{\prime}$ and

$\displaystyle\frac{1}{2}\rho^{2}(\rho^{\prime}-\rho)\geq\frac{1}{2}\rho^{2}X^{T}(A(G^{\prime})-A(G^{\star}))X=\sum\limits_{uv\in
E(H^{\prime})}\rho x_{u}\rho x_{v}-\sum\limits_{uv\in E(H)}\rho x_{u}\rho
x_{v}.$ (2)

Recall that

$X_{0}=\sum_{v\in K}x_{v},~{}~{}~{}x_{1}=\max_{v\in
V(H)}x_{v}~{}~{}~{}\hbox{and}~{}~{}~{}x_{2}=\min_{v\in V(H)}x_{v}.$

Thus, for any $v\in V(H)$, we have

$\displaystyle X_{0}+d_{H}(v)x_{2}\leq\rho x_{v}\leq X_{0}+d_{H}(v)x_{1}.$ (3)

It follows that

$\sum\limits_{uv\in E(H^{\prime})}\rho x_{u}\rho x_{v}\geq\sum\limits_{uv\in
E(H^{\prime})}(X_{0}+d_{H}(u)x_{2})(X_{0}+d_{H}(v)x_{2}),$ $\sum\limits_{uv\in
E(H)}\rho x_{u}\rho x_{v}\leq\sum\limits_{uv\in
E(H)}(X_{0}+d_{H}(u)x_{1})(X_{0}+d_{H}(v)x_{1}).$

Now let

$a=\sum\limits_{uv\in E(H^{\prime})}d_{H}(uv),~{}~{}b=\sum_{uv\in
E(H)}d_{H}(uv),~{}~{}c=\sum\limits_{uv\in E(H)}d_{H}(u)d_{H}(v),$

and suppose to the contrary that $a\geq b+1.$ Then

$\displaystyle\sum\limits_{uv\in E(H^{\prime})}\rho x_{u}\rho
x_{v}-\sum\limits_{uv\in E(H)}\rho x_{u}\rho x_{v}$ $\displaystyle\geq$
$\displaystyle aX_{0}x_{2}-bX_{0}x_{1}-cx_{1}^{2}$ $\displaystyle=$
$\displaystyle
X_{0}\left(\left(a-\frac{1}{2}\right)x_{2}-bx_{1}\right)+\left(\frac{1}{2}X_{0}x_{2}-cx_{1}^{2}\right).$

By Claim 2.1, $\left(a-\frac{1}{2}\right)x_{2}>bx_{1}.$ And by (1),

$\frac{1}{2}X_{0}x_{2}-cx_{1}^{2}>X^{2}_{0}\left(\frac{1}{2\rho}-\frac{c}{(\rho-t)^{2}}\right)>0,$

since $\rho\geq\sqrt{n-1}$ and $n$ is large enough. Combining with (2), we
have $\rho^{\prime}>\rho$, a contradiction. Hence, the first inequality holds.

We now prove the second inequality. Let $a=b$ and
$Y=(y_{1},y_{2},\ldots,y_{n})^{T}$ be the Perron vector of $G^{\prime}$ such
that $y_{i}$ and $x_{i}$ correspond the the same vertex $i$. Suppose to the
contrary that $a^{\prime}\geq b+1$, and assume that

$Y_{0}=\sum_{v\in K}y_{v},~{}~{}~{}y_{1}=\max_{v\in
V(H^{\prime})}y_{v}~{}~{}~{}\hbox{and}~{}~{}~{}y_{2}=\min_{v\in
V(H^{\prime})}y_{v}.$

Similar with (3), we have

$\displaystyle Y_{0}+d_{H^{\prime}}(v)y_{2}\leq\rho^{\prime}y_{v}\leq
Y_{0}+d_{H^{\prime}}(v)y_{1}.$ (4)

for any $v\in V(H^{\prime})$. It follows that

$\displaystyle
y_{1}<\frac{Y_{0}}{\rho^{\prime}-t}~{}~{}~{}\hbox{and}~{}~{}~{}y_{2}\geq\frac{Y_{0}}{\rho^{\prime}}.$
(5)

Now we can see that

$\displaystyle\rho^{\prime}\rho(\rho^{\prime}-\rho)Y^{T}X$ $\displaystyle=$
$\displaystyle\rho^{\prime}\rho\left((A(G^{\prime})Y)^{T}X-Y^{T}(A(G)X)\right)$
$\displaystyle=$ $\displaystyle\sum\limits_{uv\in E(H^{\prime})}(\rho
x_{u}\rho^{\prime}y_{v}+\rho x_{v}\rho^{\prime}y_{u})-\sum\limits_{uv\in
E(H)}(\rho x_{u}\rho^{\prime}y_{v}+\rho x_{v}\rho^{\prime}y_{u}).$

Now let

$a^{\prime}=\sum_{uv\in
E(H^{\prime})}d_{H^{\prime}}(uv),b^{\prime}=\sum_{uv\in
E(H)}d_{H^{\prime}}(uv),c^{\prime}=\sum\limits_{uv\in
E(H)}\left(d_{H}(u)d_{H^{\prime}}(v)+d_{H}(v)d_{H^{\prime}}(u)\right).$

Note that $e(H)=e(H^{\prime})$. By (3) and (4), we have

$\displaystyle\rho^{\prime}\rho(\rho^{\prime}-\rho)Y^{T}X$ $\displaystyle\geq$
$\displaystyle\sum\limits_{uv\in
E(H^{\prime})}\left((X_{0}+d_{H}(u)x_{2})(Y_{0}+d_{H^{\prime}}(v)y_{2})+(X_{0}+d_{H}(v)x_{2})(Y_{0}+d_{H^{\prime}}(u)y_{2})\right)$
$\displaystyle-\sum\limits_{uv\in
E(H)}\left((X_{0}+d_{H}(u)x_{1})(Y_{0}+d_{H^{\prime}}(v)y_{1})+(X_{0}+d_{H}(v)x_{1})(Y_{0}+d_{H^{\prime}}(u)y_{1})\right)$
$\displaystyle\geq$ $\displaystyle
aY_{0}x_{2}+a^{\prime}X_{0}y_{2}-bY_{0}x_{1}-b^{\prime}X_{0}y_{1}-c^{\prime}x_{1}y_{1}.$

Recall that $d_{H}(uv)=d_{H}(u)+d_{H}(v)$. We can observe that

$\sum_{uv\in E(H^{\prime})}d_{H}(uv)=\sum_{v\in
V(H^{\prime})}d_{H}(v)d_{H^{\prime}}(v)=\sum_{v\in
V(H)}d_{H}(v)d_{H^{\prime}}(v)=\sum_{uv\in E(H)}d_{H^{\prime}}(uv),$

that is, $a=b^{\prime}.$ Combining with $a=b$ and $a^{\prime}\geq a+1$, we
have

$\displaystyle\rho^{\prime}\rho(\rho^{\prime}-\rho)Y^{T}X$ $\displaystyle\geq$
$\displaystyle
aY_{0}x_{2}+(a+1)X_{0}y_{2}-aY_{0}x_{1}-aX_{0}y_{1}-c^{\prime}x_{1}y_{1}$
$\displaystyle=$ $\displaystyle
X_{0}\left(\left(a+\frac{1}{2}\right)y_{2}-ay_{1}\right)+\left(\frac{X_{0}y_{2}}{2}+aY_{0}\left(x_{2}-x_{1}\right)-c^{\prime}x_{1}y_{1}\right).$

By Claim 2.1, we have $\left(a+\frac{1}{2}\right)y_{2}>ay_{1}.$ And by (1) and
(5), we have

$\frac{X_{0}y_{2}}{2}+aY_{0}\left(x_{2}-x_{1}\right)-c^{\prime}x_{1}y_{1}>X_{0}Y_{0}\left(\frac{1}{2\rho^{\prime}}+\frac{a}{\rho}-\frac{a}{\rho-t}-\frac{c^{\prime}}{(\rho-t)(\rho^{\prime}-t)}\right)>0,$

since $\rho\geq\rho^{\prime}\geq\rho(K_{1,n-1})=\sqrt{n-1}$ and
$a,c^{\prime},t$ are constants. It follows that
$\rho^{\prime}\rho(\rho^{\prime}-\rho)Y^{T}X>0$, that is,
$\rho^{\prime}>\rho$, a contradiction. This completes the proof. ∎

######  Definition 2.1.

_Let $X=(x_{1},x_{2},\ldots,x_{n})^{T}$ and $Y=(y_{1},y_{2},\ldots,y_{n})^{T}$
be two decreasing real vectors. If_

$\sum_{i=1}^{k}x_{i}\leq\sum_{i=1}^{k}y_{i},~{}~{}k=1,2,\ldots,n,$

_then we say that $X$ is_ weakly majorized _by $Y$ and denote it by
$X\prec_{w}Y$. If $X\prec_{w}Y$ and $\sum_{i=1}^{n}x_{i}=\sum_{i=1}^{n}y_{i}$,
then we say that $X$ is_ majorized _by $Y$ and denote it by $x\prec y$._

The following two lemmas are needed in the proof of Lemma 2.7, which is one of
our main tools in this paper.

######  Lemma 2.5.

[20] Let $X=(x_{1},x_{2},\ldots,x_{n})^{T}$,
$Y=(y_{1},y_{2},\ldots,y_{n})^{T}$ be two nonnegative decreasing real vectors.
If $X\prec_{w}Y$, then $\|X\|_{p}\leq\|Y\|_{p}$ for $p>1$, with equality
holding if and only if $X=Y$.

######  Lemma 2.6 (Exercises 5 (i), P74, [41]).

Let $X,Y,Z\in R^{n}$ be three decreasing vectors. If $X\prec Y$, then
$X^{T}\cdot Z\leq Y^{T}\cdot Z$.

Let $\pi(G)$ be the decreasing sequence of vertex degrees of a graph $G$. By
using majorization, Bıyıkoǧlu and Leydold [34] showed that, for two trees $T$
and $T^{\prime}$ with $|T|=|T^{\prime}|$, if $\pi(T^{\prime})\prec\pi(T)$,
then $\rho(T^{\prime})\leq\rho(T).$ Unfortunately, this nice tool does not
work for general graphs, even for unicyclic graphs. However, the following
lemma implies that $G^{\star}$ has a local degree sequence majorization.

######  Lemma 2.7.

Let $H$ and $H^{\prime}$ be defined as in Lemma 2.4. Let
$\pi(H)=(d_{1},\ldots,d_{|H|})$ and
$\pi(H^{\prime})=(d^{\prime}_{1},\ldots,d^{\prime}_{|H|})$. If
$\pi(H)\prec\pi(H^{\prime})$, then $\pi(H)=\pi(H^{\prime})$.

###### Proof.

Let $V(H)=\\{v_{1},v_{2}\ldots,v_{|H|}\\}$ with $d_{H}(v_{i})=d_{i}$. Since
$V(H)=V(H^{\prime})$, by graph isomorphism, we may let
$d_{H^{\prime}}(v_{i})=d^{\prime}_{i}$ for $i=1,2,\ldots,|H|$. Suppose to the
contrary that $\pi(H)\neq\pi(H^{\prime})$. Then by Lemma 2.5, we have

$\displaystyle\sum\limits_{i=1}^{|H|}{d^{\prime}}_{i}^{2}>\sum\limits_{i=1}^{|H|}d_{i}^{2}.$
(6)

Now let $X=Z=\pi(H)$ and $Y=\pi(H^{\prime})$ in Lemma 2.6. Then we have

$\displaystyle\sum\limits_{i=1}^{|H|}d_{i}^{2}\leq\sum\limits_{i=1}^{|H|}d_{i}d^{\prime}_{i}.$
(7)

Furthermore, we see that

$\sum\limits_{i=1}^{|H|}d_{i}d^{\prime}_{i}=\sum\limits_{v\in
V(H^{\prime})}d_{H}(v)d_{H^{\prime}}(v)=\sum\limits_{uv\in
E(H^{\prime})}(d_{H}(u)+d_{H}(v))=\sum\limits_{uv\in E(H^{\prime})}d_{H}(uv).$

And similarly,

$\sum\limits_{i=1}^{|H|}d_{i}^{2}=\sum\limits_{uv\in
E(H)}(d_{H}(u)+d_{H}(v))=\sum\limits_{uv\in E(H)}d_{H}(uv).$

It follows from the first inequality of Lemma 2.4 that
$\sum\limits_{i=1}^{|H|}d_{i}d^{\prime}_{i}\leq\sum\limits_{i=1}^{|H|}d_{i}^{2}.$
Combining with (7), we have
$\sum\limits_{i=1}^{|H|}d_{i}d^{\prime}_{i}=\sum\limits_{i=1}^{|H|}d_{i}^{2}.$
By the second inequality of Lemma 2.4, we have

$\sum\limits_{uv\in E(H^{\prime})}d_{H^{\prime}}(uv)\leq\sum\limits_{uv\in
E(H)}d_{H}(uv),$

that is,
$\sum\limits_{i=1}^{|H|}{d^{\prime}}_{i}^{2}\leq\sum\limits_{i=1}^{|H|}d_{i}^{2},$
which contradicts (6). So, $\pi(H)=\pi(H^{\prime})$. ∎

##  3 Characterization of Components in $G^{\star}-K$

Throughout this section, assume that $t\geq 4$ and $2\leq s\leq t$. Let
$G^{\star},K,H_{s,t}$ and related notations be defined as above. In
particular, recall that each component $H$ of $G^{\star}-K$ satisfies
$(s,t)$-property, that is, $H$ is $K_{a,b}$-minor free for all positive
integers $a,b$ with $a+b=t+1$ and $1\leq a\leq\gamma$, where
$\gamma=\min\\{s,\lfloor\frac{t+1}{2}\rfloor\\}$.

######  Lemma 3.1.

Let $G$ be a connected graph with $|G|=t+1$. Then $G$ has $(s,t)$-property if
and only if each component of $\overline{G}$ has at least $\gamma+1$ vertices.

###### Proof.

Since $|G|=t+1$, a $K_{a,b}$-minor is equivalent to a copy of $K_{a,b}$ for
any positive integers $a,b$ with $a+b=t+1$ and $1\leq a\leq\gamma$. It is easy
to see that $G$ has $(s,t)$-property if and only if each component of
$\overline{G}$ has at least $\gamma+1$ vertices. ∎

######  Lemma 3.2.

Let $\beta=\lfloor\frac{t+1}{s+1}\rfloor$ and $G$ be a connected graph with
$|G|=t+1$. If $G$ has $(s,t)$-property, then $e(G)\leq{t\choose 2}+\beta-1$.

###### Proof.

By Lemma 3.1, each component of $\overline{G}$ has at least $\gamma+1$
vertices. Now assume that $G$ is edge-maximal and $\overline{G}$ has $c$
components. Then each component of $\overline{G}$ is a tree and $c$ is
maximal. This implies that $c=\lfloor\frac{t+1}{\gamma+1}\rfloor$ and
$e\left(\overline{G}\right)=|G|-c.$ If $s\leq\lfloor\frac{t+1}{2}\rfloor$,
then $\gamma=s$ and thus $c=\beta$. It follows that

$\displaystyle e(G)={{t+1}\choose 2}-e\left(\overline{G}\right)={t\choose
2}+c-1={t\choose 2}+\beta-1.$ (8)

If $s>\lfloor\frac{t+1}{2}\rfloor$, then $\gamma=\lfloor\frac{t+1}{2}\rfloor$
and $\beta=1$. We also have $c=\beta$ and hence (8) holds. ∎

The following lemma holds clearly.

######  Lemma 3.3.

Let $G$ be a graph with $vw\in E(G)$ and $uw\notin E(G)$. If $d_{G}(u)\geq
d_{G}(v)$, then $\pi(G)\prec\pi(G-\\{vw\\}+\\{uw\\})$ and
$\pi(G)\neq\pi(G-\\{vw\\}+\\{uw\\})$.

Recall that $\beta=\lfloor\frac{t+1}{s+1}\rfloor$ and
$H_{s,t}=(\beta-1)K_{1,s}\cup K_{1,\alpha}$, where
$\alpha=t-(\beta-1)(s+1)\geq s$. The following theorem presents a clear
characterization of a $(t+1)$-vertex component of $G^{\star}-K$, which is a
key subgraph of the extremal graphs.

######  Theorem 3.1.

Let $H$ be a component of $G^{\star}-K$. If $|H|=t+1$, then $\beta\geq 2$,
$H\cong\overline{H_{s,t}}$ and $e(H)={t\choose 2}+\beta-1$.

###### Proof.

We first show $\beta\geq 2$. Suppose that $\beta=1$. Then by Lemma 3.2,
$e(H)\leq{t\choose 2}=e(K_{t}\cup K_{1}).$ By Lemma 2.3, $e(H)=e(K_{t}\cup
K_{1})$, since $K_{t}\cup K_{1}$ also has $(s,t)$-property. Furthermore, since
$\Delta(H)\leq t-1$ and $\delta(H)\geq 1$, we can see that
$\pi(H)\prec\pi(K_{t}\cup K_{1})$ and $\pi(H)\neq\pi(K_{t}\cup K_{1})$, which
contradicts Lemma 2.7. Thus, $\beta\geq 2$ and correspondingly
$s\leq\lfloor\frac{t-1}{2}\rfloor$. It follows that $\gamma=s$.

Now we characterize the structure of $H$. By Lemma 2.3, $H$ is edge-maximal,
and combining with Lemmas 3.1 and 3.2, we have $e(H)={t\choose 2}+\beta-1$ and
$\overline{H}$ is a forest with $\beta$ components, each of which has at least
$\gamma+1$ ($=s+1$) vertices. We divide the proof into two claims.

######  Claim 3.1.

Each component of $\overline{H}$ is a star.

###### Proof.

Suppose that $\overline{H}$ contains a component $T$ which is not a star.
Then, $T$ contains at least two pendant edges $u_{1}v_{1}$ and $u_{2}v_{2}$,
where $v_{1},v_{2}$ are leaves and $u_{1}\neq u_{2}$. Assume without loss of
generality that $d_{T}(u_{1})\leq d_{T}(u_{2})$. Then $d_{H}(u_{1})\geq
d_{H}(u_{2})$. By Lemma 3.3,
$\pi(H)\prec\pi(H-\\{u_{2}v_{1}\\}+\\{u_{1}v_{1}\\}),$ which contradicts Lemma
2.7. ∎

######  Claim 3.2.

$\overline{H}\cong H_{s,t}.$

###### Proof.

It suffices to show that of $\overline{H}$ has at most one component not
isomorphic to $K_{1,s}$. Suppose that there exist two components $T_{1}$ and
$T_{2}$ with $|T_{2}|\geq|T_{1}|\geq s+2$. Assume that $u_{i}v_{i}\in
E(T_{i})$ and $v_{i}$ is a leaf for $i\in\\{1,2\\}$. Similar to the proof of
Claim 3.1, we can see that
$\pi(H)\prec\pi(H-\\{u_{2}v_{1}\\}+\\{u_{1}v_{1}\\}),$ a contradiction. ∎

Having Claim 3.2, it remains to show that $\overline{H_{s,t}}$ has
$(s,t)$-property. Since $\gamma=s$ and $H_{s,t}\cong
K_{1,\alpha}\cup(\beta-1)K_{1,s}$, each component of $H_{s,t}$ has at least
$\gamma+1$ vertices. By Lemma 3.1, $\overline{H_{s,t}}$ has $(s,t)$-property.
∎

$w$$u_{1}$$u_{2}$$\overline{K}_{a}$$\overline{K}_{b}$$\overline{K}_{c}$$w$$u_{1}$$u_{2}$$K_{a}$$K_{b}$$K_{c}$$H_{a,b,c}$$\overline{H_{a,b,c}}$
Figure 1: The graph $H_{a,b,c}$ and its complement.

######  Lemma 3.4.

Let $\beta\leq 2$ and $G$ be a connected graph with $|G|=t+2$. If $G$ has
$(s,t)$-property, then $e(G)\leq{t\choose 2}+2$, and if equality holds, then
$\overline{G}$ is isomorphic to either some $H_{a,b,c}$ (see Fig. 1) or the
Petersen graph $H^{\star}$.

###### Proof.

Since $G$ satisfies $(s,t)$-property, $G$ contains no $K_{1,t}$-minor. By
Lemma 2.1, we have $e(G)\leq{t\choose 2}+2$. In the following, assume that
$e(G)={t\choose 2}+2$. Then $e\left(\overline{G}\right)=2t-1.$ The proof is
divided into five claims.

######  Claim 3.3.

$\overline{G}$ is connected and $diam(\overline{G})=2$, where
$diam(\overline{G})$ is the diameter of $\overline{G}$.

###### Proof.

If $\overline{G}$ is not connected or $diam\left(\overline{G}\right)\geq 3$,
then there exist a pair of non-adjacent vertices $u,v$ with no common neighbor
in $\overline{G}$. This implies that $uv\in E(G)$ and $N_{G}(u)\cup
N_{G}(v)=V(G)$. Since $|G|=t+2$, we can conclude that $G$ contains a
$K_{1,t}$-minor, a contradiction with $(s,t)$-property. ∎

######  Claim 3.4.

Let $S=\\{u_{1},\ldots,u_{|S|}\\}$ be a minimum cut set of $\overline{G}$.
Then $2\leq|S|\leq 3$.

###### Proof.

Let $d_{G}(u,v)$ be the distance of $u,v\in V(G)$. If $|S|=1$, then
$\overline{G}-\\{u_{1}\\}$ has at least two components $G_{1}$ and $G_{2}$.
Since $G$ is connected, there exists a vertex $v_{1}$, say $v_{1}\in
V(G_{1})$, with $u_{1}v_{1}\notin E\left(\overline{G}\right)$. Now,
$d_{\overline{G}}(v_{1},v)\geq 3$ for any $v\in V(G_{2})$, contradicting Claim
3.3. Therefore, $|S|\geq 2$. Furthermore, since
$\delta\left(\overline{G}\right)\geq|S|$. Thus,
$2e\left(\overline{G}\right)\geq\delta\left(\overline{G}\right)\cdot|G|\geq|S|(t+2).$
Combining with $e\left(\overline{G}\right)=2t-1$, we have $|S|\leq 3.$ ∎

Now let $W=V(G)\setminus S$, $W_{1}=\\{w\in W||N_{\overline{G}}(w)\cap
S|=1\\}$ and $\overline{G}[W]$ consists of $k$ components
$T_{1},\ldots,T_{k}$, where $k\geq 2$.

######  Claim 3.5.

$S$ dominates $W$ and each $V(T_{i})$ dominates $S$ in $\overline{G}$.
Moreover, $W_{1}$ belongs to a single component $T_{i}$.

###### Proof.

Firstly, suppose that $N_{\overline{G}}(w_{0})\cap S=\varnothing$ for some
$w_{0}\in W$. Without loss of generality, assume that $w_{0}\in V(T_{1})$.
Then $d_{\overline{G}}(w_{0},w)\geq 3$ for any $w\in V(T_{2})$, a
contradiction. Hence, $S$ dominates $W$ in $\overline{G}$. Secondly, if a
$V(T_{i})$ does not dominate $S$ in $\overline{G}$, say $u_{1}\notin\cup_{w\in
V(T_{i})}N_{\overline{G}}(w)$, then $S\setminus\\{u_{1}\\}$ is a cut set,
which contradicts the minimality of $|S|$.

Now we show that $W_{1}\subseteq V(T_{i})$ for some $i$. Suppose to the
contrary that $w_{i}\in W_{1}\cap V(T_{i})$ for $i=1,2$. Since
$diam(\overline{G})=2$, $w_{1}$ and $w_{2}$ have a unique and common neighbor,
say $u_{1}$, in $S$. It follows that $wu_{1}\in E\left(\overline{G}\right)$
for any $w\in W$ (Otherwise, either $d_{\overline{G}}(w,w_{1})\geq 3$ or
$d_{\overline{G}}(w,w_{2})\geq 3$). Therefore,
$d_{\overline{G}}(u_{1})\geq|W|.$ If $|S|=2$, then

$e\left(\overline{G}-\\{u_{1}\\}\right)\leq
e\left(\overline{G}\right)-|W|=(2t-1)-t=t-1.$

This implies that $\overline{G}-\\{u_{1}\\}$ is not connected, which
contradicts $|S|=2$. If $|S|=3$, then
$d_{\overline{G}}(u_{2})\geq\delta\left(\overline{G}\right)\geq|S|=3.$ It
follows that

$e\left(\overline{G}-\\{u_{1},u_{2}\\}\right)\leq
e\left(\overline{G}\right)-(|W|+2)=(2t-1)-(t+1)=t-2.$

Then $\\{u_{1},u_{2}\\}$ is a cut set of $\overline{G}$, contradicting
$|S|=3$. So, the claim holds. ∎

Now we may assume without loss of generality that $W_{1}\subseteq V(T_{1}).$
Note that

$\displaystyle
e\left(\overline{G}\right)=e_{\overline{G}}(S)+\sum_{i=1}^{k}e_{\overline{G}}(V(T_{i}))+\sum_{i=1}^{k}e_{\overline{G}}(V(T_{i}),S).$
(9)

######  Claim 3.6.

If $|S|=2$, then $\overline{G}$ is isomorphic to some $H_{a,b,c}$ (see Fig.
1).

$\overline{K}_{a}$$\overline{K}_{b}$$\overline{K}_{c}$$H^{\prime}_{a,b,c}$$w_{1}$$w_{2}$$u_{1}$$u_{2}$$K_{a}$$K_{b}$$K_{c}$$w_{1}$$w_{2}$$u_{1}$$u_{2}$$\overline{H^{\prime}_{a,b,c}}$$K_{t-2}$
Figure 2: The graph $H^{\prime}_{a,b,c}$ and its complement.

###### Proof.

Now, $|W|=t$. Since $W_{1}\subseteq V(T_{1}),$ by (9) we have

$e\left(\overline{G}\right)\geq 2|T_{1}|-1+2\left(|W|-|T_{1}|\right)=2t-1.$

Recall that $e\left(\overline{G}\right)=2t-1.$ We can see that
$e_{\overline{G}}(S)=0$, $T_{1}$ is a tree with $V(T_{1})=W_{1}$, and
$W\setminus W_{1}$ is an independent set of $\overline{G}$.

We shall further show that $T_{1}$ is a star. Since $diam(\overline{G})=2$ and
$V(T_{1})=W_{1}$, we can observe that $w_{1}$ and $w_{2}$ have a unique and
common neighbor in $S$ for any $w_{1},w_{2}\in V(T_{1})$ with
$d_{T_{1}}(w_{1},w_{2})\geq 3$. Thus, if $diam(T_{1})\geq 5$, then $V(T_{1})$
dominates exactly one vertex of $S$ in $\overline{G}$, contradicting Claim
3.5. If $diam(T_{1})=4$, then all vertices in $V(T_{1})$ but the central
vertex are adjacent to a vertex (say $u_{2}$) of $S$. But now, we can find a
leaf $w$ with $d_{\overline{G}}(w,u_{1})=3$, a contradiction. If
$diam(T_{1})=3$, that is, $T_{1}$ is a double star, then we can similarly see
that all leaves have a common neighbor (say $u_{2}$) in $S$, and two central
vertices $w_{1}$ and $w_{2}$ are adjacent to $u_{1}$. It follows that
$\overline{G}\cong H^{\prime}_{a,b,c}$ for some $a,b,c$ with $a+b+c=t-2$ (see
Fig. 2). If $c\leq\gamma-1$, we contract the edge $u_{1}u_{2}$ in $G$ and call
the new vertex $u$ in the resulting graph, then we get a complete bipartite
subgraph with bipartite partition $\left\langle
V(K_{c})\cup\\{u\\},V(K_{a})\cup V(K_{b})\cup\\{w_{1},w_{2}\\}\right\rangle$.
This implies that $G$ contains a $K_{c+1,a+b+2}$-minor, a contradiction with
$(s,t)$-property. So, $c\geq\gamma$. By symmetry, we also have
$a,b\geq\gamma.$ Therefore, $t-2=a+b+c\geq 3\gamma$. This implies that
$\gamma\leq\lfloor\frac{t-2}{3}\rfloor$ and thus
$s\leq\lfloor\frac{t-2}{3}\rfloor$, which contradicts
$\beta=\lfloor\frac{t+1}{s+1}\rfloor\leq 2$.

Now we conclude that $T_{1}$ is a star. Let $w$ be the central vertex of
$T_{1}$. Without loss of generality, assume that $wu_{1}\in E(\overline{G})$.
Then $\overline{G}\cong H_{a,b,c}$ for some $a,b,c$ with $a+b+c=t-1$ (see Fig.
1), as desired. ∎

######  Claim 3.7.

If $|S|=3$, then $\overline{G}$ is isomorphic to the Petersen graph
$H^{\star}$ (see Fig. 3).

$\overline{H^{\star}}$$H^{\star}$$u_{1}$$u_{2}$$u_{3}$ Figure 3: The Petersen
graph $H^{\star}$ and its complement.

###### Proof.

Now $\delta\left(\overline{G}\right)\geq|S|=3$. So, all leaves of $T_{1}$, if
exist, belong to $W\setminus W_{1}$. Hence,

$\displaystyle e_{\overline{G}}(V(T_{1}))+e_{\overline{G}}(V(T_{1}),S)\geq
2|T_{1}|,$ (10)

and if equality holds, then $T_{1}$ is a cycle with $V(T_{1})=W_{1}$.

On the other hand, by Claim 3.5, $V(T_{1})$ dominates $S$ in $\overline{G}$,
which implies that each vertex of $W\setminus V(T_{1})$ also dominates $S$ in
$\overline{G}$ (Otherwise, we can find $w_{1}\in V(T_{1})$ and $w_{2}\in
W\setminus V(T_{1})$ with $d_{\overline{G}}(w_{1},w_{2})\geq 3$). Therefore,
$e_{\overline{G}}\left(W\setminus V(T_{1}),S\right)=3(|W|-|T_{1}|)$. Combining
with (9) and (10), we have

$e\left(\overline{G}\right)\geq
e_{\overline{G}}(S)+2|T_{1}|+3(|W|-|T_{1}|)\geq 3|W|-|T_{1}|\geq 2|W|+1=2t-1.$

Since $e\left(\overline{G}\right)=2t-1$, we have $e_{\overline{G}}(S)=0$,
$T_{1}\cong C_{|W_{1}|}$ and $|W|=|T_{1}|+1.$

Note that $\delta\left(\overline{G}\right)\geq 3$. Each vertex of $S$ has at
least two neighbors in $V(T_{1})$. It follows that $|T_{1}|\geq 6$.
Furthermore, any two vertices with distance at least 3 in $T_{1}$ have a
common neighbor in $S$. If $|T_{1}|\geq 7$, then all vertices in $T_{1}$ have
a common neighbor in $S$, contradicting Claim 3.5. So, $T_{1}\cong C_{6}$ and
every pair of vertices with distance 3 in $T_{1}$ have a common neighbor in
$S$. Thus, $\overline{G}\cong H^{\star}$ (see Fig. 3). ∎

Combining with Claim 3.6 and Claim 3.7, the proof of Lemma 3.4 is completed. ∎

We now use $\mathbb{H}_{i}$, $\mathbb{H}_{>i}$ and $\mathbb{H}_{<i}$ to denote
the family of components in $G^{\star}-K$ with order $i$, greater than $i$ and
less than $i$, respectively.

######  Lemma 3.5.

$\mathbb{H}_{>t+3}=\varnothing.$

###### Proof.

Suppose to the contrary that $H\in\mathbb{H}_{>t+3}$. By Lemma 2.1,

$\displaystyle e(H)\leq{t\choose 2}+|H|-t.$ (11)

Assume that $|H|=pt+q$, where $p\geq 1$ and $1\leq q\leq t$, and let
$H^{\prime}\cong pK_{t}\cup K_{q}$ with $V(H^{\prime})=V(H)$. Clearly,
$H^{\prime}$ satisfies $(s,t)$-property. By (11), we can see that

$e(H)\leq{t\choose 2}+(pt+q)-t<p{t\choose 2}+{q\choose 2}=e(H^{\prime})$

for $|H|>t+3$ and $t\geq 4$. If $p\leq 7$, then $|H|\leq 8t$ (a constant). By
Lemma 2.3, we have $e(H^{\prime})\leq e(H)$, a contradiction. Now assume that
$p\geq 8.$ Then by (11),

$\displaystyle e(H)\leq{t\choose 2}+pt<\frac{4p}{5}{t\choose
2}\leq\frac{4}{5}e(H^{\prime}).$ (12)

Now let $G^{\prime}=G^{\star}-E(H)+E(H^{\prime})$ and
$\rho^{\prime}=\rho(G^{\prime})$. Then

$\displaystyle\rho^{\prime}-\rho\geq
X^{T}(A(G^{\prime})-A(G^{\star}))X=\sum\limits_{uv\in
E(H^{\prime})}2x_{u}x_{v}-\sum\limits_{uv\in E(H)}2x_{u}x_{v}.$

Recall that $x_{1}=\max_{v\in V(H)}x_{v}$ and $x_{2}=\min_{v\in V(H)}x_{v}.$
By (12) and Claim 2.1,

$\rho^{\prime}-\rho\geq
2e(H^{\prime})x^{2}_{2}-2e(H)x^{2}_{1}>2e(H^{\prime})(x^{2}_{2}-\frac{4}{5}x^{2}_{1})>0,$

a contradiction. Thus we have $\mathbb{H}_{>t+3}=\varnothing.$ ∎

######  Lemma 3.6.

$\mathbb{H}_{t}=O(\frac{n}{t})$.

###### Proof.

By Lemma 3.5, $\mathbb{H}_{>t+3}=\varnothing.$ Hence, it suffices to show
$|\mathbb{H}_{i}|<t$ for any $i\leq t+3$ and $i\neq t$. Suppose to the
contrary that $|\mathbb{H}_{i}|\geq t$ for some $i$ and let $\mathbb{F}$ be
the disjoint union of any $t$ components in $\mathbb{H}_{i}$. If $i<t$, then
$e(\mathbb{F})\leq e(tK_{i})<e(iK_{t})$, which contradicts Lemma 2.3.

If $i=t+1$, then by Lemma 3.2 and
$\beta=\lfloor\frac{t+1}{s+1}\rfloor\leq\lfloor\frac{t+1}{3}\rfloor$, we have

$e(\mathbb{F})\leq t\left({t\choose 2}+\beta-1\right)<(t+1){t\choose
2}=e\left((t+1)K_{t}\right),$

which contradicts Lemma 2.3.

If $i\in\\{t+2,t+3\\}$, then by Lemma 2.1,

$e(\mathbb{F})\leq t\left({t\choose 2}+i-t\right)<i{t\choose 2}=e(iK_{t}),$

also a contradiction. ∎

Now we are ready to characterize a $(t+2)$-vertex component of $G^{\star}-K$,
which is also a key subgraph of the extremal graphs.

$K_{t-s-1}$$K_{s}$$v_{t}$$v_{t+2}$$v_{t+1}$ Figure 4: The graph
$S^{1}\left(\overline{H_{s,t}}\right)$ for
$\beta=\lfloor\frac{t+1}{s+1}\rfloor=2$.

######  Theorem 3.2.

Let $H$ be a component of $G^{\star}-K$. If $|H|=t+2$, then $\beta\leq 2$.
Moreover, $H\cong S^{1}\left(\overline{H_{s,t}}\right)$ for $\beta=2$ (see
Fig. 4), and $H\cong\overline{H^{\star}}$ for $\beta=1$.

###### Proof.

The proof is divided into several claims.

######  Claim 3.8.

$\beta\leq 2$.

###### Proof.

If $\beta\geq 3$, then by Theorem 3.1,
$e\left(\overline{H_{s,t}}\right)={t\choose 2}+\beta-1\geq{t\choose 2}+2.$ By
Lemma 3.6, $G^{\star}-K$ contains a component $H_{0}$ isomorphic to $K_{t}$.
Let $H^{\prime}\cong\overline{H_{s,t}}\cup\overline{H_{s,t}}$ and
$V(H^{\prime})=V(H\cup H_{0})$. By Theorem 3.1, $H^{\prime}$ has
$(s,t)$-property. However, $e(H\cup H_{0})=2{t\choose 2}+2<e(H^{\prime}),$
contradicting Lemma 2.3. So, $\beta\leq 2$. ∎

######  Claim 3.9.

$e(H)={t\choose 2}+2$.

###### Proof.

By Lemma 2.1, we have $e(H)\leq{t\choose 2}+2$. Since $K_{t}\cup K_{2}$
satisfies $(s,t)$-property, by Lemma 2.3, we have $e(H)\geq e(K_{t}\cup
K_{2})={t\choose 2}+1$. Now suppose that $e(H)=e(K_{t}\cup K_{2})$. Since
$\Delta(H)\leq t-1$ and $\delta(H)\geq 1$, we can see that
$\pi(H)\prec\pi(K_{t}\cup K_{2})$. By Lemma 2.7, we have

$\pi(H)=\pi(K_{t}\cup K_{2})=(t-1,t-1,\ldots,t-1,1,1),$

which implies that $H$ is obtained from $K_{t}$ by deleting an edge
$u_{1}u_{2}$ and adding two pendant edges $u_{1}v_{1}$ and $u_{2}v_{2}$. Since
$t\geq 4$, we have $N_{H}(u_{1})\setminus\\{v_{1}\\}\neq\varnothing$ and thus

$\rho(x_{u_{1}}-x_{v_{1}})=(x_{v_{1}}-x_{u_{1}})+\sum_{v\in
N_{H}(u_{1})\setminus\\{v_{1}\\}}x_{v}>x_{v_{1}}-x_{u_{1}},$

that is, $x_{u_{1}}>x_{v_{1}}$. By symmetry, we have $x_{u_{1}}=x_{u_{2}}$ and
$x_{v_{1}}=x_{v_{2}}$. Now, let
$H^{\prime}=H-\\{u_{1}v_{1},u_{2}v_{2}\\}+\\{u_{1}u_{2},v_{1}v_{2}\\}$ and
$G^{\prime}=G^{\star}-E(H)+E(H^{\prime})$. Then $H^{\prime}\cong K_{t}\cup
K_{2}$ and thus $H^{\prime}$ has $(s,t)$-property.

$\displaystyle\rho(G^{\prime})-\rho(G^{\star})\geq
X^{T}(A(G^{\prime})-A(G^{\star}))X=2(x_{u_{1}}-x_{v_{2}})(x_{u_{2}}-x_{v_{1}})>0,$

a contradiction. Hence, $e(H)={t\choose 2}+2$. ∎

Now, combining Claims 3.8 and 3.9 with Lemma 3.4, $H$ is isomorphic to either
some $\overline{H_{a,b,c}}$ (see Fig. 1) or the complement of the Peterson
graph $H^{\star}$.

######  Claim 3.10.

If $\beta=2$, then $H\cong S^{1}\left(\overline{H_{s,t}}\right)$ (see Fig. 4).

###### Proof.

Since $\beta=\lfloor\frac{t+1}{s+1}\rfloor$, we have

$\displaystyle 2s+1\leq t\leq
3s+1~{}~{}~{}\hbox{and}~{}~{}~{}\gamma=\min\\{s,\lfloor\frac{t+1}{2}\rfloor\\}=s.$
(13)

If $H\cong\overline{H^{\star}}$, then $|H|=10$, $t=8$ and $H$ is 6-regular. It
follows that $e(H)=30.$ On the other hand, since
$S^{1}\left(\overline{H_{s,8}}\right)$ is a subdivision of
$\overline{H_{s,8}}$, by Theorem 3.1 we have
$e\left(S^{1}\left(\overline{H_{s,8}}\right)\right)=e\left(\overline{H_{s,8}}\right)+1={t\choose
2}+\beta=30$. By Fig. 4 we can see that

$\displaystyle\pi\left(S^{1}\left(\overline{H_{s,t}}\right)\right)=(t-1,\ldots,t-1,t-s,s+1,2),$
(14)

where $s+1\leq t-s\leq 6$. Since $H$ is 6-regular, we have
$\pi(H)\prec\pi\left(S^{1}\left(\overline{H_{s,8}}\right)\right),$
contradicting Lemma 2.7. Thus, $H$ is isomorphic to some
$\overline{H_{a,b,c}}$ with $a+b+c=t-1$.

Next we show that

$\displaystyle\min\\{b,c\\}\geq\gamma.$ (15)

If $b\leq\gamma-1$, we contract the edge $u_{2}w$ in $\overline{H_{a,b,c}}$
and call the new vertex $u$ in the resulting graph, then we get a complete
bipartite subgraph with bipartite partition $\langle V(K_{b})\cup\\{u\\}$,
$V(K_{a})\cup V(K_{c})\cup\\{u_{1}\\}\rangle$. This implies that $H$ contains
a $K_{b+1,a+c+1}$-minor, a contradiction with $(s,t)$-property. So,
$b\geq\gamma$. And by symmetry, $c\geq\gamma.$

Now by Fig. 1 we can see that

$\displaystyle\pi\left(\overline{H_{a,b,c}}\right)=(t-1,\ldots,t-1,a_{1},a_{2},a_{3}),$
(16)

where $a_{1},a_{2},a_{3}\in\\{a+2,b+1,c+1\\}.$ By (13) and (15),
$\min\\{b,c\\}\geq\gamma=s.$ It follows that $a_{3}\geq 2$ and $a_{2}\geq
s+1$. Comparing (14) with (16), we have
$\pi\left(\overline{H_{a,b,c}}\right)\prec\pi\left(S^{1}\left(\overline{H_{s,t}}\right)\right)$.
By Lemma 2.7,
$\pi\left(\overline{H_{a,b,c}}\right)=\pi\left(S^{1}\left(\overline{H_{s,t}}\right)\right)$.
So, $a_{3}=2$ and $a_{2}=s+1.$ Note that $\min\\{b,c\\}\geq s\geq 2$. We
conclude that $a=0$ and $\min\\{b,c\\}=s$, that is, $\overline{H_{a,b,c}}\cong
S^{1}\left(\overline{H_{s,t}}\right).$

Finally, we shall prove that $S^{1}\left(\overline{H_{s,t}}\right)$ has
$(s,t)$-property. It suffices to show that contracting any edge, the resulting
graph always has $(s,t)$-property. Indeed, if we contract an edge within the
$(t-1)$-clique, then the complement of the resulting graph is clearly
connected. By Lemma 3.1, it has $(s,t)$-property. If we contract an edge out
of the $(t-1)$-clique, then the resulting graph is isomorphic to
$\overline{H_{s,t}}$. By Theorem 3.1, it also has $(s,t)$-property. ∎

######  Claim 3.11.

If $\beta=1$, then $H\cong\overline{H^{\star}}$ (see Fig. 3).

###### Proof.

Since $\beta=\lfloor\frac{t+1}{s+1}\rfloor=1$, we have $t\leq 2s$ and thus
$\gamma=\min\\{s,\lfloor\frac{t+1}{2}\rfloor\\}=\lfloor\frac{t+1}{2}\rfloor.$
If $H$ is isomorphic to some $\overline{H_{a,b,c}}$ with $a+b+c=t-1$, then by
(15), we have $t-1\geq b+c\geq 2\gamma=2\lfloor\frac{t+1}{2}\rfloor,$ a
contradiction. By Lemma 3.4, $H$ is only possibly isomorphic to
$\overline{H^{\star}}.$

It remains to show that $\overline{H^{\star}}$ has $(s,t)$-property. We know
that the Peterson graph $H^{\star}$ is 3-connected and any two non-adjacent
vertices of $H^{\star}$ have exactly one common neighbor, which implies that
contracting any edge of $\overline{H^{\star}}$, the complement of the
resulting graph is connected. By Lemma 3.1, the resulting graph has
$(s,t)$-property, and thus $\overline{H^{\star}}$ has $(s,t)$-property. ∎

Combining with Claims 3.8, 3.10 and 3.11, the proof of Theorem 3.2 is
completed. ∎

From Lemma 3.5, we know that $\mathbb{H}_{>t+3}=\varnothing$. Now combining
with Lemma 3.4, we can get a stronger result.

######  Theorem 3.3.

$\mathbb{H}_{>t+2}=\varnothing$.

###### Proof.

It suffices to show that $\mathbb{H}_{t+3}=\varnothing$. Suppose to the
contrary that there exists a component $H$ of $G^{\star}-K$ with $|H|=t+3.$ On
one hand, $e(H)\leq{t\choose 2}+3$ by Lemma 2.1. On the other hand, note that
$K_{t}\cup K_{3}$ also satisfies $(s,t)$-property. Then by Lemma 2.3,
$e(H)\geq e(K_{t}\cup K_{3})={t\choose 2}+3.$ Therefore, $e(H)={t\choose
2}+3$. Moreover, if $\beta\geq 3$, then by Theorem 3.1,
$|\overline{H_{s,t}}|=t+1$, $e\left(\overline{H_{s,t}}\right)={t\choose
2}+(\beta-1)$ and $\overline{H_{s,t}}$ has $(s,t)$-property. Selecting two
copies of $K_{t}$ in $G^{\star}-K$, we have

$e(H\cup K_{t}\cup K_{t})=3{t\choose 2}+3<3{t\choose
2}+3(\beta-1)=e\left(\overline{H_{s,t}}\cup\overline{H_{s,t}}\cup\overline{H_{s,t}}\right),$

a contradiction with Lemma 2.3. Therefore, $\beta\leq 2.$

######  Claim 3.12.

$\delta(H)\geq 2.$

###### Proof.

If $\delta(H)=1$, say $d_{H}(v)=1$, then $H-\\{v\\}$ is connected and
$e(H-\\{v\\})={t\choose 2}+2$. By Lemma 3.4, $H-\\{v\\}$ is isomorphic to
either $\overline{H^{\star}}$ or some $\overline{H_{a,b,c}}$ with $a+b+c=t-1$.
Observe that $\overline{H_{a,b,c}}$ contains a $K_{t}$-minor (by contracting
edges $u_{1}u_{2}$ and $u_{2}w$, see Fig. 1). Hence,
$H-\\{v\\}\cong\overline{H^{\star}}$ (Otherwise, $H$ contains a
$K_{1,t}$-minor).

Now let $vuw$ be a path of length 2 in $H$. We know that any two non-adjacent
vertices in the Petersen graph $H^{\star}$ have exactly one common neighbor.
So, contracting $uw$ in $H-\\{v\\}$, the new vertex is of degree $t-1$ in the
resulting graph. Correspondingly, contracting $uw$ in $H$, the new vertex is
of degree $t$, which contradicts that $H$ is $K_{1,t}$-minor free. ∎

Now we have $\pi(H)\prec\pi(K_{t}\cup K_{3})=(t-1,\ldots,t-1,2,2,2)$, since
$e(H)={t\choose 2}+3$ and $\delta(H)\geq 2$. By Lemma 2.7,
$\pi(H)=\pi(K_{t}\cup K_{3}).$ Let $S_{1}=\\{v\in V(H)|d_{H}(v)=2\\}$ and
$S_{2}=\cup_{v\in S_{1}}N_{H}(v)\setminus S_{1}$. Then $|S_{1}|=3$, and $1\leq
d_{S_{1}}(u)\leq 3$ for any $u\in S_{2}$.

######  Claim 3.13.

$d_{S_{1}}(u)=1$ for any $u\in S_{2}$.

###### Proof.

Let $R$ be the set of non-adjacent vertex-pairs in $S_{2}$. Since
$|V(H)\setminus S_{1}|=t$ and $d_{H}(u)=t-1$ for any $u\in V(H)\setminus
S_{1}$, we have $|R|=\frac{1}{2}e_{H}(S_{1},S_{2})\leq 3$. Suppose that
$d_{S_{1}}(u_{0})=c\in\\{2,3\\}$ for some $u_{0}\in S_{2}$. Then, $u_{0}$ has
exactly $c$ non-neighbors, say $\\{u_{1},\ldots,u_{c}\\}$, in $S_{2}$. If
$c=3$, then $R=\\{(u_{0},u_{i})|i=1,2,3\\}$ and there are three paths
$u_{0}v_{i}u_{i}$ in $H$, where $v_{i}\in S_{1}$ and $i\in\\{1,2,3\\}$. But
now we find a $K_{2,t-1}$-minor in $H$ by contracting two of the three paths
into edges. Therefore, $c=2$.

Since $t\geq 4$, we can find a vertex $u_{3}\in N_{H}(u_{0})\setminus S_{1}$.
If both $u_{1}$ and $u_{2}$ are neighbors of $u_{3}$, then $H$ contains a
double star with a non-pendant edge $u_{0}u_{3}$ and $t$ leaves, and thus a
$K_{1,t}$-minor. If both $u_{1}$ and $u_{2}$ are not neighbors of $u_{3}$,
then $|R|\geq 4$, a contradiction. Hence, we may assume that $u_{1}u_{3}\in
E(H)$ and $u_{2}u_{3}\notin E(H)$. Then, $u_{1}u_{2}\in E(H)$ (Otherwise, we
get $|R|\geq 4$ again). It follows that $P=u_{0}u_{3}u_{1}u_{2}$ is an induced
path in $H$ and $S_{2}=\\{u_{0},u_{1},u_{2},u_{3}\\}$. Furthermore,
$d_{S_{1}}(u_{0})=d_{S_{1}}(u_{2})=2$ and
$d_{S_{1}}(u_{1})=d_{S_{1}}(u_{3})=1$. Now, we can always find a double star
with a non-pendant edge in $E(P)$ and $t$ leaves, a contradiction. ∎

######  Claim 3.14.

$x_{u}>x_{v}$ for any $u\in S_{2}$ and $v\in S_{1}$.

###### Proof.

By (3), $\rho x_{u}\geq X_{0}+d_{H}(u)x_{2}$ and $\rho x_{v}\leq
X_{0}+d_{H}(v)x_{1}$. Combining with Claim 2.1, we have $\rho(x_{u}-x_{v})\geq
d_{H}(u)x_{2}-d_{H}(v)x_{1}>0.$ ∎

Now by Claim 3.13, each $u_{i}\in S_{2}$ has a unique neighbor $v_{i}$ in
$S_{1}$, and thus a unique non-neighbor $u_{j}$ in $S_{2}$. If $v_{i}=v_{j}$
or $v_{i}v_{j}\in E(H)$ for some $(u_{i},u_{j})\in R$, then $u_{i}$ and
$u_{j}$ have $t-1$ common neighbors after contracting the path
$u_{i}v_{i}v_{j}u_{j}$ into $u_{i}v_{i}u_{j}$ in $H$. This implies that $H$
contains a $K_{2,t-1}$-minor. Thus, $v_{i}\neq v_{j}$ and $v_{i}v_{j}\notin
E(H)$ for any $(u_{i},u_{j})\in R$. Let

$H^{\prime}=H-\\{u_{i}v_{i},u_{j}v_{j}|(u_{i},u_{j})\in
R\\}+\\{u_{i}u_{j},v_{i}v_{j}|(u_{i},u_{j})\in R\\}$

and $G^{\prime}=G^{\star}-E(H)+E(H^{\prime})$. Note that $H^{\prime}\cong
K_{t}\cup K_{3}$. Thus, $H^{\prime}$ has $(s,t)$-property. Moreover, by Claim
3.14, we have

$\rho(G^{\prime})-\rho(G^{\star})\geq 2\sum_{(u_{i},u_{j})\in
R}(x_{u_{i}}x_{u_{j}}+x_{v_{i}}x_{v_{j}}-x_{u_{i}}x_{v_{i}}-x_{u_{j}}x_{v_{j}})=2(x_{u_{i}}-x_{v_{j}})(x_{u_{j}}-x_{v_{i}})>0,$

a contradiction. So, $\mathbb{H}_{t+3}=\varnothing$. This completes the proof.
∎

##  4 Proof of Theorem 1.2

Tait’s conjecture has been confirmed for $s+t\leq 6$. This implies that Tait’s
conjecture holds for $t\leq 3$. In this section, we only need prove Theorem
1.2 under that $t\geq 4$.

######  Lemma 4.1.

$|\mathbb{H}_{<t}\cup\mathbb{H}_{t+2}|\leq 1.$

###### Proof.

By the way of contradiction assume that
$H_{1},H_{2}\in\mathbb{H}_{<t}\cup\mathbb{H}_{t+2}$, and let
$|H_{1}|+|H_{2}|=pt+q$, where $0\leq p\leq 2$ and $1\leq q\leq t$. For each
$H_{i}$, if $|H_{i}|\leq t-1$, then $e(H_{i})\leq{|H_{i}|\choose 2}$; and if
$|H_{i}|=t+2$, then $e(H_{i})\leq{t\choose 2}+2$ by Lemma 3.2. In any case,
one can check that $e(H_{1}\cup H_{2})<p{t\choose 2}+{q\choose 2}=e(pK_{t}\cup
K_{q})$, a contradiction with Lemma 2.3. ∎

######  Theorem 4.1.

Let $G^{\star},s,t,n,p,q,\beta$ be defined as in Theorem 1.2. If $\beta=1$,
then

$G^{\star}\cong\left\\{\begin{aligned}
&K_{s-1}\nabla\left((p-1)K_{t}\cup\overline{H^{\star}}\right)&&\hbox{for $q=2$
and $t=8$};\\\ &K_{s-1}\nabla\left(pK_{t}\cup
K_{q}\right)&&\hbox{otherwise}.\end{aligned}\right.$

###### Proof.

Since $\beta=1$, by Theorem 3.1 we have $\mathbb{H}_{t+1}=\varnothing$, and by
Theorem 3.3, $\mathbb{H}_{>t+2}=\varnothing$. Furthermore, by Lemma 4.1, all
but at most one component $H$ of $G^{\star}-K$ are isomorphic to $K_{t}$. Note
that $|G^{\star}-K|=pt+q$, where $1\leq q\leq t$. Then, either $|H|=q$ or
$|H|=t+q=t+2$.

If $q\neq 2$, then $H\cong K_{q}$ and $G^{\star}-K\cong pK_{t}\cup K_{q},$ as
desired. Now assume that $q=2$. Then either $H\cong K_{2}$, or
$H\cong\overline{H^{\star}}$ by Theorem 3.2 (In this case, $t=8$). So, if
$t\neq 8$, then $G^{\star}-K\cong pK_{t}\cup K_{2}.$ If $t=8$, then
$H\cong\overline{H^{\star}}$ (Otherwise, $H\cong K_{2}$. Then $e(K_{8}\cup
K_{2})=29<30=e\left(\overline{H^{\star}}\right)$, a contradiction with Lemma
2.3). ∎

######  Lemma 4.2.

$|\mathbb{H}_{t+1}|\leq 2\beta-2$, where
$\beta=\lfloor\frac{t+1}{s+1}\rfloor$.

###### Proof.

The case $\mathbb{H}_{t+1}=\varnothing$ is trivial. Assume that
$\mathbb{H}_{t+1}\neq\varnothing$. Then by Theorem 3.1, $\beta\geq 2$,
$H\cong\overline{H_{s,t}}$ and $e(H)={t\choose 2}+\beta-1$ for any
$H\in\mathbb{H}_{t+1}$.

If $|\mathbb{H}_{t+1}|\geq 2\beta$, we select $2\beta$ copies of
$\overline{H_{s,t}}$ and denote it by $\mathbb{F}$. Then
$e(\mathbb{F})=2\beta\left({t\choose 2}+\beta-1\right)$. Now let
$\mathbb{F}^{\prime}=2\beta K_{t}\cup K_{2\beta}$. Note that $2\beta<t.$ Then
$\mathbb{F}^{\prime}$ satisfies $(s,t)$-property. However,

$e(\mathbb{F}^{\prime})=2\beta{t\choose 2}+{2\beta\choose
2}>2\beta\left({t\choose 2}+\beta-1\right)=e(\mathbb{F}),$

a contradiction. So, $|\mathbb{H}_{t+1}|\leq 2\beta-1$.

Now assume that $|\mathbb{H}_{t+1}|=2\beta-1$. Let $\mathbb{F}$ be the
disjoint union of $2\beta-1$ copies of $\overline{H_{s,t}}$, and
$\mathbb{F}^{\prime}=(2\beta-1)K_{t}\cup K_{2\beta-1}$. Then
$e(\mathbb{F}^{\prime})=e(\mathbb{F}).$ Recall that $H_{s,t}\cong
K_{1,\alpha}\cup(\beta-1)K_{1,s}$, where $\alpha=t-(s+1)(\beta-1)\geq s$. So,

$\displaystyle\delta\left(\overline{H_{s,t}}\right)=(s+1)(\beta-1)>2(\beta-1)$
(17)

and thus $\delta(\mathbb{F})>2\beta-2.$ Note that
$\pi(\mathbb{F}^{\prime})=(t-1,\ldots,t-1,2\beta-2,\ldots,2\beta-2).$ We can
observe that $\pi(\mathbb{F})\prec\pi(\mathbb{F}^{\prime}),$ a contradiction.
Therefore, $|\mathbb{H}_{t+1}|\leq 2\beta-2$. ∎

######  Lemma 4.3.

If $\mathbb{H}_{t+1}\neq\varnothing$, then
$\mathbb{H}_{t+2}\cup\mathbb{H}_{<t}=\varnothing$.

###### Proof.

Suppose to the contrary that
$\mathbb{H}_{t+2}\cup\mathbb{H}_{<t}\neq\varnothing$. By Lemma 4.1,
$G^{\star}-K$ contains a unique component
$H_{1}\in\mathbb{H}_{t+2}\cup\mathbb{H}_{<t}.$ Now let
$H_{2}\in\mathbb{H}_{t+1}$. Then by Theorem 3.1, $\beta\geq 2$ and
$H_{2}\cong\overline{H_{s,t}}$.

If $|H_{1}|=t+2$, then $\beta=2$ and $H_{1}\cong
S^{1}\left(\overline{H_{s,t}}\right)$ by Theorem 3.2. Note that $H_{1}$ is a
subdivision of $H_{2}$ and $e(H_{2})={t\choose 2}+\beta-1$. We have

$e(H_{1}\cup H_{2})=2e(H_{2})+1=2\left({t\choose
2}+\beta-1\right)+1=2{t\choose 2}+3.$

Now let $H^{\prime}=K_{t}\cup K_{t}\cup K_{3}$. Then $|H^{\prime}|=|H_{1}\cup
H_{2}|$ and $e(H^{\prime})=e(H_{1}\cup H_{2}).$ By (17), $\delta(H_{2})>2.$
Since $H_{1}$ is a subdivision of $H_{2}$, $\delta(H_{1})=2$ and its vertex of
degree two is unique. This implies that $\pi(H_{1}\cup
H_{2})\prec\pi(H^{\prime})$ and $\pi(H_{1}\cup H_{2})\neq\pi(H^{\prime})$, a
contradiction.

If $|H_{1}|<t$, then $H_{1}\cong K_{|H_{1}|}$. Then

$\displaystyle|H_{1}|\leq\beta-1.$ (18)

Otherwise, $|H_{1}|>\beta-1,$ then

$e(H_{1}\cup H_{2})={|H_{1}|\choose 2}+{t\choose 2}+\beta-1<{t\choose
2}+{|H_{1}|\choose 2}+|H_{1}|=e(K_{t}\cup K_{|H_{1}|+1}),$

a contradiction with Lemma 2.3. On the other hand, we have

$\displaystyle|H_{1}|(\beta-1)\leq{|H_{1}|\choose 2}.$ (19)

Indeed, recall that $|\mathbb{H}_{t}|=O(\frac{n}{t})$, thus $G^{\star}-K$
contains a disjoint union of $H_{1}$ and $|H_{1}|$ copies of $K_{t}$. We
denote it by $\mathbb{F}$. Then $e(\mathbb{F})={|H_{1}|\choose
2}+|H_{1}|{t\choose 2}.$ Now let $\mathbb{F}^{\prime}=|H_{1}|H_{2}$. Clearly,
$|\mathbb{F}|=|\mathbb{F}^{\prime}|$ and
$e(\mathbb{F}^{\prime})=|H_{1}|\left({t\choose 2}+\beta-1\right)$. By Lemma
2.3, $e(\mathbb{F}^{\prime})\leq e(\mathbb{F})$. It follows that (19) holds.
However, (18) and (19) contradict each other. ∎

######  Theorem 4.2.

Let $G^{\star},s,t,n,p,q,\beta$ be defined as in Theorem 1.2. If $\beta\geq
2$, then

$G^{\star}\cong\left\\{\begin{aligned} &K_{s-1}\nabla\left((p-1)K_{t}\cup
S^{1}\left(\overline{H_{s,t}}\right)\right)&&\hbox{if $q=\beta=2$};\\\
&K_{s-1}\nabla\left((p-q)K_{t}\cup q\overline{H_{s,t}}\right)&&\hbox{if $q\leq
2(\beta-1)$ except $q=\beta=2$};\\\ &K_{s-1}\nabla\left(pK_{t}\cup
K_{q}\right)&&\hbox{if $q>2(\beta-1)$}.\end{aligned}\right.$

###### Proof.

Recall that $|G^{\star}-K|=pt+q$, where $1\leq q\leq t$, and
$H\cong\overline{H_{s,t}}$ for any $H\in\mathbb{H}_{t+1}$. Moreover, we assert
that if $q\leq 2(\beta-1)$, then $\mathbb{H}_{<t}=\varnothing$. Indeed, if
$G^{\star}-K$ contains a component $H_{1}$ with $|H_{1}|<t,$ then
$\mathbb{H}_{>t}=\varnothing$ and $|\mathbb{H}_{<t}|=1$ by Lemmas 4.1 and 4.3.
This implies that $|H_{1}|=q$. Now by (19),
$|H_{1}|(\beta-1)\leq{|H_{1}|\choose 2}$, that is, $|H_{1}|\geq 2(\beta-1)+1,$
contradicts $q\leq 2(\beta-1)$.

Now we distinguish two cases. We first assume that $q\neq 2$. Then by Lemmas
4.1 and 4.3, $G^{\star}-K$ is isomorphic to either $pK_{t}\cup K_{q}$ or
$(p-q)K_{t}\cup q\overline{H_{s,t}}.$ If $q\leq 2(\beta-1)$ $(<t)$, then
$\mathbb{H}_{<t}=\varnothing$, and thus $G^{\star}-K\cong(p-q)K_{t}\cup
q\overline{H_{s,t}}.$ If $q>2(\beta-1)$. then by Lemma 4.2, we have
$G^{\star}-K\cong pK_{t}\cup K_{q}$.

Now assume that $q=2$. Since $\beta\geq 2$, we have $q\leq 2(\beta-1)$ and
thus $\mathbb{H}_{<t}=\varnothing$. If $\beta>2$, then
$\mathbb{H}_{t+2}=\varnothing$ by Theorem 3.2. Thus,
$G^{\star}-K\cong(p-q)K_{t}\cup q\overline{H_{s,t}}.$ It remains the case
$q=\beta=2$. Now if $\mathbb{H}_{t+1}\neq\varnothing$, then
$\mathbb{H}_{t+2}=\varnothing$ by Lemma 4.3. This implies that
$G^{\star}-K\cong(p-2)K_{t}\cup\overline{H_{s,t}}\cup\overline{H_{s,t}}.$
Recall that $e\left(\overline{H_{s,t}}\right)={t\choose 2}+\beta-1={t\choose
2}+1.$ Now let $H^{\prime}=K_{t}\cup S^{1}\left(\overline{H_{s,t}}\right).$
Then $|H^{\prime}|=2|\overline{H_{s,t}}|=2t+2$ and

$e(H^{\prime})=e(K_{t})+e\left(\overline{H_{s,t}}\right)+1=2e\left(\overline{H_{s,t}}\right).$

Since $S^{1}\left(\overline{H_{s,t}}\right)$ is a subdivision of
$\overline{H_{s,t}}$, we can easily see that
$\pi\left(\overline{H_{s,t}}\cup\overline{H_{s,t}}\right)\prec\pi(H^{\prime}),$
a contradiction. Thus, $\mathbb{H}_{t+1}=\varnothing$. It follows that
$|\mathbb{H}_{t+2}|=1.$ From Theorem 3.2, we have
$G^{\star}-K\cong(p-1)K_{t}\cup S^{1}\left(\overline{H_{s,t}}\right).$ This
completes the proof. ∎

Combining with Theorems 4.1 and 4.2, we completes the proof of Theorem 1.2.

##  5 Proof of Theorems 1.3 and 1.4

Throughout this section, let $G^{*}$ be the extremal graph with the maximum
spectral radius over all $n$-vertex connected $K_{1,t}$-minor free graphs,
$\rho=\rho(G^{*})$ and $X=(x_{1},x_{2},\ldots,x_{n})^{T}$ be the Perron vector
of $G^{*}$. Furthermore, assume that $u^{*}\in V(G^{*})$ with
$x_{u^{*}}=\max_{u\in V(G^{*})}x_{u}$, and let $A=N_{G^{*}}(u^{*}),$
$B=V(G^{*})\setminus(A\cup\\{u^{*}\\})$,
$N^{2}(u^{*})=\\{d_{G^{*}}(w,u^{*})=2|w\in B\\}.$ Above all, we need a lemma.

######  Lemma 5.1.

[37] Let $G$ be a connected graph and $X=(x_{1},x_{2},\ldots,x_{n})^{T}$ be
its Perron vector. If $x_{u}\geq x_{v}$ and
$N_{G}(v)\setminus(N_{G}(u)\cup\\{u\\})=S\neq\varnothing$ for some $u,v\in
V(G)$, then $\rho\left(G-\\{vw|w\in S\\}+\\{uw|w\in S\\}\right)>\rho(G)$.

If $n\leq t$, it is clear that $G^{*}\cong K_{n}$. Moreover, there exists no
connected $K_{1,2}$-minor free graph of order $n\geq 3$. Therefore, we need
only consider connected $K_{1,t}$-minor free graphs for $t\geq 3$ and $n\geq
t+1$.

######  Lemma 5.2.

$\rho>t-2$ and $|A|=t-1$.

###### Proof.

Let $K_{t}-e$ be the graph obtained from $K_{t}$ by deleting an edge, and
recall that $S^{n-t}(K_{t})$ is obtained from $K_{t}$ by subdividing $n-t$
times of one edge. Clearly, $S^{n-t}(K_{t})$ is $K_{1,t}$-minor free and
contains $K_{t}-e$ as a proper subgraph. It follows that
$\rho(G^{*})\geq\rho(S^{n-t}(K_{t}))>\rho(K_{t}-e)$. Let
$\rho^{\prime}=\rho(K_{t}-e)$ and $Y=(y_{1},\ldots,y_{1},y_{2},y_{2})^{T}$ be
the Perron vector of $K_{t}-e$, where $y_{1}$ corresponds to the $t-2$
vertices of degree $t-1$ and $y_{2}$ corresponds to the two vertices of degree
$t-2$. Then we have

$\rho^{\prime}y_{1}=(t-3)y_{1}+2y_{2},~{}~{}~{}~{}\rho^{\prime}y_{2}=(t-2)y_{1}.$

Solving these two equations, we have $\rho^{\prime
2}-(t-3)\rho^{\prime}-2(t-2)=0$. Since $\rho=\rho(G^{*})>\rho(K_{t}-e)$, we
have

$\displaystyle\rho^{2}-(t-3)\rho>2(t-2).$ (20)

Clearly, $\rho>t+2$ for $t\geq 3$, as claimed. Furthermore, $\rho
x_{u^{*}}=\sum_{v\in A}x_{v}\leq|A|x_{u^{*}}.$ It follows that
$|A|\geq\rho>t-2$. On the other hand, we see that $|A|\leq\Delta(G^{*})\leq
t-1$ for forbidding $K_{1,t}$-minor. Therefore, $|A|=t-1$. ∎

By Lemma 5.2, $d_{A}(v)\leq t-2$ for any $v\in A$. Let $A_{0}=\\{v\in
A|d_{A}(v)=t-2\\}$ and $A_{1}=A\setminus A_{0}$. Clearly, $d_{B}(v)=0$ for any
$v\in A_{0}$, since $\Delta(G^{*})=t-1$.

######  Lemma 5.3.

(i) $d_{B}(v)\leq 1$ for any $v\in A_{1}$.

(ii) $d_{B}(w)\leq 2$ for any $w\in B$. Particularly, $d_{B}(w)\leq 1$ for
$w\in N^{2}(u^{*})$.

###### Proof.

(i) Suppose that $d_{B}(v_{0})\geq 2$ for some $v_{0}\in A_{1}$. Then $G^{*}$
contains a double star with a non-pendant edge $u^{*}v_{0}$ and
$|A|-1+d_{B}(v_{0})$ leaves. Since $|A|-1+d_{B}(v_{0})\geq t$, we find a
$K_{t}$-minor in $G^{*}$, a contradiction. So the claim holds.

(ii) For any vertex $w\in B$, we can find a shortest path $P$ from $w$ to
vertices in $A$. Clearly, $d_{B\cap V(P)}(w)\leq 1$, and particularly,
$d_{B\cap V(P)}(w)=0$ if $w\in N^{2}(u^{*})$. Let $v\in A$ be the other
endpoint of $P$. Then $G^{*}$ contains a tree consisting of a path $P+vu^{*}$
and $|A|-1+d_{B\setminus V(P)}(w)$ leaves. Since $G^{*}$ is $K_{1,t}$-minor
free, we have $|A|-1+d_{B\setminus V(P)}(w)\leq t-1$. It follows that
$d_{B}(w)\leq d_{B\cap V(P)}(w)+1$, and thus the claim holds. ∎

######  Lemma 5.4.

Let $v_{1}\in A_{1}$ and $w\in B$ such that $v_{1}w$ is an edge, and
$\overline{N}_{A}(v_{1})$ be the set of non-neighbors of $v_{1}$ in $A$. Then
$x_{w}\leq\sum_{v\in\overline{N}_{A}(v_{1})}x_{v}.$

###### Proof.

By Lemma 5.3, $w$ is the unique neighbor of $v_{1}$ in $B$. Thus we have

$\rho x_{u^{*}}=\sum\limits_{v\in
A\setminus\\{v_{1}\\}}x_{v}+x_{v_{1}},~{}~{}~{}\rho
x_{v_{1}}=\sum\limits_{v\in N_{A}(v_{1})}x_{v}+x_{w}+x_{u^{*}}.$

It follows that
$\rho(x_{u^{*}}-x_{v_{1}})=(x_{v_{1}}-x_{u^{*}})-x_{w}+\sum\limits_{v\in\overline{N}_{A}(v_{1})}x_{v}.$
Therefore,

$x_{w}=(\rho+1)(x_{v_{1}}-x_{u^{*}})+\sum\limits_{v\in\overline{N}_{A}(v_{1})}x_{v}\leq\sum\limits_{v\in\overline{N}_{A}(v_{1})}x_{v},$

since $x_{v_{1}}\leq x_{u^{*}}$. ∎

######  Theorem 5.1.

If $n=t+1$, then $\overline{G^{*}}\cong\frac{n}{2}K_{1,1}$ for even $n$, and
$\overline{G^{*}}\cong K_{1,2}\cup\frac{n-3}{2}K_{1,1}$ for odd $n$. In other
words, $\overline{G^{*}}\cong H_{1,t}$.

###### Proof.

Recall that $|A|=t-1$. Then $|B|=1$. Say $B=\\{w\\}$, then
$N_{G^{*}}(w)\subseteq A_{1}$. We can see that $N_{G^{*}}(w)=A_{1}$. Indeed,
if there exists a vertex $v\in A_{1}$ with $vw\notin E(G^{*})$, then
$\max\\{d_{G^{*}}(v),d_{G^{*}}(w)\\}\leq t-2$. So,
$\Delta(G^{*}+vw)=\Delta(G^{*})=t-1$, and thus, $G^{*}+vw$ also contains no
$K_{1,t}$. However, $\rho(G^{*}+vw)>\rho(G^{*})$, a contradiction.

Recall that $A_{1}=\\{v\in A|d_{A}(v)\leq t-3\\}$. We now claim that
$d_{A}(v)=t-3$ for any $v\in A_{1}$. Suppose that $d_{A}(v_{0})\leq t-4$ for
some $v_{0}\in A_{1}$ and let $v_{1}\in\overline{N}_{A}(v_{0})$. Then
$d_{A}(v_{1})\leq t-3$, and thus $v_{1}\in A_{1}=N_{G^{*}}(w)$. Furthermore,
$d_{A}(v_{1})=t-3$ (Otherwise, $\Delta(G^{*}+v_{0}v_{1})=\Delta(G^{*})$ and
$\rho(G^{*}+v_{0}v_{1})>\rho(G^{*})$). By Corollary LABEL:le004, we have
$x_{w}\leq x_{v_{0}}$. Now let
$G^{\prime}=G^{*}-\\{wv_{1}\\}+\\{v_{0}v_{1}\\}$. Then
$\Delta(G^{\prime})=\Delta(G^{*})$, and since $v_{0}\in A_{1}=N_{G^{*}}(w)$,
$G^{\prime}$ is still a connected graph. However, by Lemma 5.1, we get
$\rho(G^{\prime})>\rho(G^{*})$, a contradiction. So, $d_{A}(v)=t-3$ for any
$v\in A_{1}$. Note that each vertex in $A_{0}$ dominates $A$. The above claim
implies that $G^{*}[A_{1}]$ is isomorphic to $K_{|A_{1}|}$ by deleting a
perfect matching. Hence, $|A_{1}|$ is even.

It is known that $\rho(G)\leq\Delta(G)$ for any connected graph $G$, with
equality if and only if $G$ is $\Delta$-regular. Now, $G^{*}$ is $t-1$-regular
if and only if $A_{1}=A$. It follows that if $t+1$ is even, then $A_{1}=A$,
and thus $\overline{G^{*}}$ is the union of $\frac{t+1}{2}$ independent edges,
that is, $u^{*}w$ and others within $A$.

If $t+1$ is odd, then $|A|=t-1$ is also odd, and since $|A_{1}|$ is even, we
have $|A_{1}|<|A|$ (see Fig. 5). By symmetry, $x_{v}=x_{u^{*}}$ for any $v\in
A_{0}$, and we may let $x_{v}=x_{1}$ for any $v\in A_{1}$. Thus, $\rho
x_{w}=|A_{1}|x_{1},$ $\rho x_{u^{*}}=|A_{1}|x_{1}+|A_{0}|x_{u^{*}}$ and

$\rho x_{1}=(|A_{1}|-2)x_{1}+(|A_{0}|+1)x_{u^{*}}+x_{w}.$

Note that $|A_{0}|+|A_{1}|=|A|=t-1$. Solving above equations, we get

$\displaystyle\rho^{3}-(t-3)\rho^{2}-(2t-2)\rho+|A_{0}||A_{1}|=0.$ (21)

Since $|A_{1}|$ is even and $t+1$ is odd, we have $2\leq|A_{1}|\leq t-2$ and
$t\geq 4$. Thus,

$|A_{0}||A_{1}|\geq\min\\{2(t-3),t-2\\}=t-2,$

with $|A_{0}||A_{1}|=t-2$ if and only if $|A_{1}|=t-2$. Since $\rho$ is the
maximum spectral radius, by (21) we can see that $|A_{0}||A_{1}|$ must attain
its minimum. Therefore, $|A_{1}|=t-2$ and thus $|A_{0}|=1$. Now,
$\overline{G^{*}}$ is the union of $\frac{n-3}{2}$ independent edges with all
endpoints in $A_{1}$, and a path $u^{*}wv$ with $v\in A_{0}$. This completes
the proof. ∎

$A_{1}$$A_{0}$$u^{*}$$w$ Figure 5: The extremal graph $G^{*}$ for odd $n=t+1$.

Now we consider the case $n\geq t+2$. Recall that $S^{k}(G)$ denotes a graph
obtained from $G$ by subdividing $k$ times of one edge.

######  Theorem 5.2.

If $n\geq t+2$, then $G^{*}\cong S^{n-t}(K_{t})$.

###### Proof.

Observe that a graph $G$ is $K_{1,3}$-minor free if and only if $\Delta(G)\leq
2$. Therefore, if $t=3$, then $G^{*}\cong C_{n}$, in other words, $G^{*}\cong
S^{n-3}(K_{3})$. Next, let $t\geq 4$. The proof is divided into several
claims.

######  Claim 5.1.

$|A_{1}|\geq|N^{2}(u^{*})|\geq 2$.

###### Proof.

Since $|A|=t-1$ and $n\geq t+2$, we have $N^{2}(u^{*})\neq\varnothing$. We
first show $|N^{2}(u^{*})|\geq 2$. Suppose to the contrary that
$N^{2}(u^{*})=\\{w_{0}\\}$. By Lemma 5.3, we have $d_{B}(w_{0})\leq 1$, and
$d_{B}(w)\leq 2$ for each $w\in B$. Since $G^{*}$ is connected, $G^{*}[B]$ is
a pendant path $P=w_{0}w_{1}\cdots w_{n-t-1}$. Take an arbitrary vertex
$v_{0}\in N_{A}(w_{0})$. If $\overline{N}_{A}(w_{0})\subseteq
N_{G^{*}}(v_{0})$, then $|N_{G^{*}}(v_{0})\cup
N_{G^{*}}(w_{0})|=|A\cup\\{u^{*},w_{0},w_{1}\\}|=t+2$. Hence, $G^{*}$ contains
a double star with a non-pendant edge $v_{0}w_{0}$ and $t$ leaves, a
contradiction. Thus, there exists a vertex
$v_{1}\in\overline{N}_{A}(w_{0})\cap\overline{N}_{G^{*}}(v_{0})$. Then
$d_{G^{*}}(v_{1})\leq t-2$.

Now, let $G^{\prime}=G^{*}+\\{v_{1}w_{n-t+1}\\}$ and $G^{\prime\prime}$ be the
graph obtained from $G^{\prime}$ by contracting the path
$w_{0}w_{1}w_{2}\cdots w_{n-t-1}v_{1}$ into an edge $w_{0}v_{1}$. Clearly,
$|G^{\prime\prime}|=t+1$ and
$\Delta(G^{\prime\prime})=\Delta(G^{\prime})=\Delta(G^{*})=t-1$. Therefore,
$G^{\prime\prime}$ is $K_{1,t}$-minor free, and thus $G^{\prime}$ is too.
However, $\rho(G^{\prime})>\rho(G^{*})$, a contradiction. So
$|N^{2}(u^{*})|\geq 2$. Furthermore, by Lemma 5.3 (i), we have
$|A_{1}|\geq|N^{2}(u^{*})|$. ∎

Now let $A_{11}=\\{v\in A_{1}|d_{A}(v)\leq t-4\\}$. Since $n\geq t+2$, we have
$|B|\geq 2$. So we may assume that $w^{\prime},w^{\prime\prime}\in B$ with
$x_{w^{\prime}}=\max\limits_{w\in B}x_{w}$ and
$x_{w^{\prime\prime}}=\max\limits_{w\in B\setminus\\{w^{\prime}\\}}x_{w}$.

######  Claim 5.2.

If $d_{B}(v_{0})=0$ for some $v_{0}\in A_{1}$, then
$x_{w^{\prime}}+x_{w^{\prime\prime}}\leq x_{u^{*}}+\sum\limits_{v\in
A_{11}}x_{v}.$

###### Proof.

We first show $w^{\prime}\in N^{2}(u^{*})$. Otherwise, $w^{\prime}\in
B\setminus N^{2}(u^{*})$. By Lemma 5.3, $d_{B}(w^{\prime})\leq 2$, and hence,
$\rho x_{w^{\prime}}=\sum_{w\in N_{B}(w^{\prime})}x_{w}\leq 2x_{w^{\prime}}$.
It follows that $\rho\leq 2$, which contradicts Lemma 5.2 as $t\geq 4$. Since
$w^{\prime}\in N^{2}(u^{*})$, we have $d_{B}(w^{\prime})\leq 1$ and

$\displaystyle\rho x_{w^{\prime}}\leq x_{w^{\prime\prime}}+\sum_{v\in
N_{A}(w^{\prime})}x_{v}.$ (22)

If $w^{\prime\prime}\in B\setminus N^{2}(u^{*})$, then
$d_{B}(w^{\prime\prime})\leq 2$ and hence $\rho x_{w^{\prime\prime}}\leq
x_{w^{\prime}}+x_{w^{\prime\prime}}$, which implies

$\displaystyle x_{w^{\prime\prime}}\leq\frac{x_{w^{\prime}}}{\rho-1}.$ (23)

Combining with (22), we have

$\displaystyle
x_{w^{\prime}}\leq\frac{\rho-1}{\rho^{2}-\rho-1}\sum\limits_{v\in
N_{A}(w^{\prime})}x_{v}.$ (24)

Furthermore, by Claim 5.1, $|N^{2}(u^{*})|\geq 2$. Hence, there exist a vertex
$w\in N^{2}(u^{*})\setminus\\{w^{\prime}\\}$ and a vertex $v$ in
$N_{A}(w)\setminus N_{A}(w^{\prime})$. So,
$d_{A}(w^{\prime})\leq|A\setminus\\{v,v_{0}\\}|=t-3$. Combining it with (23)
and (24), we have

$x_{w^{\prime}}+x_{w^{\prime\prime}}\leq\frac{\rho}{\rho-1}x_{w^{\prime}}\leq\frac{\rho}{\rho^{2}-\rho-1}\sum\limits_{v\in
N_{A}(w^{\prime})}x_{v}\leq\frac{(t-3)\rho}{\rho^{2}-\rho-1}x_{u^{*}}.$

Note that (20) implies $\rho^{2}-\rho-1>(t-3)\rho$. So,
$x_{w^{\prime}}+x_{w^{\prime\prime}}<x_{u^{*}}$, as desired.

Now assume that $w^{\prime\prime}\in N^{2}(u^{*})$. By Lemma 5.3,
$d_{B}(w^{\prime\prime})\leq 1$ and thus $\rho x_{w^{\prime\prime}}\leq
x_{w^{\prime}}+\sum_{v\in N_{A}(w^{\prime\prime})}x_{v}$. Combining with (22),
we have

$\displaystyle\rho(x_{w^{\prime}}+x_{w^{\prime\prime}})\leq(x_{w^{\prime}}+x_{w^{\prime\prime}})+\sum_{v\in
N_{A}(w^{\prime})\cup N_{A}(w^{\prime\prime})}x_{v},$ (25)

since $N_{A}(w^{\prime})\cap N_{A}(w^{\prime\prime})=\varnothing$ by Lemma
5.3. Moreover,

$|N_{A}(w^{\prime})\cup
N_{A}(w^{\prime\prime})|\leq|A\setminus\\{v_{0}\\}|=t-2.$

If $|N_{A}(w^{\prime})\cup N_{A}(w^{\prime\prime})|\leq t-3$, then by (25), we
have
$x_{w^{\prime}}+x_{w^{\prime\prime}}\leq\frac{t-3}{\rho-1}x_{u^{*}}<x_{u^{*}}$.
If $d_{A}(v_{1})\leq t-4$ for some $v_{1}\in N_{A}(w^{\prime})\cup
N_{A}(w^{\prime\prime})$, then $v_{1}\in A_{11}$ and

$x_{w^{\prime}}+x_{w^{\prime\prime}}\leq\frac{t-3}{\rho-1}x_{u^{*}}+x_{v_{1}}<x_{u^{*}}+\sum_{v\in
A_{11}}x_{v}.$

Next we may assume that $|N_{A}(w^{\prime})\cup N_{A}(w^{\prime\prime})|=t-2$
and $d_{A}(v)=t-3$ for any $v\in N_{A}(w^{\prime})\cup
N_{A}(w^{\prime\prime})$. Now $N_{A}(w^{\prime})\cup
N_{A}(w^{\prime\prime})=A\setminus\\{v_{0}\\}$. Since $v_{0}\in A_{1}$,
$d_{A}(v_{0})\leq t-3$ and thus $v_{0}$ has a non-neighbor $v_{1}\in
N_{A}(w^{\prime})\cup N_{A}(w^{\prime\prime})$. Therefore, $d_{A}(v_{1})=t-3$,
and $v_{1}$ dominates $N_{A}(w^{\prime})\cup N_{A}(w^{\prime\prime})$. Let
$v_{1}v_{2}$ be an edge between $N_{A}(w^{\prime})$ and
$N_{A}(w^{\prime\prime})$. Then $v_{0}$ is also a non-neighbor of $v_{2}$
(Otherwise, $|N_{G^{*}}(v_{1})\cup
N_{G^{*}}(v_{2})|=|A\cup\\{u^{*},w^{\prime},w^{\prime\prime}\\}|=t+2$ and we
get a $K_{1,t}$-minor). Now we see that $d_{A}(v_{0})\leq t-4$ and thus
$v_{0}\in A_{11}$. On the other hand, by Lemma 5.4, we have
$x_{w^{\prime\prime}}\leq x_{v_{0}}$. It follows that
$x_{w^{\prime}}+x_{w^{\prime\prime}}\leq x_{u^{*}}+\sum_{v\in A_{11}}x_{v}.$ ∎

######  Claim 5.3.

$d_{B}(v)=1$ for each vertex $v\in A_{1}$, and thus $e(A,B)=|A_{1}|$.

###### Proof.

By Lemma 5.3, $d_{B}(v)\leq 1$ for each vertex $v\in A_{1}$. Suppose that
$d_{B}(v_{0})=0$ for some $v_{0}\in A_{1}$. We can see that $\rho
x_{u^{*}}=\sum\limits_{v\in A}x_{v}$ and

$\displaystyle\rho^{2}x_{u^{*}}=\sum\limits_{v\in A}\sum\limits_{u\in
N_{G^{*}}(v)}x_{u}=|A|x_{u^{*}}+\sum\limits_{v\in
A}d_{A}(v)x_{v}+\sum\limits_{w\in B}d_{A}(w)x_{w}.$ (26)

From (26) and the definitions of $A_{0}$ and $A_{11}$, we have

$\displaystyle(\rho^{2}-(t-3)\rho)x_{u^{*}}$ $\displaystyle=$
$\displaystyle\rho^{2}x_{u^{*}}-(t-3)\sum\limits_{v\in A}x_{v}$ (27)
$\displaystyle=$ $\displaystyle|A|x_{u^{*}}+\sum\limits_{v\in
A}(d_{A}(v)-t+3)x_{v}+\sum\limits_{w\in B}d_{A}(w)x_{w}$ $\displaystyle\leq$
$\displaystyle|A|x_{u^{*}}+\sum\limits_{v\in A_{0}}x_{v}-\sum\limits_{v\in
A_{11}}x_{v}+\sum\limits_{w\in B}d_{A}(w)x_{w}$ $\displaystyle\leq$
$\displaystyle(|A|+|A_{0}|+e(A,B)-2)x_{u^{*}}+x_{w^{\prime}}+x_{w^{\prime\prime}}-\sum\limits_{v\in
A_{11}}x_{v}.$

Combining Claim 5.2 with $(\ref{a006})$, we have

$(\rho^{2}-(t-3)\rho)x_{u^{*}}\leq(|A|+|A_{0}|+e(A,B)-1)x_{u^{*}}.$

Recall that $d_{B}(v)=0$ for any $v\in A_{0}$, and $d_{B}(v)\leq 1$ for any
$v\in A_{1}$. Therefore,

$e(A,B)=e(A_{1},B)=\sum\limits_{v\in
A_{1}\setminus\\{v_{0}\\}}d_{B}(v)\leq|A_{1}\setminus\\{v_{0}\\}|=|A_{1}|-1.$

It follows that $\rho^{2}-(t-3)\rho\leq 2(|A|-1)=2(t-2),$ which contradicts
(20). So, $d_{B}(v)=1$ for any $v\in A_{1}$ and thus
$e(A,B)=e(A_{1},B)=|A_{1}|$. ∎

######  Claim 5.4.

$|A_{11}|\leq 2$.

###### Proof.

Suppose to the contrary that $|A_{11}|\geq 3$. Then $|A\setminus A_{11}|\leq
t-4$, and thus

$\rho x_{u^{*}}=\sum\limits_{v\in A_{11}}x_{v}+\sum\limits_{v\in A\setminus
A_{11}}x_{v}\leq\sum\limits_{x\in A_{11}}x_{v}+(t-4)x_{u^{*}}.$

Therefore, by Lemma 5.2, we have

$\displaystyle\sum\limits_{v\in A_{11}}x_{v}\geq(\rho-t+4)x_{u^{*}}\geq
2x_{u^{*}}.$ (28)

Combining with (27) and (28), we have

$\displaystyle(\rho^{2}-(t-3)\rho)x_{u^{*}}$ $\displaystyle\leq$
$\displaystyle|A|x_{u^{*}}+\sum\limits_{v\in A_{0}}x_{v}-\sum\limits_{v\in
A_{11}}x_{v}+\sum\limits_{w\in B}d_{A}(w)x_{w}$ $\displaystyle\leq$
$\displaystyle(|A|+|A_{0}|-2)x_{u^{*}}+e(A,B)x_{u^{*}}.$

By Claim 5.3, we have $e(A,B)=|A_{1}|$. Hence,

$\rho^{2}-(t-3)\rho\leq(|A|+|A_{0}|+|A_{1}|-2)=2|A|-2=2(t-2),$

which contradicts (20). Thus, $|A_{11}|\leq 2$, as claimed. ∎

######  Claim 5.5.

If $|A_{1}|\geq 3$, then $A_{10}$ is a clique, where $A_{10}=\\{v\in
A|d_{A}(v)=t-3\\}$.

###### Proof.

Recall that $A_{11}=\\{v\in A|d_{A}(v)\leq t-4\\}$. Then
$A_{10}=A_{1}\setminus A_{11}.$ Suppose to the contrary that there exist two
non-adjacent vertices $v_{1},v_{2}\in A_{10}$. Since
$d_{A}(v_{1})=d_{A}(v_{2})=t-3$, both $v_{1}$ and $v_{2}$ dominate
$A\setminus\\{v_{1},v_{2}\\}$. Since $|A_{1}|\geq 3$, we can take a vertex
$v_{3}\in A_{1}\setminus\\{v_{1},v_{2}\\}$. Furthermore, by Claim 5.3, there
exists a unique vertex $w_{i}\in N_{B}(v_{i})$ for $i\in\\{1,2,3\\}$. If
$w_{3}\not=w_{1}$, then

$|N_{G^{*}}(v_{1})\cup
N_{G^{*}}(v_{3})|\geq|A\cup\\{u^{*},w_{1},w_{3}\\}|=t+2.$

If $w_{3}\not=w_{2}$, then we similarly have $|N_{G^{*}}(v_{2})\cup
N_{G^{*}}(v_{3})|\geq t+2.$ If $w_{1}=w_{2}=w_{3}$, then by Claim 5.1,
$|N^{2}(u^{*})|\geq 2$ and thus there exist a vertex $w_{4}\in
N^{2}(u^{*})\setminus\\{w_{1}\\}$ and a vertex $v_{4}\in N_{A}(w_{4})$. It
follows that

$|N_{G^{*}}(v_{1})\cup
N_{G^{*}}(v_{4})|\geq|A\cup\\{u^{*},w_{1},w_{4}\\}|=t+2.$

Thus we always find a $K_{1,t}$-minor, a contradiction. ∎

Now we are ready to give the final proof of the theorem. By Claim 5.1,
$|A_{1}|\geq|N^{2}(u^{*})|\geq 2$. If $|A_{1}|=2$, then $|N^{2}(u^{*})|=2$,
and $G^{*}[A\cup\\{u^{*}\\}]\cong K_{t}-e$, where the unique non-edge lies in
$A_{1}$. Now we can see that $d_{A}(w)=1$ and $d_{B}(w)\leq 1$ for each $w\in
N^{2}(u^{*})$. Moreover, $d_{B}(w)\leq 2$ for any $w\in B\setminus
N^{2}(u^{*})$. Since $G^{*}$ is an extremal graph, we can observe that
$G^{*}[A_{1}\cup B]$ is a path with both endpoints in $A_{1}$. This implies
that $G^{*}\cong S^{n-t}(K_{t})$, as desired.

It remains the case $|A_{1}|\geq 3$. We shall prove that this is impossible.
By Claim 5.4, $|A_{11}|\leq 2$. Suppose that $|A_{11}|=|\\{v_{1},v_{2}\\}|=2$.
For $i\in\\{1,2\\}$, since $d_{A}(v_{i})\leq t-4$, $v_{i}$ has at least one
non-neighbor $v^{\prime}_{i}\in A_{10}$. By the definition of $A_{10}$,
$d_{A}(v^{\prime}_{1})=d_{A}(v^{\prime}_{2})=t-3$, and hence
$v^{\prime}_{1}\not=v^{\prime}_{2}$. By Claim 5.3, there exists a unique
vertex $w_{i}\in N_{B}(v^{\prime}_{i})$ for $i\in\\{1,2\\}$ (Possibly,
$w_{1}=w_{2}$). And by Lemma 5.4, $x_{w_{i}}\leq x_{v_{i}}$ for
$i\in\\{1,2\\}$. Thus, $x_{w_{1}}+x_{w_{2}}\leq x_{v_{1}}+x_{v_{2}}=\sum_{v\in
A_{11}}x_{v}$. Recall that $e(A,B)=|A_{1}|$. Then by $(\ref{a006})$,

$\displaystyle(\rho^{2}-(t-3)\rho)x_{u^{*}}$ $\displaystyle\leq$
$\displaystyle(|A|+|A_{0}|+e(A,B)-2)x_{u^{*}}+x_{w_{1}}+x_{w_{2}}-\sum\limits_{v\in
A_{11}}x_{v}$ $\displaystyle\leq$
$\displaystyle(|A|+|A_{0}|+|A_{1}|-2)x_{u^{*}}$ $\displaystyle=$
$\displaystyle 2(t-2))x_{u^{*}},$

a contradiction with (20). Thus $|A_{11}|\leq 1$.

According to Claim 5.5, $A_{10}$ is a clique. Recall that $A_{10}=\\{v\in
A|d_{A}(v)=t-3\\}$. Therefore, each vertex $v\in A_{10}$ has a non-neighbor
$v_{0}\in A_{11}$. And since $|A_{11}|\leq 1$, we have that
$A_{11}=\\{v_{0}\\}$ and $e(\\{v_{0}\\},A_{10})=0$. Let
$A_{10}=\\{v_{1},v_{2},\ldots,v_{|A_{10}|}\\}$. By Claim 5.3, there exists a
unique vertex $w_{i}\in N_{B}(v_{i})$ for each $v_{i}\in A_{1}$ (Possibly,
$w_{i}=w_{j}$ for some $i\neq j$). Since $|N^{2}(u^{*})|\geq 2$ and $G^{*}[B]$
consists of disjoint paths, we may assume without loss of generality that

(i) $w_{|A_{10}|}\not=w_{0}$;

(ii) if $|N^{2}(u^{*})|\geq 3$, then $w_{0}$ and $w_{|A_{10}|}$ belong to two
distinct paths of $G^{*}[B]$.

Note that $|A_{1}|\geq 3$, then $|A_{10}|=|A_{1}|-|A_{11}|\geq 2$. Let

$G^{\prime}=G^{*}-\\{v_{i}w_{i}|i=1,2,\ldots,|A_{10}|-1\\}+\\{v_{i}v_{0}|i=1,2,\ldots,|A_{10}|-1\\}.$

By Lemma 5.4, $x_{w_{i}}\leq x_{v_{0}}$ for each $w_{i}\in A_{10}$.
Furthermore, by Lemma 5.1 we have $\rho(G^{\prime})>\rho(G^{*})$. We can
observe that $G^{\prime}[A\cup\\{u^{*}\\}]\cong K_{t}-e$, where the unique
non-edge is $v_{0}v_{|A_{10}|}$. Moreover, $G^{\prime}[B]$ is still the
disjoint union of paths, and the only edges between $A$ and $B$ are
$v_{0}w_{0}$ and $v_{|A_{10}|}w_{|A_{10}|}$. These observations imply that
$G^{\prime}$ is a subgraph of $S^{n-t}(K_{t})$. It follows that
$\rho(S^{n-t}(K_{t}))\geq\rho(G^{\prime})>\rho(G^{*})$, a contradiction. This
completes the proof. ∎

Recall that $H_{1,t}$ is a star forest of order $t+1$, precisely, the disjoint
union of $\lfloor\frac{t+1}{2}\rfloor$ stars in which all but at most one are
isomorphic to $K_{1,1}$. By Theorems 5.1 and 5.2, we complete the proof of
Theorem 1.3. Furthermore, we know that for any connected graph $G$,
$\rho(G)\leq\Delta(G)$, with equality if and only if $G$ is a $\Delta$-regular
graph. One can see that Theorem 1.4 is a direct corollary of Theorem 1.3.

## References

  * [1] L. Babai, B. Guiduli, Spectral extrema for graphs: the Zarankiewicz problem, _Electron. J. Combin._ 16 (2009) no. 1, Research Paper 123, 8 pp.
  * [2] B. Bollobás, V. Nikiforov, Cliques and the spectral radius, _J. Combin. Theory Ser. B_ 97 (2007) 859–865.
  * [3] B.N. Boots, G.F. Royle, A conjecture on the maximum value of the principal eigenvalue of a planar graph, _Geogr. Anal._ 23 (1991) 276–282.
  * [4] D.S. Cao, A. Vince, The spectral radius of a planar graph, _Linear Algebra Appl._ 187 (1993) 251–257.
  * [5] S. Cioabă, D.N. Desai, M. Tait, The spectral radius of graphs with no odd wheels, arXiv:2104.07729v1.
  * [6] S. Cioabă, L.H. Feng, M. Tait, X.D. Zhang, The maximum spectral radius of graphs without friendship subgraphs, _Electron. J. Combin._ 27 (2020) no. 4, Research Paper 4.22, 19 pp.
  * [7] M.Z. Chen, A M. Liu, X.D. Zhang, On the spectral radius of graphs without a star forest, _Discrete Math._ 344 (2021), no. 4, 112269, 12 pp.
  * [8] M.Z. Chen, A M. Liu, X.D. Zhang, Spectral extremal results with forbidding linear forests, _Graphs Combin._ 35 (2019) 335–351.
  * [9] M. Chudnovsky, B. Reed, P. Seymour, The edge-density for $K_{2,t}$ minors, _J. Combin. Theory Ser. B_ 101 (2011) 18–46.
  * [10] D. Cvetković, P. Rowlinson, The largest eigenvalue of a graph: A survey, _Linear Multilinear Algebra_ 28 (1990) 3–33.
  * [11] G. Ding, T. Johnson, P. Seymour, Spanning trees with many leaves, _J. Graph Theory_ 37 (2001) 189–197.
  * [12] M.N. Ellingham, X.Y. Zha, The spectral radius of graphs on surfaces, _J. Combin. Theory Ser. B_ 78 (2000) 45–56.
  * [13] L.H. Feng, G.H. Yu, X.D. Zhang, Spectral radius of graphs with given matching number, _Linear Algebra Appl._ 422 (2007) 133–138.
  * [14] Z. Füredi, M. Simonovits, The history of degenerate (bipartite) extremal graph problems, _Bolyai Soc. Studies (The Erdös Centennial)_ 25 (2013) 167–262.
  * [15] J. Gao, X.M. Hou, The spectral radius of graphs without long cycles, _Linear Algebra Appl._ 566 (2019) 17–33.
  * [16] Y. Hong, On the spectral radius and the genus of graphs, _J. Combin. Theory Ser. B_ 65 (1995) 262–268.
  * [17] Y. Hong, Sharp upper bounds of the spectral radius of graphs in terms of genus, _J. Combin. Theory Ser. B_ 74 (1998) 153–159.
  * [18] Y. Hong, Tree-width, clique-minors, and eigenvalues, _Discrete Math._ 274 (2004) 281–287.
  * [19] B.L. Li, B. Ning, The stability method, eigenvalues and cycles of consecutive lengths, arXiv:2102.03855.
  * [20] H.Q. Lin, B. Ning, A complete solution to the Cvetković-Rowlinson conjecture, _J. Graph Theory_ (2021) 1–10.
  * [21] Y. Li, Y. Peng, The spectral radius of graphs with no intersecting odd cycles, arXiv:2106.00587.
  * [22] W. Mantel, Problem 28, soln. by H. Gouventak, W. Mantel, J. Teixeira de Mattes, F. Schuh and W.A. Wythoff, _Wiskundige Opgaven_ 10 (1907) 60–61.
  * [23] B. Ning, X. Peng, Extensions of the Erdős-Gallai theorem and Luo’s theorem, _Combin. Probab. Comput._ 29 (2020) 128–136.
  * [24] V. Nikiforov, The spectral radius of graphs with no $K_{2,t}$-minor, _Linear Algebra Appl._ 531 (2017) 510–515.
  * [25] V. Nikiforov, A spectral condition for odd cycles in graphs, _Linear Algebra Appl._ 428 (2008) 1492–1498.
  * [26] V. Nikiforov, Some new results in extremal graph theory: In surveys in Combinatorics 2011, _London Math. Society Lecture Note Ser._ 392 (2011) 141–181.
  * [27] V. Nikiforov, The spectral radius of graphs without paths and cycles of specified length, _Linear Algebra Appl._ 432 (2010) 2243–2256.
  * [28] V. Nikiforov, Bounds on graph eigenvalues II, _Linear Algebra Appl._ 427 (2007) 183–189.
  * [29] V. Nikiforov, A contribution to the Zarankiewicz problem, _Linear Algebra Appl._ 432 (2010) 1405–1411.
  * [30] J.L. Shu, Y. Hong, Upper bounds for the spectral radii of outerplanar graphs and Halin graphs, _Chinese Ann. Math. Ser. A_ 21 (2000), no.6, 677–682.
  * [31] M. Tait, J. Tobin, Three conjectures in extremal spectral graph theory, _J. Combin. Theory Ser. B_ 126 (2017) 137–161.
  * [32] M. Tait, The Colin de Verdière parameter, excluded minors, and the spectral radius, _J. Combin. Theory Ser. A_ 166 (2019) 42–58.
  * [33] P. Turán, On an extremal problem in graph theory, _Mat. Fiz. Lapok_ 48 (1941) 436–452.
  * [34] T. Bıyıkoǧlu, J. Leydold, Graphs with given degree sequence and maximal spectral radius, _Electron. J. Combin._ 15 (2008), no. 1, Research Paper 119, 9 pp.
  * [35] B. Wang, W. Chen, L. Fang, Extremal spectral radius of $K_{3,3}/K_{2,4}$-minor free graphs, _Linear Algebra Appl._ 628 (2021) 103–114.
  * [36] H. Wilf, Spectral bounds for the clique and independence numbers of graphs, _J. Combin. Theory Ser. B_ 40 (1986) 113–117.
  * [37] B.F. Wu, E.L. Xiao, Y. Hong, The spectral radius of trees on $k$ pendant vertices, _Linear Algebra Appl._ 395 (2005) 343–349.
  * [38] M.Q. Zhai, H.Q. Lin, Spectral extrema of graphs: forbidden hexagon, _Discrete Math._ 343 (2020), no. 10, 112028, 6 pp.
  * [39] M.Q. Zhai, H.Q. Lin, A strengthening of the spectral color critical edge theorem: books and theta graphs, arXiv:2102.04041.
  * [40] M.Q. Zhai, B. Wang, Proof of a conjecture on the spectral radius of $C_{4}$-free graphs, _Linear Algebra Appl._ 437 (2012) 1641–1647.
  * [41] X.Z. Zhan, Matrix theory, Graduate Studies in Mathematics, 147. American Mathematical Society, Providence, RI, 2013. x+253 pp.
  * [42] Z. Dvořák, B. Mohar, Spectral radius of finite and infinite planar graphs and of graphs of bounded genus, _J. Combin. Theory Ser. B_ 100 (2010), no. 6, 729–739.