# A general theorem in spectral extremal graph theory

John Byrne University of Delaware, Department of Mathematical Sciences,
<EMAIL_ADDRESS>Dheer Noal Desai University of Wyoming, Department of
Mathematics and Statistics. The University of Memphis, Department of
Mathematical Sciences<EMAIL_ADDRESS>Michael Tait Villanova University,
Department of Mathematics & Statistics<EMAIL_ADDRESS>Research
partially supported by NSF grant DMS-2245556.

###### Abstract

The extremal graphs $\mathrm{EX}(n,\mathcal{F})$ and spectral extremal graphs
$\mathrm{SPEX}(n,\mathcal{F})$ are the sets of graphs on $n$ vertices with
maximum number of edges and maximum spectral radius, respectively, with no
subgraph in $\mathcal{F}$. We prove a general theorem which allows us to
characterize the spectral extremal graphs for a wide range of forbidden
families $\mathcal{F}$ and implies several new and existing results. In
particular, whenever $\mathrm{EX}(n,\mathcal{F})$ contains the complete
bipartite graph $K_{k,n-k}$ (or certain similar graphs) then
$\mathrm{SPEX}(n,\mathcal{F})$ contains the same graph when $n$ is
sufficiently large. We prove a similar theorem which relates
$\mathrm{SPEX}(n,\mathcal{F})$ and $\mathrm{SPEX}_{\alpha}(n,\mathcal{F})$,
the set of $\mathcal{F}$-free graphs which maximize the spectral radius of the
matrix $A_{\alpha}=\alpha D+(1-\alpha)A$, where $A$ is the adjacency matrix
and $D$ is the diagonal degree matrix.

##  1 Introduction

For a family of graphs $\mathcal{F}$ and $\alpha\in[0,1)$, we define
$\mathrm{ex}(n,\mathcal{F})$, $\mathrm{spex}(n,\mathcal{F})$, and
$\mathrm{spex}_{\alpha}(n,\mathcal{F})$ to be the maximum number of edges,
maximum spectral radius of the adjacency matrix, and maximum spectral radius
of the matrix $A_{\alpha}$ respectively over all $n$-vertex graphs which do
not contain any $F\in\mathcal{F}$ as a subgraph. Here $A_{\alpha}=\alpha
D+(1-\alpha)A$ where $D$ is the diagonal degree matrix and $A$ is the
adjacency matrix. So
$\mathrm{spex}(n,\mathcal{F})=\mathrm{spex}_{0}(n,\mathcal{F})$ and
$\mathrm{spex}_{1/2}(n,\mathcal{F})$ is one half of the maximum spectral
radius of the signless Laplacian over $\mathcal{F}$-free graphs. As is
standard, we define $\mathrm{EX}(n,\mathcal{F})$,
$\mathrm{SPEX}(n,\mathcal{F})$, and $\mathrm{SPEX}_{\alpha}(n,\mathcal{F})$ as
the set of extremal graphs for each respective function, and we call the
graphs in each set (edge) extremal, spectral extremal, and alpha spectral
extremal, respectively. When $\mathcal{F}=\\{F\\}$ is a single graph we use
the standard notation $\mathrm{ex}(n,F)$ instead of $\mathrm{ex}(n,\\{F\\})$
and similarly with the other functions. If the family of extremal graphs
consists of a single graph $H$ we will write $\mathrm{EX}(n,\mathcal{F})=H$
instead of $\mathrm{EX}(n,\mathcal{F})=\\{H\\}$, and similarly with the other
functions. Our goal in this paper is to prove general theorems which capture
many previous and new results on these parameters.

Spectral extremal graph theory has become very popular recently. Several
sporadic results appeared over the years, for example results of Wilf [59] and
Nosal [54], before the field was studied systematically. All results in the
area which regard the adjacency matrix can be understood under the general
framework of Brualdi-Solheid problems [4], where one seeks to maximize the
spectral radius of the adjacency matrix over a family of graphs. When the
family is defined by a forbidden subgraph, this problem has a Turán-type
flavor, and the spectral Turán problem was introduced systematically by
Nikiforov [50]. Since then many papers have been written, and we refer to the
excellent recent survey [41]. We also note that there are hypergraph versions
of these problems (see for example [37, 52]), but we only consider graphs in
this paper.

Researchers have also frequently considered other matrices besides the
adjacency matrix. Signless Laplacian versions of Brualdi-Solheid problems were
studied extensively and Nikiforov introduced the $A_{\alpha}$ matrix as a way
to merge these two theories [53].

With so much recent activity in this area, we believe that it is valuable to
have general theorems that apply to families of forbidden graphs. One question
that naturally presents itself when reviewing previous results is: when are
the edge-extremal graphs the same as the spectral-extremal graphs? That is,
when do $\mathrm{EX}(n,F)$ and $\mathrm{SPEX}_{\alpha}(n,F)$ either coincide
or overlap?

Some of the first results in the area suggest that perhaps the problems are
the same. For example, the spectral Turán theorem [47] shows
$\mathrm{EX}(n,K_{r+1})=\mathrm{SPEX}(n,K_{r+1})$, and [48] shows that
$\mathrm{EX}(n,C_{2k+1})=\mathrm{SPEX}(n,C_{2k+1})=K_{n/2,n/2}$ for large
enough $n$. Furthermore, for any non-bipartite $F$, the theorems in [21, 22,
49] show that the asymptotics of the two functions coincide. However, the two
problems can also be vastly different, for example when $F$ is an even cycle
[13, 50, 61, 62]. One might then guess that there is a difference between $F$
bipartite and non-bipartite, but it is a bit more subtle than that. In [15],
it was shown that when forbidding large enough odd wheels the two extremal
families have similar structure but are in fact disjoint.

Hence we seek general criteria which can determine whether the extremal
families overlap or not. One such very nice result is in [58], proving a
conjecture in [15], where it was shown that for any graph $F$ such that any
graph in $\mathrm{EX}(n,F)$ is a Turán graph plus $O(1)$ edges, then for large
enough $n$ one has that $\mathrm{SPEX}(n,F)\subseteq\mathrm{EX}(n,F)$. Another
very nice paper proving general results about trees was written [23].

In this paper we prove some general results which apply to many forbidden
graphs or families. As special cases of our theorems, we recover results from
[7, 8, 9, 10, 11, 12, 14, 16, 23, 27, 28, 35, 39, 40, 43, 44, 50, 55, 56, 60,
64, 65] and additionally we can apply the theorems to prove several new
results. More details about specific applications are given after statements
of our theorems.

When studying a classical Turán-type problem, every edge increases the
objective function by the same amount. But when trying to determine
$\mathrm{spex}(n,F)$, some edges will contribute more to the spectral radius
than others, and so vertices of large degree are incentivized. When
$\alpha>0$, the presence of the diagonal degree matrix incentivizes large
degree vertices even further. This paper is an attempt to formalize this
phenomenon.

The rest of this paper is organized as follows. In the rest of Section 1 we
define our notation and state our main results. In Section 2 we prove results
relating $\mathrm{EX}(n,\mathcal{F})$ and $\mathrm{SPEX}(n,\mathcal{F})$. In
Section 3, we prove results relating $\mathrm{SPEX}(n,\mathcal{F})$ and
$\mathrm{SPEX}_{\alpha}(n,\mathcal{F})$. In Section 4 we give concluding
remarks.

###  1.1 Notation

For graphs $G$ and $H$, $\overline{G}$ denotes the complement of $G$, $G+H$
denotes the join of $G$ and $H$, $G\cup H$ denotes their disjoint union, and
$a\cdot G$ denotes the disjoint union of $a$ copies of $G$; if $a=\infty$ then
this means countably many copies. We write $H\subseteq G$ if $H$ is a subgraph
of $G$. We write $\Delta(G)$ for the maximum degree of $G$. We write $A=A(G)$
for the adjacency matrix, $D=D(G)$ for the diagonal degree matrix, and
$A_{\alpha}=A_{\alpha}(G)=\alpha D(G)+(1-\alpha)A(G)$. For a symmetric matrix
$M$ we use $\lambda_{1}(M)$ to mean the largest eigenvalue of the matrix, and
for a graph $G$ we write $\lambda(G)$ and $\lambda_{\alpha}(G)$ for
$\lambda_{1}(A(G))$ and $\lambda_{1}(A_{\alpha}(G))$, respectively. For $v\in
V(G)$ and $U\subseteq V(G)$, we write $N(v)$ for the neighborhood of $v$,
$N_{U}(v)$ for $N(v)\cap U$, and $d_{U}(v)$ for $|N_{U}(v)|$. For
$i\in\mathbb{N}$, we write $N_{i}(v)$ for the set of vertices at distance $i$
from $v$. For $U,W\subseteq V(G)$, we write $e(U,W)$ for $|\\{(u,w):u\in
U,w\in W,u\sim w\\}|$, and $e(U)$ for $e(U,U)/2$; we write $E(U,W)$ and $E(U)$
for the corresponding sets of edges. We write $G[U]$ for the subgraph induced
by $U$ and if $U\cap W=\emptyset$ we write $G[U,W]$ for the bipartite subgraph
on vertices $U\sqcup W$ and with all edges in $G$ between $U$ and $W$. Our
notation for specific classes of graphs is standard; we note that $P_{n}$
denotes the path of order $n$, $M_{n}$ is a maximum matching on $n$ vertices,
and $K_{m,\infty}$ means that the larger partite set has a countable set of
vertices. Sometimes we will consider the graph on $n$ vertices which is the
disjoint union of a maximum number of copies of $G$, plus isolated vertices in
the remainder, and we will call this the maximal union of $G$.

Let $\mathcal{F}$ be a family of graphs and let $G$ be a graph. We denote by
$\mathrm{ex}^{G}(n,\mathcal{F})$ the maximum number of edges in an
$\mathcal{F}$-free graph which contains a copy of $G$, and we write
$\mathrm{EX}^{G}(n,\mathcal{F})$ for the corresponding extremal graphs. We
write $\mathrm{ex}_{c}(n,\mathcal{F})$ for the connected extremal number of
$\mathcal{F}$, the maximum number of edges in a connected $\mathcal{F}$-free
graph, and $\mathrm{EX}_{c}(n,\mathcal{F})$ for the set of corresponding
extremal graphs.

###  1.2 Main results

Our first goal is to relate the extremal graphs and spectral extremal graphs.
In [63] it was proven that, if $\mathrm{EX}(n,F)=K_{k}+\overline{K_{n-k}}$ or
$\mathrm{EX}(n,F)=K_{k}+(K_{2}\cup\overline{K_{n-k-2}})$, then
$\mathrm{SPEX}(n,F)=\mathrm{EX}(n,F)$ if $n$ is large enough. The following
theorem generalizes this result (see the discussion following Proposition
1.2.)

######  Theorem 1.1.

Let $\mathcal{F}$ be a family of graphs. Suppose that
$\mathrm{ex}(n,\mathcal{F})=O(n)$, $K_{k+1,\infty}$ is not $\mathcal{F}$-free,
and for $n$ large enough $\mathrm{EX}^{K_{k,n-k}}(n,\mathcal{F})\ni H$, where
one of the following holds:

  * (a)

$H=K_{k,n-k}$

  * (b)

$H=K_{k}+\overline{K_{n-k}}$

  * (c)

$H=K_{k}+(K_{2}\cup\overline{K_{n-k-2}})$

  * (d)

$H=K_{k}+X$ where $e(X)\leq Qn+O(1)$ for some $Q\in[0,3/4)$ and $\mathcal{F}$
is finite

  * (e)

$H=K_{k}+X$ where $e(X)\leq Qn+O(1)$ for some $Q\in[3/4,\infty)$ and
$\mathcal{F}$ is finite

  * (f)

(e) holds, all but a bounded number of vertices of $X$ have constant degree
$d$, $K_{k}+(\infty\cdot K_{1,d+1})$ is not $\mathcal{F}$-free.

If (a), (b), or (c) holds then for $n$ large enough,
$\mathrm{SPEX}(n,\mathcal{F})=H$.

If (d) or (f) holds then for $n$ large enough,
$\mathrm{SPEX}(n,\mathcal{F})\subseteq\mathrm{EX}^{K_{k}+\overline{K_{n-k}}}(n,\mathcal{F})$.

If (e) holds then for $n$ large enough all graphs in
$\mathrm{SPEX}(n,\mathcal{F})$ are of the form $K_{k}+Y$, where $e(Y)\geq
e(X)-O(n^{1/2})$ and $\Delta(Y)$ is bounded in terms of $\mathcal{F}$.

We make two remarks about Theorem 1.1. First, we show in Section 2 any graph
satisfying (d) must have $e(X)=Qn+O(1)$ for some $Q\in\\{0,1/2,2/3\\}$.
Secondly, Theorem 1.1 (d) is sharp in that it fails if $Q=3/4$. The reason is
that there are two non-isomorphic trees of order $4$.

######  Proposition 1.2.

There exists a finite family of graphs $\mathcal{F}$ such that
$\mathrm{EX}(n,\mathcal{F})=K_{2}+X$, where $e(X)=3n/4+O(1)$, and for
infinitely many $n$,
$\mathrm{SPEX}(n,\mathcal{F})\cap\mathrm{EX}(n,\mathcal{F})=\emptyset$.

We now turn to applications. We would like to make use of the existing
literature on the extremal functions $\mathrm{ex}(n,\mathcal{F})$ and
$\mathrm{ex}_{c}(n,\mathcal{F})$. Thus, note that if
$\mathrm{EX}(n,\mathcal{F})\ni H\supseteq K_{k,n-k}$ or
$\mathrm{EX}_{c}(n,\mathcal{F})\ni H\supseteq K_{k,n-k}$ then
$\mathrm{EX}^{K_{k,n-k}}(n,\mathcal{F})\ni H$, and moreover in cases (a)-(d)
or else if $Q<1$, we have that $K_{k+1,\infty}$ is not $\mathcal{F}$-free.
Furthermore it is not too difficult to show that if
$\mathrm{ex}_{c}(n,\mathcal{F})=O(n)$ then $\mathrm{ex}(n,\mathcal{F})=O(n)$.
This implies that in such cases, if we replace the assumption
“$\mathrm{EX}^{K_{k,n-k}}(n,\mathcal{F})\ni H$ and
$\mathrm{ex}(n,\mathcal{F})=O(n)$” in Theorem 1.1 with either
“$\mathrm{EX}(n,\mathcal{F})\ni H$” or “$\mathrm{EX}_{c}(n,\mathcal{F})\ni
H$,” then we obtain a special case of the result, which generalizes Theorem
1.7 of [63].

######  Corollary 1.3.

Suppose that $\mathcal{F}$ is a family of graphs such that, for $n$ large
enough, $\mathrm{EX}(n,\mathcal{F})\ni H$ (or
$\mathrm{EX}_{c}(n,\mathcal{F})\ni H$), where $H$ is one of the graphs in
(a)-(d) or (f) of Theorem 1.1, and moreover that $\mathcal{F}$ is finite in
cases (d) and (f) and $Q<1$ in case (f). Then for $n$ large enough,
$\mathrm{SPEX}(n,\mathcal{F})\subseteq\mathrm{EX}(n,\mathcal{F})$ (or
$\mathrm{SPEX}(n,\mathcal{F})\subseteq\mathrm{EX}_{c}(n,\mathcal{F})$).

We list some applications of Theorem 1.1 and Corollary 1.3. All of our results
only apply when $n$ is large enough, and this condition is assumed everywhere
in the list below. The literature for specific families $\mathcal{F}$ contains
many results with a specific lower bound on the ‘large enough’ $n$, and thus
our results do not always imply the quantitative part of the results that we
mention.

  * •

Paths. Balister, Győri, Lehel, and Schelp [1] showed that
$\mathrm{EX_{c}}(n,P_{2\ell+2})=K_{\ell}+\overline{K_{n-\ell}}$ and
$\mathrm{EX_{c}}(n,P_{2\ell+3})=K_{\ell}+(K_{2}\cup\overline{K_{n-\ell-2}})$
for any $\ell\geq 1$. Thus, Corollary 1.3 and Theorem 1.1 (b) and (c) give
$\mathrm{SPEX}(n,P_{2\ell+2})=K_{\ell}+\overline{K_{n-\ell}}$ and
$\mathrm{SPEX}(n,P_{2\ell+3})=K_{\ell}+(K_{2}\cup\overline{K_{n-\ell-2}})$.
This result was shown by Nikiforov [51].

  * •

Matchings. Erdős and Gallai [18] showed that
$\mathrm{EX}(n,M_{2k+2})=K_{k}+\overline{K_{n-k}}$. Thus,
$\mathrm{SPEX}(n,M_{2k+2})=K_{k}+\overline{K_{n-k}}$. This result was shown by
Feng, Yu, and Zhang [27] (and also proved in a different way by Csikvári
[16]).

  * •

Copies of $P_{3}$. Bushaw and Kettle [5] showed that $\mathrm{EX}(n,k\cdot
P_{3})=K_{k-1}+M_{n-k+1}$. Thus, Theorem 1.1 (d) gives $\mathrm{SPEX}(n,k\cdot
P_{3})=K_{k-1}+M_{n-k+1}$ This was shown by Chen, Liu, and Zhang [8].

  * •

Linear forests. Lidicky, Liu, and Palmer [42] generalized the result of [18]:
if $F=\bigcup_{i=1}^{j}P_{v_{i}}$ for $v_{i}\geq 2$, $j\geq 2$, and at least
one $v_{i}\neq 3$, then $\mathrm{EX}(n,F)=K_{k}+\overline{K_{n-k}}$ if some
$v_{i}$ is even and $\mathrm{EX}(n,F)=K_{k}+(K_{2}\cup\overline{K_{n-k-2}})$
if all $v_{i}$ are odd, where $k=\left(\sum_{i=1}^{j}\lfloor
v_{i}/2\rfloor\right)-1$. Thus, $\mathrm{SPEX}(n,F)=K_{k}+\overline{K_{n-k}}$
if some $v_{i}$ is even and
$\mathrm{SPEX}(n,F)=K_{k}+(K_{2}\cup\overline{K_{n-k-2}})$ if all $v_{i}$ are
odd. This result was shown by Chen, Liu, and Zhang [8].

  * •

Star forests. Lidicky, Liu, and Palmer [42] investigated the extremal number
of $F=\bigcup_{i=1}^{k}K_{1,d_{i}}$, where $d_{1}\geq\cdots\geq d_{k}$ and
$k\geq 2$. In this case it is possible that
$\mathrm{EX}(n,\mathcal{F})\cap\mathrm{SPEX}(n,\mathcal{F})=\emptyset.$ Note
that $\mathrm{EX}^{K_{k-1,n-k+1}}(n,\mathcal{F})=K_{k-1}+X$, where $X$ is an
almost $(d_{k}-1)$-regular graph; $K_{k,\infty}\supseteq F$; and
$K_{k-1}+(\infty\cdot K_{1,d_{k}})$ is not $\mathcal{F}$-free. Thus Theorem
1.1 (f) gives that
$\mathrm{SPEX}(n,\mathcal{F})\subseteq\mathrm{EX}^{K_{k}+\overline{K_{n-k}}}(n,\mathcal{F})$.
Then one can show using equitable partitions that if $n-k+1$ is even, we
actually have $\mathrm{SPEX}(n,\mathcal{F})=\\{K_{k}+X:X\text{ is
}(d_{k}-1)\text{-regular}\\}$. This was shown by Chen, Liu, and Zhang [9].

  * •

Trees. At the same time that we were finishing this paper Fang, Lin, Shu, and
Zhang [23] proved several theorems studying trees. These include the results
listed below about “certain small trees”. Our result below about “almost all
trees” is complementary to the results in [23]; their results determine for
which trees $T$ $\mathrm{SPEX}(n,T)=K_{k,n-k}$ but the characterization is
phrased in terms of coverings and the extremal number of a decomposition-like
family.

    * –

Certain small trees. Caro, Patkós and Tuza [6] determined
$\mathrm{EX}_{c}(n,T)$ for many small trees $T$. Let $S_{a_{1},\ldots,a_{j}}$
denote the spider obtained by identifying paths of orders
$a_{1}+1,\ldots,a_{j}+1$ at one endpoint, and let $D_{a,b}$ denote the double
star on $a+b+2$ vertices whose two non-leaf vertices have degrees $a+1$ and
$b+1$. Let $D_{2,2}^{*}$ be the graph obtained by attaching a leaf to a leaf
of $D_{2,2}$. Among their results there are some to which we can apply Theorem
1.1 which are not already mentioned above: (i)
$\mathrm{EX}_{c}(n,S_{2,2,1})=K_{2}+\overline{K_{n-2}}$; (ii)
$\mathrm{EX}_{c}(n,S_{3,1,1})=K_{1}+M_{n-1}$; (iii)
$\mathrm{EX}_{c}(n,D_{2,2})=K_{2,n-2}$; (iv)
$\mathrm{EX}_{c}(n,D_{2,2}^{*})=K_{2}+\overline{K_{n-2}}$; (v)
$\mathrm{EX}_{c}(n,S_{3,2,1})=K_{2}+\overline{K_{n-2}}$; (vi)
$\mathrm{EX}_{c}(n,D_{2,3})=K_{2,n-2}$.

    * –

Almost all trees. Let $T$ be a tree with proper coloring $V=A\sqcup B$, where
$k+1=|A|\leq|B|$, such that $B$ contains a vertex of degree at least 3,
exactly one of whose neighbors is not a leaf. (In the proof of Proposition 1.4
we will show that ‘almost all trees’ indeed have this property.) It is well-
known that $\mathrm{ex}(n,T)=O(n)$. Observe that $K_{k,\infty}$ is $T$-free.
To show it is $T$-saturated, it remains to show that adding any edge to
$K_{k,\infty}$ creates a copy of $T$. Let $L,R$ be the partite sets with
$|L|=k$. Since $A$ has a leaf, $e(R)=0$, or else we could embed $T$ in $G$ by
placing this leaf incident to an edge in $R$ and placing the rest of $A$ in
$L$. To show $e(L)=0$, suppose $L$ has an edge. Then we can embed $T$ in $G$
by placing at least 2 leaves of $A$ in $R$ and the rest of $A$ in $L$, a
contradiction. Thus, Theorem 1.1 (a) gives $\mathrm{SPEX}(n,T)=K_{k,n-k}$.

  * •

Spectral Erdős-Sós theorem. Note that $G$ contains all trees on $2k+2$
vertices if and only if $G$ is not $\mathcal{F}$-free, where $\mathcal{F}$ is
the set of all graphs which contain all trees on $2k+2$ vertices. Note that
$\mathrm{EX}^{K_{k,n-k}}(n,\mathcal{F})=K_{k}+\overline{K_{n-k}}$ (see e.g.
Lemma 4.6 of [14]). Thus, we have
$\mathrm{SPEX}(n,\mathcal{F})=K_{k}+\overline{K_{n-k}}$. Similarly, if
$\mathcal{F}^{\prime}$ is the set of all graphs which contain all trees on
$2k+3$ vertices, then
$\mathrm{SPEX}(n,\mathcal{F}^{\prime})=K_{k}+(K_{2}\cup\overline{K_{n-k-2}})$.
These results were shown by Cioabă and the second and third authors [14].

  * •

Long cycles. Let $\mathcal{F}=\\{C_{\ell},C_{\ell+1},\ldots\\}$ be the set of
cycles of length at least $\ell\geq 5$. Note
$\mathrm{EX}^{K_{k,n-k}}(n,\mathcal{F})=K_{k}+\overline{K_{n-k}}$ if $\ell$ is
odd and
$\mathrm{EX}^{K_{k,n-k}}(n,\mathcal{F})=K_{k}+(K_{2}\cup\overline{K_{n-k-2}})$
if $\ell$ is even, where $k=\lfloor(\ell-1)/2\rfloor$; this can be viewed as a
special case of a result of Kopylov [38]. Erdős and Gallai [18] showed that
$\mathrm{ex}(n,\mathcal{F})\leq\frac{1}{2}(k-1)(n-1)$. Thus,
$\mathrm{SPEX}(n,\mathcal{F})=K_{k}+\overline{K_{n-k}}$ if $\ell$ is odd and
$\mathrm{SPEX}(n,\mathcal{F})=K_{k}+(K_{2}\cup\overline{K_{n-k-2}})$ if $\ell$
is even. This result was shown by Gao and Hou [28]. In fact, the result also
follows from the spectral even cycle theorem [13], but we have included it to
demonstrate the versatility of Theorem 1.1.

  * •

Arithmetic progression of cycles. Let $\mathcal{F}$ be the set of cycles of
length $\ell$ modulo $r$, $\ell<r$. Bollobás [3] showed that
$\mathrm{ex}(n,\mathcal{F})<r^{-1}((r+1)^{r}-1)n$. Thus, if $\ell$ is even and
at least 5, then
$\mathrm{SPEX}(n,\mathcal{F})=K_{\ell/2-1}+(K_{2}\cup\overline{K_{n-\ell/2-1}})$
and if $\ell,r$ are both odd then
$\mathrm{SPEX}(n,\mathcal{F})=K_{(r+\ell)/2-1,n-(r+\ell)/2+1}$. The first
result follows from the spectral even cycle theorem, while the second one
appears to be new.

  * •

Interval of even cycles. Note that $G$ contains $k$ consecutive even cycle
lengths if and only if $G$ is not $\mathcal{F}$-free, where $\mathcal{F}$ is
the set of all graphs which contain $k$ consecutive even cycle lengths.
Verstraëte [57] proved that $\mathrm{ex}(n,\mathcal{F})<3kn$. Thus,
$\mathrm{SPEX}(n,\mathcal{F})=K_{k}+(K_{2}\cup\overline{K_{n-k-2}})$. This
result appears to be new.

  * •

Disjoint cycles. Let $\mathcal{F}$ be the set of all disjoint unions of $k$
cycles (of possibly different lengths), where $k\geq 2$. Erdős and Pósa [19]
showed that $\mathrm{EX}(n,\mathcal{F})=K_{2k-1}+\overline{K_{n-2k+1}}$. Thus,
$\mathrm{SPEX}(n,\mathcal{F})=K_{2k-1}+\overline{K_{n-2k+1}}.$ This result was
shown by Liu and Zhai [43].

  * •

Disjoint long cycles. Let $\mathcal{F}$ be the set of all disjoint unions of
$k$ cycles, each of length at least $\ell\geq 5$. Harvey and Wood [34] showed
that $\mathrm{ex}(n,\mathcal{F})<\frac{2}{3}k\ell n$. Thus, if $\ell$ is even
then
$\mathrm{SPEX}(n,\mathcal{F})=K_{k\ell/2-1}+(K_{2}\cup\overline{K_{n-k\ell/2-1}})$
and if $\ell$ is odd then
$\mathrm{SPEX}(n,\mathcal{F})=K_{k(\ell+1)/2-1}+\overline{K_{n-k(\ell+1)/2+1}}$.
The first result follows from the spectral extremal result for $t\cdot
C_{\ell}$ [24], while the second result appears to be new.

  * •

Disjoint equicardinal cycles. Let $\mathcal{F}$ be the set of all disjoint
unions of two cycles of the same length. Häggkvist [33] showed the
$\mathrm{ex}(n,\mathcal{F})<6n$. Thus,
$\mathrm{SPEX}(n,\mathcal{F})=K_{3}+\overline{K_{n-3}}$. This result appears
to be new.

  * •

Minors. Note that $G$ is $F$-minor free if and only if $G$ is
$\mathcal{F}$-free, where $\mathcal{F}$ is the set of all graphs which have an
$F$-minor. Suppose that $K_{k}+\overline{K_{n-k}}$ is $\mathcal{F}$-saturated;
then $\mathrm{EX}^{K_{k,n-k}}(n,\mathcal{F})=K_{k}+\overline{K_{n-k}}$,
because $\overline{K_{k}}+(K_{2}\cup\overline{K_{\infty}})$ has a
$K_{k}+(K_{2}\cup\overline{K_{\infty}})$-minor. Mader [46] showed that
$\mathrm{ex}(n,\mathcal{F})<(k-1)2^{{k-1\choose 2}-1}n$. Thus
$\mathrm{SPEX}(n,\mathcal{F})=K_{k}+\overline{K_{n-k}}$. We list below some
special cases.

    * –

The $K_{k}$-minor free spectral extremal graph is
$K_{k-2}+\overline{K_{n-k+2}}$. This was shown by the third author [55].

    * –

If $F$ is obtained by deleting from $K_{k}$ the edges of disjoint paths, not
all of order 3, then the $F$-minor free spectral extremal graph is
$K_{k-3}+\overline{K_{n-k+3}}$. This was shown recently by Chen, Liu, and
Zhang [12].

    * –

If $F_{k}$ is the friendship graph with $k$ triangles then the $F_{k}$-minor
free spectral extremal graph is $K_{k}+\overline{K_{n-k}}$. This was shown by
He, Li, and Feng [35].

If $\mathrm{SPEX}(n,F)=K_{k}+\overline{K_{n-k}}$ then
$\mathrm{SPEX}(n,\mathcal{F})=K_{k}+\overline{K_{n-k}}$ holds automatically,
without making use of Theorem 1.1. The same applies to
$\mathrm{SPEX}_{\alpha}(n,F)$.

  * •

Topological subdivisions. The extremal result of [46] is actually stronger
than as stated in the application above; it applies even when $\mathcal{F}$ is
the family of all topological subdivisions of $K_{k}$. A similar argument to
the minor case then proves the following: if $\mathcal{F}$ is the family of
all topological subdivisions of $F$, and $K_{k}+\overline{K_{n-k}}$ is
$\mathcal{F}$-saturated then
$\mathrm{SPEX}(n,\mathcal{F})=K_{k}+\overline{K_{n-k}}$.

  * •

Chorded cycles. Let $\mathcal{F}$ be the family of all chorded cycles. Pósa
(see e.g. in [32]) showed that $\mathrm{ex}(n,\mathcal{F})<2n-3$. Thus
$\mathrm{SPEX}(n,\mathcal{F})=K_{2,n-2}$. This was shown recently by Zheng,
Huang, and Wang [65] and gives an answer to a question posed by Gould
(Question 3 in [32]).

  * •

Two disjoint chorded cycles. Let $\mathcal{F}_{1}$ be the family of all graphs
made of two disjoint cycles, one of which has a chord, and let
$\mathcal{F}_{2}$ be the family of all graphs made of two disjoint chorded
cycles. Bialostocki, Finkel, and Gyárfás [2] showed that
$\mathrm{EX}(n,\mathcal{F}_{1})\ni K_{4,n-4}$ and
$\mathrm{EX}(n,\mathcal{F}_{2})\ni K_{5,n-5}$. Thus
$\mathrm{SPEX}(n,\mathcal{F}_{1})=K_{4,n-4}$ and
$\mathrm{SPEX}(n,\mathcal{F}_{2})=K_{5,n-5}$. This result appears to be new.

  * •

Disjoint chorded cycles. Let $\mathcal{F}$ be the family of all graphs made of
$k$ disjoint chorded cycles. The result of Gao and Wang [30] implies that
$\mathrm{ex}(n,\mathcal{F})=O(n)$ via a well-known bound on max cut. Thus,
$\mathrm{SPEX}(n,\mathcal{F})=K_{3k-1,n-3k+1}$. This result appears to be new.

  * •

Multiply chorded cycles. Let $\mathcal{F}$ be the family of all cycles with
$k(k-2)+1$ chords, $k\geq 2$. Gould, Horn, and Magnant [31] showed that
$\mathrm{ex}(n,\mathcal{F})=O(n)$. Thus,
$\mathrm{SPEX}(n,\mathcal{F})=K_{k,n-k}$. This result appears to be new.

  * •

Cycles with $k$ incident chords. Let $\mathcal{F}$ be the family of cycles
with $k$ chords all incident to the same vertex. Jiang [36] showed that
$\mathrm{EX}(n,\mathcal{F})\ni K_{k+1,n-k-1}$. Thus,
$\mathrm{SPEX}(n,\mathcal{F})=K_{k+1,n-k-1}$. This result appears to be new.

######  Proposition 1.4.

The proportion of all labelled $m$-vertex trees $T$ such that for some $k$,
$\mathrm{SPEX}(n,T)=K_{k,n-k}$ for $n$ large enough, approaches $1$ as
$m\to\infty$.

Our second goal is to relate the spectral extremal graphs and alpha spectral
extremal graphs.

######  Theorem 1.5.

Let $\mathcal{F}$ be a family of graphs containing some bipartite graph $F$
for which $F-v$ is a forest, or such that $\mathrm{ex}(n,\mathcal{F})=O(n)$.
Suppose that for $n$ large enough, $\mathrm{SPEX}(n,\mathcal{F})\ni H$, where
either:

  * (a)

$H=K_{k}+\overline{K_{n-k}}$

  * (b)

$H=K_{k}+(K_{2}\cup\overline{K_{n-k-2}})$.

Then for any $\alpha\in(0,1)$, for any $n$ large enough,
$\mathrm{SPEX}_{\alpha}(n,\mathcal{F})=H$.

We give a list of new and existing results implied by Theorem 1.5; if no
reference is given for the required spectral result that means that it falls
under the previous list of applications.

  * •

Paths. We have
$\mathrm{SPEX}_{\alpha}(n,P_{2\ell+2})=K_{\ell}+\overline{K_{n-\ell}}$ and
$\mathrm{SPEX}_{\alpha}(n,P_{2\ell+3})=K_{\ell}+(K_{2}\cup\overline{K_{n-\ell-2}})$.
This was shown by Chen, Liu, and Zhang [11].

  * •

Matchings. We have
$\mathrm{SPEX}_{\alpha}(n,M_{2k+2})=K_{k}+\overline{K_{n-k}}$. This was shown
by Yuan and Shao [60].

  * •

Linear forests. Generalizing the previous two results: if
$F=\bigcup_{i=1}^{j}P_{v_{i}}$ where $v_{i}\geq 2$, $j\geq 2$, and at least
one $v_{i}\neq 3$, then
$\mathrm{SPEX}_{\alpha}(n,\mathcal{F})=K_{k}+\overline{K_{n-k}}$ if some
$v_{i}$ is even and
$\mathrm{SPEX}_{\alpha}(n,\mathcal{F})=K_{k}+(K_{2}\cup\overline{K_{n-k-2}})$
if all $v_{i}$ are odd, where $k=\left(\sum_{i=1}^{j}\lfloor
v_{i}/2\rfloor\right)-1$. This was shown by Chen, Liu, and Zhang [11].

  * •

Certain small trees. We have (i)
$\mathrm{SPEX}_{\alpha}(n,S_{2,2,1})=K_{k}+\overline{K_{n-2}}$; (ii)
$\mathrm{SPEX}_{\alpha}(n,D_{2,2}^{*})=K_{2}+\overline{K_{n-2}}$; (iii)
$\mathrm{SPEX}_{\alpha}(n,S_{3,2,1})=K_{2}+\overline{K_{n-2}}$. These results
appear to be new.

  * •

Spectral Erdős-Sós theorem. Let $\mathcal{F}$ be the set of all graphs which
contain all trees on $2k+2$ vertices, and let $\mathcal{F}^{\prime}$ be the
set of all graphs which contain all trees on $2k+3$ vertices. Then
$\mathrm{SPEX}_{\alpha}(n,\mathcal{F})=K_{k}+\overline{K_{n-k}}$ and
$\mathrm{SPEX}_{\alpha}(n,\mathcal{F}^{\prime})=K_{k}+(K_{2}\cup\overline{K_{n-k-2}})$.
These results were shown by Chen, Li, Li, Yu, and Zhang [7].

  * •

Even cycles and consecutive cycles. Cioabă and the second and third authors
[13] showed that
$\mathrm{SPEX}(n,C_{2\ell+2})=K_{\ell}+(K_{2}\cup\overline{K_{n-\ell-2}})$ and
$\mathrm{SPEX}(n,\\{C_{2\ell+1},C_{2\ell+2}\\})=K_{\ell}+\overline{K_{n-\ell}}$,
for $k\geq 2$. Thus,
$\mathrm{SPEX}_{\alpha}(n,C_{2\ell+2})=K_{k}+(K_{2}\cup\overline{K_{n-\ell-2}})$
and
$\mathrm{SPEX}_{\alpha}(n,\\{C_{2\ell+1},C_{2\ell+2}\\})=K_{\ell}+\overline{K_{n-\ell}}$.
This was shown by Li and Yu [39].

  * •

Intersecting even cycles. Let $C_{\ell_{1},\ldots,\ell_{t}}$ be obtained by
intersecting the cycles $C_{\ell_{1}}\ldots,C_{\ell_{t}}$ at a unique vertex.
The second author [17] showed that if $\ell_{1},\ldots,\ell_{t}\geq 2$ and
some $\ell_{t}>2$, then
$\mathrm{SPEX}(n,C_{2\ell_{1},\ldots,2\ell_{t}})=K_{k}+(K_{2}\cup\overline{K_{n-k-2}})$,
where $k=\sum_{i=1}^{t}(\ell_{i}-1)$. Thus,
$\mathrm{SPEX}_{\alpha}(n,C_{2\ell_{1},\ldots,2\ell_{t}})=K_{k}+(K_{2}\cup\overline{K_{n-k-2}})$.
This result appears to be new.

  * •

Long cycles. If $\mathcal{F}=\\{C_{\ell},C_{\ell+1},\ldots\\}$ then
$\mathrm{SPEX}_{\alpha}(n,\mathcal{F})=K_{k}+\overline{K_{n-k}}$ if $\ell$ is
odd and
$\mathrm{SPEX}_{\alpha}(n,\mathcal{F})=K_{k}+(K_{2}\cup\overline{K_{n-k-2}})$
if $\ell$ is even, where $k=\lfloor(\ell-1)/2\rfloor$. This result is implied
by the result forbidding even cycles or consecutive cycles.

  * •

Arithmetic progression of cycles. Let $\mathcal{F}$ be the set of cycles of
length $\ell$ modulo $r$, $\ell<r$. If $\ell$ is even and at least 5, then
$\mathrm{SPEX}_{\alpha}(n,\mathcal{F})=K_{\ell/2-1}+(K_{2}\cup\overline{K_{n-\ell/2-1}})$.
This result is implied by the result forbidding even cycles.

  * •

Interval of even cycles. Let $\mathcal{F}$ be the family of all graphs which
contain $k$ consecutive even cycle lengths. Then
$\mathrm{SPEX}_{\alpha}(n,\mathcal{F})=K_{k}+(K_{2}\cup\overline{K_{n-k-2}})$.
This result appears to be new.

  * •

Disjoint cycles. If $\mathcal{F}$ is the set of all disjoint unions of $k$
cycles (of possibly different lengths) then
$\mathrm{SPEX}_{\alpha}(n,\mathcal{F})=K_{2k-1}+\overline{K_{n-2k+1}}$. This
was shown by Li, Yu, and Zhang [40].

  * •

Disjoint long cycles. Let $\mathcal{F}$ be the set of all disjoint unions of
$k$ cycles, each of length at least $\ell\geq 5$. If $\ell$ is even then
$\mathrm{SPEX}_{\alpha}(n,\mathcal{F})=K_{k\ell/2-1}+\overline{K_{n-k\ell/2+1}}$
and if $\ell$ is odd then
$\mathrm{SPEX}_{\alpha}(n,\mathcal{F})=K_{k(\ell+1)/2-1}+(K_{2}\cup\overline{K_{n-k(\ell+1)/2+1}})$.
This result seems to be new.

  * •

Disjoint equicardinal cycles. If $\mathcal{F}$ is the family of all disjoint
unions of two cycles of the same length, then
$\mathrm{SPEX}_{\alpha}(n,\mathcal{F})=K_{3}+\overline{K_{n-3}}$ for $n$ large
enough. This result seems to be new.

  * •

Minors. If $\mathcal{F}$ is the family of all graphs which have an $F$-minor
and $K_{k}+\overline{K_{n-k}}$ is $\mathcal{F}$-saturated, then
$\mathrm{SPEX}_{\alpha}(n,\mathcal{F})=K_{k}+\overline{K_{n-k}}$.

    * –

If $F=K_{k}$ then
$\mathrm{SPEX}_{\alpha}(n,\mathcal{F})=K_{k-2}+\overline{K_{n-k+2}}$. This was
shown by Chen, Liu, and Zhang [10].

    * –

If $F$ is obtained by deleting from $K_{k}$ the edges of disjoint paths, not
all of length 3, then
$\mathrm{SPEX}_{\alpha}(n,\mathcal{F})=K_{k-3}+\overline{K_{n-k+3}}$. This
result appears to be new.

    * –

If $F$ is the friendship graph with $k$ triangles
$\mathrm{SPEX}_{\alpha}(n,\mathcal{F})=K_{k}+\overline{K_{n-k}}$. This was
shown by Wang and Zhang [64].

  * •

Topological subdivisions. If $\mathcal{F}$ is the family of all topological
subdivisions of $F$ and $K_{k}+\overline{K_{n-k}}$ is $\mathcal{F}$-saturated,
then $\mathrm{SPEX}_{\alpha}(n,\mathcal{F})=K_{k}+\overline{K_{n-k}}$.

We observe that there are fewer options for the assumed extremal graph in
Theorem 1.5 than in Theorem 1.1. In the case that $H=K_{k,n-k}$ there is a
simple counterexample that explains this: let $F$ be any graph such that
$\mathrm{SPEX}(n,F)=K_{k,n-k}$ for $n$ large enough, where $k>1$. Then
$K_{1,n}$ is also $F$-free, and if $\alpha$ is sufficiently close to 1 then
$\lambda_{\alpha}(K_{1,n})\geq\alpha(n-1)>\lambda_{\alpha}(K_{k,n-k})$ (see
e.g. [53]). Thus, one could only hope to extend Theorem 1.5 to this case if
$\alpha$ is restricted to a certain range. When $H$ is of the form $K_{k}+X$,
then the situation may be more subtle and we do not attempt to address every
case.

##  2 Spectral extremal results

In this section we prove results concerning $\mathrm{SPEX}(n,\mathcal{F})$. In
subsections 2.1, 2.2, 2.3, and 2.4 we prove Theorem 1.1; in subsection 2.5 we
prove Proposition 1.2; and in subsection 2.6 we prove Proposition 1.4. Unless
stated otherwise, all claims are asserted only for $n$ large enough.

###  2.1 Structure of edge extremal graphs

######  Proposition 2.1.

Under the assumptions of Theorem 1.1 (d) $X$ can be obtained from a maximal
union of $P_{1}$, of $P_{2}$, or of $P_{3}$ by adding or deleting a bounded
number of edges.

###### Proof.

Note that $K_{k+1,\infty}\supseteq F$ for some $F\in\mathcal{F}$. Let $\delta$
be the smallest degree in the partite set of $F$ of size $k+1$. Note that
$\Delta(X)\leq\delta-1$, because $F\subseteq
K_{k}+(K_{1,\delta}\cup\overline{K_{n-k-\delta-1}})$.

Consider the components of $X$. We claim the number of components of order at
least 4 is bounded; otherwise, the union of these components is a subgraph
$Y\subseteq X$ with $|V(Y)|\to\infty$ and $|e(Y)|\geq 3|V(Y)|/4$, thus
contradicting the fact that $\mathrm{ex}^{K_{k,n-k}}(n,\mathcal{F})\leq
kn+Qn+O(1)$ for $n$ large enough. Moreover, the order of a component of $X$ is
bounded; otherwise, by taking the largest component $Y$, we find a subgraph
$Y\subseteq X$ with $|V(Y)|\to\infty$ and $|e(Y)|\geq|V(Y)|-1$, again
contradicting our bound on $\mathrm{ex^{K_{k,n-k}}}(n,\mathcal{F})$.

Now let $\nu=\max\\{i:\text{there exist an unbounded number of components of
$X$ of order }i\\}\in\\{1,2,3\\}$. If $\nu=1$ then $e(X)$ is bounded, and we
are done.

Suppose $\nu=2$. Then $X$ is the union of an unbounded number copies of
$P_{2}$, a bounded number of graphs of bounded order, and isolated vertices.
Suppose for contradiction there are 2 isolated vertices in $X$; then adding an
edge $e_{0}$ between them creates a copy $F_{0}$ of a graph from
$\mathcal{F}$. Since there were already an unbounded number of disjoint edges
in $X$, one such edge $e_{1}$ is disjoint from $F_{0}$, and the neighborhoods
of its endpoints contain the neighborhoods of the endpoints of $e_{0}$, so we
can replace $e_{0}$ by $e_{1}$ to find $F_{1}\simeq F_{0}$ which already
existed in $K_{k}+X$, a contradiction. Thus there is at most 1 isolated
vertex. Hence, $X$ is obtained from $M_{n-k}$ by deleting and adding a bounded
number of edges.

Suppose $\nu=3$. Then $X$ is the union of an unbounded number of copies of
$P_{3}$, a bounded number of graphs of bounded order, and graphs of order less
than 3. We will show that the components smaller than $P_{3}$ span at most 5
vertices; for otherwise, we can find either 3 $P_{1}$ components, a $P_{1}$
component and a $P_{2}$ component, or three $P_{2}$ components. In any case we
can add and delete edges for a net increase in $e(X)$ without creating any
components on more than 3 vertices, and such that the copy of some
$F_{0}\in\mathcal{F}$ which must have been created uses a vertex from a newly
created $P_{3}$ component; but similarly to the previous case, we find another
$P_{3}$ component (or two disjoint $P_{3}$ components if needed) which was not
used in $F_{0}$, hence there was some $F_{1}\simeq F_{0}$ which already
existed, a contradiction. This shows that $X$ is obtained from a maximal union
of $P_{3}$ by deleting and adding a bounded number of edges. ∎

###  2.2 Common features of the spectral extremal graphs

The purpose of this subsection is to prove the following proposition.

######  Proposition 2.2.

Assume the setup of any of the cases (a)-(f) of Theorem 1.1. If
$G\in\mathrm{SPEX}(n,\mathcal{F})$ then $G\supseteq K_{k,n-k}$.

Let $H$ be the edge extremal graph; when we need to specify the number of
vertices, we will write $H_{n}$ instead of $H$. Set $\lambda=\lambda_{1}(G)$,
and let $x$ be a Perron eigenvector of $G$, scaled so that its greatest entry
is $x_{z}=1$. Let $F\in\mathcal{F}$ be a graph such that $F\subseteq
K_{k+1,\infty}$, and let $m=|V(F)|$,
$m^{\prime}=\sup\\{|V(F^{\prime})|:F^{\prime}\in\mathcal{F}\\}$. Let $C$ be
chosen such that $\mathrm{ex}(n,\mathcal{F})\leq Cn$. We choose positive
constants $\eta,\varepsilon,\sigma,\beta$ to satisfy the following
inequalities:

  * (i)

$\beta<\frac{k}{2C}$

  * (ii)

$10C\sigma<\varepsilon^{2}$

  * (iii)

$\varepsilon<\eta\leq C$

  * (iv)

$\sigma<\frac{\varepsilon^{2}}{30k}$

  * (v)

$(8k^{3}+2)\varepsilon<\eta$

  * (vi)

$\varepsilon<(2/5-1/4)/k^{3}$

  * (vii)

$(k+\varepsilon)\eta+\varepsilon^{2}/2<1/2$

  * (viii)

$(2C+m)\eta<1-\frac{1}{4k^{3}}.$

To see that such a choice exists, we choose $\eta$ first with the additional
constraint that $\eta<k/4$; this allows that some $\varepsilon>0$ will satisfy
(vii). Then we choose $\varepsilon,\sigma,$ and $\beta$ in that order. With
$V=V(G)$, let $L^{\prime}=\\{v\in V:x_{v}\geq\eta\\}$, $L=\\{v\in
V:x_{v}\geq\sigma\\}$, $M=\\{v\in V:x_{v}\geq\beta\sigma\\}$, and $S=V-L$. For
$v\in V$, let $L_{i}(v)=L\cap N_{i}(v)$, $M_{i}(v)=M\cap N_{i}(v)$,
$S_{i}(v)=S\cap N_{i}(v)$.

The proof of Proposition 2.2 is technical; a high-level outline is as follows.

  * 1.

Show that $|L|$ and $|M|$ are not too large, i.e. there are not too many
vertices with large eigenweight.

  * 2.

Show that $|L|$ is in fact bounded.

  * 3.

Relate the eigenweight of vertices to their degrees.

  * 4.

Show that eigenweights of vertices in $L^{\prime}$ are close to 1.

  * 5.

Show that $|L^{\prime}|=k$.

  * 6.

Show that if $u\not\in L^{\prime}$ then $u\sim v$ for all $v\in L^{\prime}$.

######  Lemma 2.3.

We have

$\sqrt{k(n-k)}\leq\lambda\leq\sqrt{2Cn}.$

###### Proof.

Since $K_{k,n-k}$ is $\mathcal{F}$-free we have

$\lambda\geq\lambda_{1}(K_{k,n-k})=\sqrt{k(n-k)}.$

For the upper bound,

$\lambda^{2}=\lambda^{2}x_{z}=\sum_{u\sim z}\sum_{w\sim u}x_{w}\leq\sum_{u\sim
z}d(u)\leq\sum_{u\in V}d(u)=2e(G)\leq 2Cn$

∎

######  Lemma 2.4.

We have

$|L|\leq\frac{2Cn}{\sigma\sqrt{k(n-k)}},\ \
|M|\leq\frac{2Cn}{\sigma\beta\sqrt{k(n-k)}}.$

###### Proof.

For any $v\in V$ we have $\lambda x_{v}=\sum_{u\sim v}x_{u}\leq d(v)$. Hence

$\sqrt{k(n-k)}|L|\sigma\leq\lambda|L|\sigma\leq\sum_{v\in L}\lambda
x_{v}\leq\sum_{v\in V}\lambda x_{v}\leq\sum_{v\in V}d(v)=2e(G)\leq 2Cn.$

Solving for $|L|$ proves the first claim. A similar argument applies to $|M|$.
∎

######  Lemma 2.5.

For any $v\in L$,

$d(v)\geq\frac{\sigma k}{4(1+3C)}n.$

###### Proof.

Let $v\in L$. We have

$\sigma k(n-k)\leq\lambda^{2}x_{v}=\sum_{u\sim v}\sum_{w\sim u}x_{w}\leq
d(v)+2e(N_{1})+e(N_{1},M_{2})+\underbrace{\sum_{u\sim
v}\sum_{\begin{subarray}{c}w\sim u\\\ w\in
N_{2}-M_{2}\end{subarray}}x_{w}}_{B}$

from the eigenvector equation, where in the first three terms in the right
hand side we used the estimate $x_{w}\leq 1$. We estimate $e(N_{1})$,
$e(N_{1},M_{2})$, and $B$ as follows. First, $N_{1}$ induces a subgraph of
order $d(v)$ which does not contain any element of $\mathcal{F}$, so
$e(N_{1})\leq Cd(v)$. Similarly we have $e(N_{1},M_{2})\leq
C\left(\frac{2Cn}{\sigma\beta\sqrt{k(n-k)}}+d(v)\right)$. For $B$, we use
$x_{w}\leq\sigma\beta$ and so we have $B\leq\sigma\beta e(G)\leq\sigma\beta
Cn$. Rearranging the inequality, we get

$\left(\sigma k-\sigma\beta C\right)n-\sigma
k^{2}-\frac{2C^{2}n}{\sigma\beta\sqrt{k(n-k)}}\leq(1+3C)d(v).$

By inequality (i), taking $n$ large enough gives

$d(v)\geq\frac{\sigma k}{4(1+3C)}n.$

∎

######  Lemma 2.6.

There is a constant $C_{1}=C_{1}(\mathcal{F})$ such that $|L|\leq C_{1}$.

###### Proof.

We use the same argument from Lemma 2.4 with the updated information from
Lemma 2.5. We have

$|L|\frac{\sigma k}{4(1+3C)}n\leq\sum_{v\in L}d(v)\leq 2e(G)\leq 2Cn$

so

$|L|\leq\frac{8C(1+3C)}{\sigma k}=:C_{1}.$

∎

######  Lemma 2.7.

For any vertex $v$, we have

$k(n-k)x_{v}\leq d(v)x_{v}+e(S_{1},L_{1}\cup
L_{2})+\frac{\varepsilon^{2}n}{2}.$

###### Proof.

Let $c=x_{v}$. We have

$\displaystyle k(n-k)c$ $\displaystyle\leq\lambda^{2}c=\sum_{u\sim
v}\sum_{w\sim u}x_{w}=d(v)c+\sum_{u\sim v}\sum_{\begin{subarray}{c}w\sim u\\\
w\neq v\end{subarray}}x_{w}$ $\displaystyle\leq d(v)c+\sum_{u\in
S_{1}(v)}\sum_{\begin{subarray}{c}w\sim u\\\ w\in L_{1}(v)\cup
L_{2}(v)\end{subarray}}x_{w}+2e(S_{1})\sigma+2e(L)+e(L_{1},S_{1})\sigma+e(N_{1},S_{2})\sigma.$

We apply $e(G)\leq Cn$ and $|L|\leq C_{1}$ to get

$2e(S_{1})\sigma+2e(L)+e(L_{1},S_{1})\sigma+e(N_{1},S_{2})\sigma\leq
2Cn\sigma+2C_{1}^{2}+Cn\sigma+Cn\sigma\leq 5Cn\sigma.$

So

$\displaystyle k(n-k)c$ $\displaystyle\leq d(v)c+\sum_{u\in
S_{1}(v)}\sum_{w\sim u,w\in L_{1}(v)\cup L_{2}(v)}x_{w}+5Cn\sigma\leq
d(v)c+e(S_{1},L_{1}\cup L_{2})+\frac{\varepsilon^{2}n}{2}$

where the last inequality holds by (ii). ∎

######  Lemma 2.8.

If $v\in L^{\prime}$ and $c=x_{v}$, then $d(v)\geq(c-\varepsilon)n$.

###### Proof.

Assume for a contradiction that $d(v)<cn-\varepsilon n$. Thus Lemma 2.7 gives

$k(n-k)c\leq(cn-\varepsilon n)c+e(S_{1},L_{1}\cup
L_{2})+\frac{\varepsilon^{2}n}{2}.$

Hence

$e(S_{1},L_{1}\cup L_{2})\geq(k-c+\varepsilon)nc-
ck^{2}-\frac{\varepsilon^{2}n}{2}=(k-c)nc+\varepsilon nc-
ck^{2}-\frac{\varepsilon^{2}n}{2}\geq(k-1)nc+\frac{\varepsilon^{2}n}{2},$

using that $v\in L^{\prime}$ implies that $c\geq\eta>\varepsilon$ and $c\leq
1$.

Now we claim there are at least $\sqrt{n}$ vertices in $S_{1}$ with at least
$k$ neighbors in $L_{1}\cup L_{2}$. For if not, then $e(S_{1},L_{1}\cup
L_{2})<(k-1)|S_{1}|+|L|\sqrt{n}<(k-1)(c-\varepsilon)n+C_{1}\sqrt{n}$ because
$|S_{1}|\leq d(v)$ and $|L|\leq C_{1}$. Thus $(k-1)cn-(k-1)\varepsilon
n+C_{1}\sqrt{n}>e(S_{1},L_{1}\cup
L_{2})\geq(k-1)cn+\frac{\varepsilon^{2}n}{2}$ which is a contradiction for $n$
large enough. Thus, let $D$ be a set of $\sqrt{n}$ vertices in $S_{1}$ each
with at least $k$ neighbors in $L$. Since there are only ${|L|\choose k}$
options for these $k$ neighbors, there is some set of $k$ vertices in
$L_{1}\cup L_{2}$ with at least $\sqrt{n}/{|L|\choose k}$ common neighbors in
$D$. Since $|L|\leq C_{1}$ is bounded, we have $\sqrt{n}/{|L|\choose
k}\to\infty$ as $n\to\infty$, and so by adding the vertex $v$ we find that
$G\supseteq K_{k+1,\ell}$ for arbitrarily large $\ell$. However
$K_{k+1,\ell}\supseteq F\in\mathcal{F}$ for $\ell$ large enough, which is a
contradiction. ∎

######  Lemma 2.9.

For the vertex $z$ with $x_{z}=1$, we have $(1-\varepsilon)kn\leq
e(S_{1},\\{z\\}\cup L_{1}\cup L_{2})\leq(k+\varepsilon)n$.

###### Proof.

For the lower bound, we use Lemma 2.7:

$k(n-k)(1)\leq d(z)+e(S_{1},L_{1}\cup L_{2})+\frac{\varepsilon^{2}n}{2}\leq
e(S_{1},\\{z\\}\cup L_{1}\cup L_{2})+C_{1}+\frac{\varepsilon^{2}n}{2}\leq
e(S_{1},\\{z\\}\cup L_{1}\cup L_{2})+k\varepsilon n-k^{2}$

where the second inequality follows from $e(S_{1},\\{z\\})\geq d(z)-C_{1}$ and
the last inequality follows from $\varepsilon<2k$. For the upper bound,
suppose for a contradiction that $e(S_{1},\\{z\\}\cup L_{1}\cup
L_{2})>(k+\varepsilon)n$. Let $\gamma=\varepsilon/C_{1}$. We claim there are
at least $\gamma n$ vertices inside $S_{1}$ with at least $k$ neighbors in
$L_{1}\cup L_{2}$. If not then

$e(S_{1},L_{1}\cup L_{2})<(k-1)|S_{1}|+|L|\gamma n\leq(k-1)n+\varepsilon
n=(k+\varepsilon-1)n$

because $|S_{1}|\leq n$ and $|L|\leq C_{1}$. Since $d(z)\leq n$, we then have
$e(S_{1},\\{z\\}\cup L_{1}\cup L_{2})\leq(k+\varepsilon)n$, contradicting the
assumption. Hence there is a subset $D\subseteq S_{1}$ with at least $\gamma
n$ vertices such that every vertex in $D$ has at least $k$ neighbors in
$L_{1}\cup L_{2}$. Since there are at most ${|L|\choose k}$ options for these
$k$ neighbors, there exists some set of $k$ vertices in $L_{1}\cup L_{2}$ with
at least $\gamma n/{|L|\choose k}$ common neighbors in $S_{1}$. Since $|L|\leq
C_{1}$, we have $\gamma n/{|L|\choose k}\to\infty$ as $n\to\infty$, so adding
in the vertex $z$ means that $G\supseteq K_{k+1,\ell}$ for arbitrarily large
$\ell$, hence contains $F$, which is a contradiction. ∎

######  Lemma 2.10.

For all $v\in L^{\prime}$, $d(v)\geq\left(1-\frac{2}{5k^{3}}\right)n$ and
$x_{v}\geq 1-\frac{1}{4k^{3}}$.

###### Proof.

We first show $x_{v}\geq 1-\frac{1}{4k^{3}}$. Assume for a contradiction there
is some $v\in L^{\prime}$ with $x_{v}<1-\frac{1}{4k^{3}}$. Then the
eigenvector equation for $z$ gives

$\displaystyle k(n-k)$ $\displaystyle\leq\lambda^{2}<e(S_{1}(z),\\{z\\}\cup
L_{1}(z)\cup L_{2}(z)-\\{v\\})+|N_{1}(z)\cap
N_{1}(v)|x_{v}+\frac{\varepsilon^{2}n}{2}$
$\displaystyle<(k+\varepsilon)n-|S_{1}(z)\cap N_{1}(v)|+|N_{1}(z)\cap
N_{1}(v)|\left(1-\frac{1}{4k^{3}}\right)+\frac{\varepsilon^{2}n}{2}$
$\displaystyle=kn+\varepsilon n+|L_{1}(z)\cap N_{1}(v)|-|N_{1}(z)\cap
N_{1}(v)|\frac{1}{4k^{3}}+\frac{\varepsilon^{2}n}{2}$

where in the first line, the $\varepsilon^{2}n/2$ term absorbs both the
eigenweights of the vertices in $S$ (using inequality (iv)) and the weights
from the edges in $L$ since $|L|\leq C_{1}$. This implies

$\frac{1}{4k^{3}}|N_{1}(z)\cap N_{1}(v)|<\varepsilon
n+\frac{\varepsilon^{2}n}{2}+|L|+k^{2}\leq 2\varepsilon n.$

However, since $v\in L^{\prime}$ we have $x_{v}\geq\eta$ and so
$d(v)\geq(\eta-\varepsilon)n$, so $|N_{1}(z)\cap
N_{1}(v)|\geq(\eta-2\varepsilon)n.$ This contradicts inequality (v). Now since
$x_{v}\geq 1-\frac{1}{4k^{3}}$, we have
$d(v)\geq(x_{v}-\varepsilon)n\geq\left(1-\frac{1}{4k^{3}}-\varepsilon\right)n\geq\left(1-\frac{2}{5k^{3}}\right)n$
using inequality (vi). ∎

######  Lemma 2.11.

We have $|L^{\prime}|=k$.

###### Proof.

If $|L^{\prime}|\geq k+1$ then the common neighborhood of $k+1$ vertices in
$L^{\prime}$ would have at least $n-(k+1)\frac{2}{5k^{3}}n$ vertices, so $G$
contains $K_{k+1,\ell}$ for arbitrarily large $\ell$, a contradiction.

On the other hand if $|L^{\prime}|\leq k-1$ then a refinement of Lemma 2.7
applied to $z$ along with Lemma 2.9 gives the following contradiction,

$k(n-k)\leq d(z)+e(S_{1},L^{\prime}-\\{z\\})+e(S_{1},(L_{1}\cup
L_{2})-L^{\prime})\eta+\frac{\varepsilon^{2}n}{2}\leq(k-1)n+(k+\varepsilon)n\eta+\frac{\varepsilon^{2}n}{2}<(k-1/2)n,$

where the last inequality follows from (vii). ∎

Since $|L^{\prime}|=k$ and every vertex in $L^{\prime}$ has degree at least
$\left(1-\frac{2}{5k^{3}}\right)n$, the common neighborhood of $L^{\prime}$
has at least $(1-\frac{2}{5k^{2}})n$ vertices. Let $R$ be this common
neighborhood and $E=V-L^{\prime}-R$. Note that $|E|\leq\frac{2}{5k^{2}}n$. The
following lemma completes the proof of Proposition 2.2.

######  Lemma 2.12.

We have $E=\emptyset$.

###### Proof.

Suppose otherwise. Note that

$\sum_{v\in E}d_{E\cup R}(v)\leq 2e(E)+e(E,R)\leq 2C|E|+m|E|.$

Hence, there exists some $v\in E$ such that $d_{E\cup R}(v)\leq 2C+m$.
Consider the graph $G^{\prime}$ obtained by deleting all edges between $v$ and
$E\cup R$, and adding any missing edges between $v$ and $L^{\prime}$. The
decrease in $x^{T}Ax$ is at most $(2C+m)x_{v}\eta$, and the increase is at
least $x_{v}\left(1-\frac{1}{4k^{3}}\right)$, hence
$\lambda(G^{\prime})>\lambda(G)$ by inequality (viii).

Case 1: $\mathcal{F}$ is finite. Since $\lambda(G^{\prime})>\lambda(G)$,
$G^{\prime}\supseteq F_{0}$ for some $F_{0}\in\mathcal{F}$, and $F_{0}$ must
use the vertex $v$. Since $|V(F_{0})|\leq m^{\prime}<\infty$, there is some
$u\in R-V(F_{0})$, so by replacing $v$ with $u$ we find some $F_{1}\subseteq
G$ which is isomorphic to $F_{0}$, a contradiction.

Case 2: $\mathcal{F}$ is infinite. Let $E_{1}=E-v$, and note that
$G^{\prime}[E_{1}]$ is $\mathcal{F}$-free. Furthermore, any vertex in $E_{1}$
has neighbors only in $L^{\prime}$, $E_{1}$, and $R$. Then similarly to the
argument above we find $v_{2}\in E_{1}$ such that $d_{V-L^{\prime}}(v_{2})\leq
2C+m$. Delete all edges between $v_{2}$ and $V-L^{\prime}$ and add all edges
between $v_{2}$ and $L^{\prime}$ to obtain $G^{\prime\prime}$, and note that
$x^{T}Ax$ again increases, so that $\lambda(G^{\prime\prime})>\lambda(G)$. Set
$E_{2}=E_{1}-v_{2}$, and continue in this way until we obtain
$E_{i}=\emptyset$. Since the resulting graph $G^{(i)}$ satisfies
$\lambda(G^{(i)})>\lambda(G)$, $G^{(i)}$ is not $\mathcal{F}$-free. We now
consider whether we are in case (a), (b), or (c) in the statement of Theorem
1.1.

Subcase (a). Since $G^{(i)}\supseteq K_{k,n-k}$ and is not $\mathcal{F}$-free,
$G^{(i)}$ must have an edge either in $L^{\prime}$ or $R$; but since
$|R|\to\infty$, this implies that $G^{(i)}[L^{\prime}\cup R]$ is not
$\mathcal{F}$-free. Since no edges in $L^{\prime}\cup R$ were modified to get
from $G$ to $G^{(i)}$, this implies $G[L^{\prime}\cup R]$ is not
$\mathcal{F}$-free, a contradiction.

Subcase (b). Note that $e(G^{(i)}[R])=e(G[R])\leq{k\choose
2}-e(G[L^{\prime}])\leq{k\choose 2}$. Thus we can delete all edges in
$E(G^{(i)}[R])$ and add the same number of edges in $L^{\prime}$ to obtain a
subgraph of $H$ (which is therefore $\mathcal{F}$-free). However, it is easy
to see that this operation further increases $x^{T}Ax$ so that the spectral
radius of the resulting graph exceeds $\lambda(G)$, which is a contradiction.

Subcase (c). Noting $e(G^{(i)}[R])\leq{k\choose
2}-e(G[L^{\prime}])+1\leq{k\choose 2}+1$, the same argument, where we now
delete all but one edge in $E(G^{(i)}[R])$, gives the required contradiction.

∎

We observe that our arguments for the case where $\mathcal{F}$ is infinite
apply when $H=K_{k}+\overline{K_{n-k}}$ or $H=K_{k}+(K_{2}\cup K_{n-k-2})$,
but not when $H=K_{k}+X$ where $e(X)\geq 2$. This is because, after deleting
the edges in $R$ and adding the same number of edges in $L^{\prime}$, there is
more than one possible graph spanned by the remaining edges in $R$, hence we
do not necessarily end up with a subgraph of $H$.

###  2.3 Eigenweight estimates

We now know that there is a set $L^{\prime}$ of $k$ vertices which are
adjacent to every vertex in $R=V(G)\setminus L^{\prime}$. Any other vertex may
have at most $m-1$ neighbors in $V(G)\setminus L^{\prime}$, otherwise $G$
contains a $K_{k+1,m}$ and is not $F$-free. In this subsection we give more
refined estimates on the eigenvector entries.

######  Lemma 2.13.

For $v\in R$ we have $x_{v}\leq\frac{k}{\lambda-m}$.

###### Proof.

Let $v=\arg\max\\{x_{v}:v\in R\\}$. Then we have

$\lambda x_{v}=\sum_{\begin{subarray}{c}u\sim v\\\ u\in
L\end{subarray}}x_{u}+\sum_{\begin{subarray}{c}u\sim v\\\ u\in
R\end{subarray}}x_{u}\leq k+mx_{v}.$

∎

######  Lemma 2.14.

For $v\in R$ we have $x_{v}\leq
k\left(\frac{1}{\lambda}+\frac{d_{R}(v)}{\lambda(\lambda-m)}\right).$

###### Proof.

We have

$\lambda x_{v}\leq k+\sum_{w\in N_{R}(v)}x_{w}\leq
k+d_{R}(v)\frac{k}{\lambda-m}$

by Lemma 2.13. ∎

######  Lemma 2.15.

For $v\in R$, we have $x_{v}\geq\frac{k}{\lambda}-O(n^{-1}).$

###### Proof.

First we find a lower bound on eigenweights for vertices in $L^{\prime}$. Note
that

$\lambda=\lambda x_{z}\leq k+\sum_{v\in R}x_{v}\Longrightarrow\sum_{v\in
R}x_{v}\geq\lambda-k.$

Thus, for any $w\in L^{\prime}$ we have

$\lambda x_{w}\geq\sum_{v\in R}x_{v}\geq\lambda-k\Longrightarrow x_{w}\geq
1-O(n^{-1/2}).$

Hence, for $v\in R$ we have

$\lambda x_{v}\geq\sum_{w\in L^{\prime}}x_{w}\geq
k\left(1-O(n^{-1/2})\right)\Longrightarrow
x_{v}\geq\frac{k}{\lambda}-O(n^{-1}).$

∎

Combining the estimates of Lemma 2.14 and Lemma 2.15, we see that for $v\in
R$, $x_{v}=\frac{k}{\lambda}+\Theta(n^{-1})$.

###  2.4 Proof of Theorem 1.1

Note that Proposition 2.2 already proves Theorem 1.1 (a). Thus, let $G$ be the
spectral extremal graph for any remaining case (b)-(f). For notational
convenience, let $X=\overline{K_{n-k}}$ and $Q=0$ in case (b), and let
$X=K_{2}\cup\overline{K_{n-k-2}}$ and $Q=0$ in case (c). This way, we can
write $H=K_{k}+X$ in all cases. Note that, since we now know that $G\supseteq
K_{k,n-k}$, we have
$e(G)\leq\mathrm{ex}^{K_{k,n-k}}(n,\mathcal{F})=e(K_{k}+X)$.

######  Lemma 2.16.

The set $L^{\prime}$ induces a clique.

###### Proof.

Suppose not. We transform $G$ into $K_{k}+X$ by deleting all edges in $R$ and
then adding all edges in $X$ and in $G[L^{\prime}]$. Note $e(R)\leq
e(X)+\binom{k}{2}$, since $G\supseteq K_{k,n-k}$ and
$H\in\mathrm{EX}^{K_{k,n-k}}(n,\mathcal{F})$. At least one added edge was in
$L^{\prime}$ and thus increased $x^{T}Ax$ by at least
$\left(1-\frac{1}{4k^{3}}\right)^{2}>\frac{1}{2}$. Thus the net change in
$x^{T}Ax$ is at least

$\frac{1}{2}+e(X)\left(\frac{k}{\lambda}-O(n^{-1})\right)^{2}-\left(e(X)+{k\choose
2}\right)\left(\frac{k}{\lambda}+O(n^{-1})\right)^{2}$
$\geq\frac{1}{2}-e(X)\cdot O\left((\lambda n)^{-1}\right)-{k\choose
2}\left(\frac{k}{\lambda}+O(n^{-1})\right)^{2}>\frac{1}{2}-Q\cdot
O(n^{-1/2})-{k\choose 2}\cdot O(n^{-1})>0$

which is a contradiction. ∎

Lemma 2.16 now gives that all vertices in $L^{\prime}$ are dominating and
hence all have eigenvector entry equal to $1$. This means that the error term
in Lemma 2.15 can be removed, and

$x_{v}\geq\frac{k}{\lambda}$ (1)

Armed with this we may now prove the theorem.

###### Proof Theorem 1.1 (e), (f).

We first only assume only (e). We already know that $G=K_{k}+Y$ for some $Y$.
Now, we can delete all edges in $R$ and add the edges in $X$ to transform $G$
into $X$. The change in $x^{T}Ax$ is at least

$\displaystyle-e(Y)\left(\frac{k}{\lambda}+O(n^{-1})\right)^{2}+e(X)\left(\frac{k}{\lambda}\right)^{2}$
$\displaystyle\geq(e(X)-e(Y))\frac{k^{2}}{\lambda^{2}}-e(Y)O(n^{-3/2}))$
$\displaystyle\geq(e(X)-e(Y))\frac{k^{2}}{\lambda^{2}}-O(n)\cdot O(n^{-3/2})$

The last quantity above cannot be positive, and so $e(X)-e(Y)=O(n^{1/2})$,
which proves the first claim. We already know that $\Delta(Y)$ is bounded (by
$m$).

Now assume (f). We first improve bounds on $x_{v}$ for $v\in Y$. Note that all
but a bounded number of $v\in R=V(Y)$ have $d_{Y}(v)\leq d$. By the above,
$e(X)-e(Y)=O(n^{1/2})$, so the number of vertices in $Y$ with degree less than
$d$ is $O(n^{1/2})$. Call a vertex $v\in R$ bad if $d_{R}(v)\neq d$ or $v\sim
u$ and $d_{R}(u)\neq d$ for some $u\in Y$, and good otherwise. Since
$\Delta(R)$ is bounded, the number of bad vertices in $R$ is $O(n^{1/2})$. Now
for any good vertex $v$,

$\displaystyle\lambda^{2}x_{v}$ $\displaystyle=\sum_{u\in L^{\prime}}\lambda
x_{u}+dk+\sum_{u\in N_{R}(v)}\sum_{w\in N_{R}(u)}x_{w}$ $\displaystyle\geq
k\lambda+dk+d^{2}\frac{k}{\lambda}$ $\displaystyle x_{v}$
$\displaystyle\geq\frac{k}{\lambda}+\frac{kd}{\lambda^{2}}+\frac{kd^{2}}{\lambda^{3}}.$

On the other hand,

$\displaystyle\lambda^{2}x_{v}$ $\displaystyle=\sum_{u\in L^{\prime}}\lambda
x_{u}+dk+\sum_{u\in N_{R}(v)}\sum_{w\in N_{R}(u)}x_{w}$ $\displaystyle\leq
k\lambda+dk+d^{2}\frac{k}{\lambda-m}$ $\displaystyle x_{v}$
$\displaystyle\leq\frac{k}{\lambda}+\frac{kd}{\lambda^{2}}+\frac{kd^{2}}{\lambda^{2}(\lambda-m).}$

Combining the two estimates one obtains that
$x_{v}=\frac{k}{\lambda}+\frac{kd}{\lambda^{2}}+\frac{kd^{2}}{\lambda^{3}}+O(n^{-2})$.
Now we delete all edges in $Y$ and add all edges in $X$. Note that at most
$m\cdot O(n^{1/2})=O(n^{1/2})$ edges of $Y$ are incident to a bad vertex. It
follows that for some $N=O(n^{1/2})$ , there is a set of $N$ edges of $X$ and
a set of $N$ edges of $Y$ which contain all edges of $X$ or $Y$, respectively,
incident to a bad vertex. Then the change in $x^{T}Ax$ is at least

$\displaystyle-(e(Y)-N)\left(\frac{k}{\lambda}+\frac{kd}{\lambda^{2}}+\frac{kd^{2}}{\lambda^{3}}+O(n^{-2})\right)^{2}+(e(X)-N)\left(\frac{k}{\lambda}+\frac{kd}{\lambda^{2}}+\frac{kd^{2}}{\lambda^{3}}\right)^{2}$
$\displaystyle-N\left(\frac{k}{\lambda}+O(n^{-1})\right)^{2}+N\left(\frac{k}{\lambda}\right)^{2}$
$\displaystyle\geq(e(X)-e(Y))\frac{k^{2}}{\lambda^{2}}-e(Y)\frac{k}{\lambda}\cdot
O(n^{-2})-N\frac{k}{\lambda}\cdot O(n^{-1})$
$\displaystyle\geq(e(X)-e(Y))\cdot O(n^{-1})-Qn\cdot
O(n^{-5/2})-O(n^{1/2})\cdot O(n^{-3/2})$

If $e(X)-e(Y)=\omega(1)$ then the quantity above is positive, a contradiction.
Hence $e(X)-e(Y)=O(1)$, which implies that the number of bad vertices is in
fact $O(1)$. Therefore we can take $N=O(1)$ and repeat the previous argument
to show that when we transform $K_{k}+Y$ to $K_{K}+X$ the change in $x^{T}Ax$
is at least

$(e(X)-e(Y))\cdot O(n^{-1})-Qn\cdot O(n^{-5/2})-O(1)\cdot O(n^{-3/2})$

which implies $e(X)-e(Y)=0$; hence
$G\in\mathrm{EX}^{K_{k}+\overline{K_{n-k}}}(n,\mathcal{F})$. ∎

###### Proof of Theorem 1.1 (b), (c), (d).

From Proposition 2.1, we have $e(X)=Qn+O(1)$ for some $Q\in\\{0,1/2,2/3\\}$.
The first case is $Q=0$, in other words $e(X)=O(1)$ and consequently
$e(R)=O(1)$. If
$G\not\in\mathrm{EX}^{K_{k}+\overline{K_{n-k}}}(n,\mathcal{F})$, then delete
all edges in $R$ and add all edges in $X$ to make the graph isomorphic to
$K_{k}+X$. Let $s,t$ be the number of edges deleted and added, respectively,
which satisfy $s<t=O(1)$. Then the change in $x^{T}Ax$ is at least

$-s\left(\frac{k}{\lambda}+O(n^{-1})\right)^{2}+t\left(\frac{k}{\lambda}\right)^{2}\geq(t-s)\frac{k^{2}}{\lambda^{2}}-O\left((\lambda
n)^{-1}\right)-O(n^{-2})>0$

which is a contradiction. Actually, this argument proves the following fact:
whenever $K_{k}+X$ can be obtained from $K_{k}+Y$ by deleting a bounded number
of edges and adding more edges than were deleted, we have
$\lambda_{1}(K_{k}+X)>\lambda_{1}(K_{k}+Y)$.

The second case is $Q=1/2$. We first note that since $G$ is
$\mathcal{F}$-saturated, only a bounded number of vertices $v\in R$ have
$d_{R}(v)\geq 2$, by the same argument as Proposition 2.1. On the other hand,
$e(R)$ must be unbounded, or the same argument as in the case $Q=0$ would show
$\lambda_{1}(G)<\lambda_{1}(K_{k}+X)$. Therefore, the argument in Proposition
2.1 shows that $G[R]$ has at most one isolated vertex. Thus $G$ is obtained
from a maximal union of $P_{2}$ by deleting and adding a bounded number of
edges. Since the same is true of $K_{k}+X$, we can delete and add a bounded
number of edges to transform $G$ into a graph isomorphic to $K_{k}+X$. By the
fact mentioned above, this implies that
$G\in\mathrm{EX}^{K_{k}+\overline{K_{n-k}}}(n,\mathcal{F})$.

The final case $Q=2/3$ is similar. We find that $Y$ is the union of copies of
$P_{3}$ and smaller graphs, plus a bounded number of graphs of bounded order.
The number of copies of $P_{3}$ must be unbounded; otherwise, we have
$e(Y)<\frac{2}{3}n$, and we may substitute $t-s=\Omega(n)$ in the argument
above, and find

$-s\left(\frac{k}{\lambda}+O(n^{-1})\right)^{2}+t\left(\frac{k}{\lambda}\right)^{2}\geq\Omega(n)\frac{k^{2}}{\lambda^{2}}-O(n)\cdot((\lambda
n)^{-1})-O(n)\cdot O(n^{-2})>0$

which gives a contradiction. The argument of Proposition 2.1 then shows that
$G$ is obtained by deleting and adding a bounded number of edges to a maximal
union of $P_{3}$. By the fact mentioned above, this implies that
$G\in\mathrm{EX}^{K_{k}+\overline{K_{n-k}}}(n,\mathcal{F})$. ∎

Note that the conclusions stated in (b) and (c) follow because in these cases
$\mathrm{EX}^{K_{k}+\overline{K_{k,n-k}}}(n,\mathcal{F})$ contains a single
graph up to isomorphism.

###  2.5 A counterexample

###### Proof of Proposition 1.2.

Let $\mathcal{F}$ consist of the all the following graphs:

  1. 1.

$3\cdot K_{1,4}$;

  2. 2.

$K_{2,6}\cup X_{5}\cup Y_{5}$, for all connected graphs $X_{5},Y_{5}$ on 5
vertices;

  3. 3.

$K_{2,6}\cup K_{1,3}\cup X_{5}$, for all connected graphs $X_{5}$ on 5
vertices;

  4. 4.

$K_{2,6}\cup X_{9}$, for all connected graphs $X_{9}$ on 9 vertices;

  5. 5.

$K_{2,6}\cup X_{8}$, for all connected graphs $X_{8}$ on 8 vertices except for
$P_{8}$;

  6. 6.

$X_{5}\cup Y_{5}\cup Z_{5}\cup W_{5}$, for all connected graphs
$X_{5},Y_{5},Z_{5},W_{5}$ on 5 vertices;

  7. 7.

$C_{i}\cup C_{j}\cup C_{k}$ for $3\leq i,j,k\leq 7$.

We have chosen a very large family $\mathcal{F}$, which makes the extremal
problem for $\mathcal{F}$ easy. We suspect that a similar counterexample could
be obtained with an even smaller family $\mathcal{F}$.

######  Lemma 2.17.

If $n\equiv 2\pmod{4}$ is large enough, then we have that
$\mathrm{EX}(n,\mathcal{F})=K_{2}+\left(P_{8}\cup\frac{n-10}{4}\cdot
P_{4}\right)$.

###### Proof.

One can check that $H=K_{2}+\left(P_{8}\cup\frac{n-10}{4}\cdot P_{4}\right)$
is $\mathcal{F}$-free. Now let $H^{\prime}$ be the extremal graph, so that

$e(H^{\prime})\geq 2(n-2)+1+7+\frac{n-10}{4}\cdot
3=\frac{11}{4}n-4+1+7-\frac{15}{2}=\frac{11}{4}n-\frac{7}{2}.$

By forbidding (1), we may choose vertices $x,y$ such that any other vertex $z$
has at most $11$ neighbors in $V(G)\setminus\\{x,y\\}$. Consider the
components of $G-\\{x,y\\}$; these are either graphs on 3 or 4 vertices
containing a $C_{3}$ or $C_{4}$, respectively (and by (7) there are at most 2
of each type), or connected graph of order at least $5$ (and by (6) there are
at most 3 of these), or trees on at most $4$ vertices. We claim that the order
of any graphs of the second type is at most $5\cdot 11^{9}$. Let $K$ be such a
component with $|V(K)|\geq 5\cdot 11^{9}$; let $B_{r}(v)$ denote $\\{u\in
V(K):d_{K}(u,v)\leq r\\}$. Then for any $v$, $|B_{8}(v)|\leq
1+11+\cdots+11^{8}\leq 11^{9}$ since $\Delta(K)\leq 11$, and consequently we
can find vertices $v_{1},\ldots,v_{5}$ such that for $i\neq j$,
$d(v_{i},v_{j})\geq 9$. This implies that $B_{4}(v_{i})$, $1\leq i\leq 5$,
induce 5 disjoint connected graphs on at least 5 vertices, which contradicts
(6). Putting this all together, we find a partition $V(H^{\prime})=U\sqcup B$
where $U$ is a union of trees of order at most 4, $|B|\leq 2+2\cdot 3+2\cdot
4+3\cdot 5\cdot 11^{9}\leq 11^{11}$, and $x,y\in B$. Hence, since
$\Delta(G[B-x-y])\leq 11$, we have

$\frac{11}{4}n-\frac{7}{2}\leq d(x)+d(y)+11^{11}\cdot 11+\frac{n}{4}\cdot
3\Longrightarrow d(x)+d(y)\geq 2n-\frac{7}{2}-11^{12}\geq 2n-11^{13}.$

So $d(x)\geq n-11^{13}$, $d(y)\geq n-11^{13}$, and $|N(x)\cap N(y)|\geq
n-2\cdot 11^{13}$. Note that $x$ and $y$ are contained in disjoint copies of
$K_{1,4}$ so by (1), every other vertex of $H^{\prime}$ has at most 3
neighbors outside $\\{x,y\\}$. Now we have

$e(N(x)\cap N(y))\geq\frac{11}{4}n-\frac{7}{2}-2(n-1)-2\cdot 11^{13}\cdot
5=\frac{3}{4}n-O(1)$

which implies we can find 2 disjoint edges in $N(x)\cap N(y)$. Hence $x$ and
$y$ are contained in disjoint copies of $C_{3}$. Thus by (5) and (7), all
components of $G-x-y$, except possibly one (which by (4) can be of order at
most $8$), are trees of order at most 4. Such a graph cannot have more edges
than $H$. If $e(H^{\prime})=e(H)$, then $G-x-y=a\cdot P_{4}\cup b\cdot
K_{1,3}\cup K$, where $K$ is a connected graph on 8 vertices (using (4)). By
(5), we have $K=P_{8}$; but then by (3), $b=0$. It follows that
$H^{\prime}\subseteq H$, hence $H^{\prime}\simeq H$. ∎

As in the proof above, let $H=K_{2}+\left(P_{8}\cup\frac{n-10}{4}\cdot
P_{4}\right)$. Let $G=K_{2}+\frac{n-2}{4}\cdot K_{1,3}$. One can check that
$G$ is also $\mathcal{F}$-free. We now show that
$\lambda_{1}(G)>\lambda_{1}(H)$. Note that $G$ and $H$ have equitable
partitions with quotient matrices

$B_{G}=\begin{bmatrix}1&\frac{1}{4}(n-2)&\frac{3}{4}(n-2)\\\ 2&0&3\\\ 2&1&0\\\
\end{bmatrix},\
B_{H}=\begin{bmatrix}1&\frac{1}{2}(n-10)&\frac{1}{2}(n-10)&2&2&2&2\\\
2&1&1&0&0&0&0\\\ 2&1&0&0&0&0&0\\\ 2&0&0&1&1&0&0\\\ 2&0&0&1&0&1&0\\\
2&0&0&0&1&0&1\\\ 2&0&0&0&0&1&0\end{bmatrix}.$

The characteristic polynomials are

$\displaystyle p_{G}(x)$ $\displaystyle=x^{3}-x^{2}+(1-2n)x+9-3n$
$\displaystyle p_{H}(x)$
$\displaystyle=x^{7}-3x^{6}+(3-2n)x^{5}+(3+n)x^{4}+(7n-22)x^{3}+(1-n)x^{2}+(10-4n)x+3-n.$

By the Weyl inequalities, $\lambda_{1}(G),\lambda_{1}(H)\geq\sqrt{2(n-2)}$ and
$\lambda_{2}(G),\lambda_{2}(H)<\sqrt{2(n-2)}$. Thus $p_{G}$ is negative on
$[\sqrt{2(n-2)},\lambda_{1}(G))$ and positive on $(\lambda_{1}(G),\infty)$,
and $p_{H}$ is negative on $[\sqrt{2(n-2)},\lambda_{1}(H))$ and positive on
$(\lambda_{1}(H),\infty)$. So, to show $\lambda_{1}(G)>\lambda_{1}(H)$ it
suffices to find some $x>\sqrt{2(n-2)}$ such that $p_{G}(x)<0<p_{H}(x)$. For a
constant $C>0$, we compute

$\displaystyle p_{G}(\sqrt{2(n-2)}+5/4+Cn^{-1/2})$
$\displaystyle=4C\sqrt{n}-\frac{13}{8\sqrt{2}}\sqrt{n-2}+o(\sqrt{n})$
$\displaystyle p_{H}(\sqrt{2(n-2)}+5/4+Cn^{-1/2})$
$\displaystyle=16Cn^{5/2}-\frac{5}{2\sqrt{2}}n^{2}\sqrt{n-2}+o(n^{5/2})$

as $n\to\infty$. Choosing $\frac{13}{32\sqrt{2}}<C<\frac{5}{32\sqrt{2}}$, we
find that $p_{G}(\sqrt{2(n-2)}+5/4+Cn^{-1/2})\to-\infty$ while
$p_{H}(\sqrt{2(n-2)}+5/4+Cn^{-1/2})\to\infty$. ∎

###  2.6 Forbidden trees

###### Proof of Proposition 1.4.

We will assume that all labelled trees have vertex set $[n]$ and let $T$
denote a uniformly random labelled tree on $[n]$. For $i\neq j$ in $[n]$, let
$A_{ij}$ be the event that $i\sim j$, $i$ has a neighbor different from $j$
which is adjacent precisely to $i$ and 2 leaves, and $j$ has a neighbor
different from $i$ which is adjacent precisely to $j$ and 2 leaves; let
$X_{ij}$ be the indicator function of $A_{ij}$. Observe that if $A_{ij}$
occurs then $T$ is of the form described in the application ‘Almost all trees’
of Theorem 1.1, for some $k\geq 4$. Therefore, defining $X=\sum_{i<j}X_{ij}$,
it suffices to show that $\mathbb{P}[X=0]\to 0$. Our argument is a variation
on [20] in which it was shown that almost all labelled trees have a vertex
with two leaves.

For $i,j,k,\ell\in[n]$ (not necessarily distinct), we define $N_{n}(ij)$ to be
the number of labelled trees on $[n]$ which contain the edge $ij$, and we
define $N_{n}(ij,k\ell)$ to be the number of labelled trees on $[n]$ which
contain both edges $ij$ and $k\ell$. From Lemma 6 of [45], we have the
following formulas.

######  Lemma 2.18.

For any $i,j,k,\ell$ distinct we have:

  * (a)

$N_{n}(ij)=2n^{n-3}$

  * (b)

$N_{n}(ij,ik)=3n^{n-4}$

  * (c)

$N_{n}(ij,k\ell)=4n^{n-4}$.

Next we estimate $\mathbb{E}[X]$ and $\mathbb{E}[X^{2}]$. To specify a tree
$T$ such that $A_{ij}$ occurs, we choose the neighbor of $i$ and its pair of
leaves, then we choose the neighbor of $j$ and its pair of leaves, and then
attach a tree containing the edge $ij$ and the unused vertices in $[n]$. For a
constant $c$ we have that $(n-c)^{n-c}=n^{n-c}e^{-c}+\Theta(n^{n-c-2})$. This
gives:

$\displaystyle\mathbb{P}[A_{ij}]$
$\displaystyle=\frac{1}{n^{n-2}}(n-2){n-3\choose 2}(n-5){n-6\choose
2}N_{n-6}(ij)=\frac{1}{2e^{6}n}+o(n^{-1})$ $\displaystyle\mathbb{E}[X]$
$\displaystyle={n\choose
2}\left(\frac{1}{2e^{6}n}+o(n^{-1})\right)=\frac{n}{4e^{6}}+o(n)$
$\displaystyle\mathbb{E}[X]^{2}$
$\displaystyle=\frac{n^{2}}{16e^{12}}+o(n^{2}).$

Next we consider $A_{ij}\cap A_{ik}$. There are 2 types of trees which realize
this event: (i) those in which the special neighbor of $i$ in $A_{ij}$ is the
same as the special neighbor of $i$ in $A_{ik}$ (the special neighbor of $j$
and $k$ must be distinct in a tree), and (ii) those in which they are
different. So we have

$\displaystyle\mathbb{P}[A_{ij}\cap A_{ik}]$
$\displaystyle\leq\frac{n^{9}3n^{n-13}+n^{12}3n^{n-16}}{n^{n-2}}=O(n^{-2}).$

Finally, if $i,j,k,\ell$ are distinct, then we have

$\begin{aligned} \mathbb{P}[A_{ij}\cap A_{k\ell}]&\leq\frac{n^{4}{n\choose
2}^{4}4(n-12)^{n-16}}{n^{n-2}}=\frac{1}{4e^{12}n^{2}}+o(n^{-2})\end{aligned}.$

Therefore, we have

$\displaystyle\mathbb{E}[X^{2}]$
$\displaystyle=\sum_{i<j}\mathbb{P}[A_{ij}]+\sum_{i,j,k}\mathbb{P}[A_{ij}\cap
A_{ik}]+\sum_{\\{i,j\\},\\{k,\ell\\}\text{ disjoint}}\mathbb{P}[A_{ij}\cap
A_{k\ell}]$ $\displaystyle\leq{n\choose 2}\frac{1}{e^{6}n}+n^{3}\cdot
O(n^{-2})+{n\choose 2}{n-2\choose
2}\left(\frac{1}{4e^{12}n^{2}}+o(n^{-2})\right)$
$\displaystyle=\frac{n^{2}}{16e^{12}}+o(n^{2}).$

Therefore $\mathrm{Var}(X)=o(n^{2})$, and Chebyshev’s inequality gives

$\mathbb{P}[X=0]\leq\mathbb{P}\left[|X-\mathbb{E}[X]|\geq\frac{n}{5e^{6}}\right]\leq\frac{25e^{12}\cdot
o(n^{2})}{n^{2}}\to 0.$

∎

##  3 Alpha spectral extremal results

Let $\mathcal{F}$ be the family of graphs in Theorem 1.5. We first consider
the case where $\mathcal{F}$ contains some bipartite graph $F$ with a vertex
$v$ such that $F-v$ is a forest.

######  Lemma 3.1.

There exists $c=c(F)$ such that, for any graph $G$ with $V(G)=U\sqcup W$ and

$2e(U)+e(U,W)>3c|U|+c|W|,$

there exists a copy of $F-v$ in $G$ such that $N_{F}(v)$ embeds in $U$.

###### Proof.

Let $v$ be the vertex such that $F-v$ is a forest, and let
$\Delta=\Delta(F-v)$. Let $V(F)=A\sqcup B$ be a proper coloring with $v\in B$.
Then $F-v$ has a proper coloring $A\sqcup(B\setminus\\{v\\})$, and $A$
contains all the neighbors of $v$ in $F$. Set $a=|A|$ and $b=|B|$.

Let $T$ be a forest obtained from 2 copies of $F-v$ by selecting a vertex from
$A$ from each component (observe that every component of $F-v$ must contain a
vertex in $A$) and making it adjacent to the corresponding vertex in the other
copy of $F-v$. Now if $t=|V(T)|=2(|V(F)|-1)$ then it is known that
$\mathrm{ex}(n,T)\leq(t-2)n$.

Now consider the graph $G$ with $V(G)=U\sqcup W$, appearing in the statement
of this lemma. If $e(U)>(t/2-2)|U|$ then $G[U]\supseteq F-v$ and we are done.
If $e(U,W)>(t-2)(|U|+|W|)$ then $G[U,W]\supseteq T$, and by the design of $T$
this means there is a copy of $F-v$ in $G$ in which $A$ embeds in $U$. Hence,
to guarantee the conclusion of the lemma, it suffices that $e(U)>(t-2)|U|$ or
$e(U,W)>(t-2)(|U|+|W|)$, and we may take e.g. $c=t$. ∎

If $G$ is any $F$-free graph, then for any $u\in V(G)$, there cannot be a copy
of $F-v$ in $G[N_{1}(u)\cup N_{2}(u)]$ such that all the neighbors of
$N_{F}(v)$ embed in $N_{1}(u)$. Applying Lemma 3.1 gives

$2e(N_{1}(v))+e(N_{1}(v),N_{2}(v))\leq 3cd(v)+c(n-d(v)-1)=2cd(v)+c(n-1)\leq
3cn.$ (2)

If $\mathcal{F}$ does not contain a graph $F$ so that $F-v$ is a forest, then
we assume that $\mathrm{ex}(n,\mathcal{F})=O(n)$. By choosing $c$ large enough
in Equation 2, we may assume that the equation holds in either case, for some
$c=c(\mathcal{F})$, for any $\mathcal{F}$-free graph.

######  Lemma 3.2.

([53]) Let $G$ be a graph and $0\leq\alpha\leq 1$, then

$\alpha\Delta(G)\leq\lambda_{\alpha}(G)\leq\alpha\Delta(G)+(1-\alpha)\lambda(G).$

######  Lemma 3.3.

For any $\mathcal{F}$-free graph $G$ we have $\lambda(G)\leq\sqrt{k(n-k)}+k$.

###### Proof.

We have
$\lambda(G)\leq\mathrm{spex}(n,\mathcal{F})\leq\lambda(K_{k}+(K_{2}\cup\overline{K_{n-k-2}}))$,
and by the Weyl inequalities we have

$\lambda(K_{k}+(K_{2}\cup\overline{K_{n-k-2}}))\leq\lambda(K_{k,n-k})+k=\sqrt{k(n-k)}+k.$

∎

######  Lemma 3.4.

Let $G$ be a connected graph and let $y$ be a Perron vector of
$A_{\alpha}(G)$. Then for all $v\in V(G)$, we have

$\displaystyle\lambda_{\alpha}(G)y_{v}$ $\displaystyle=\alpha
d(v)y_{v}+(1-\alpha)\sum_{u\sim v}y_{u}$
$\displaystyle\lambda_{\alpha}^{2}(G)y_{v}$ $\displaystyle=\alpha
d(v)\lambda_{\alpha}(G)y_{v}+\alpha(1-\alpha)\sum_{u\sim
v}d(u)y_{u}+(1-\alpha)^{2}\sum_{w\sim v}\sum_{u\sim w}y_{u}$
$\displaystyle\lambda_{\alpha}(G)$
$\displaystyle=\frac{1}{y^{T}y}\left(\alpha\sum_{v\in
V(G)}d(v)y_{v}^{2}+(1-\alpha)\sum_{uv\in E(G)}y_{u}y_{v}\right).$

Now let $G$ be a graph in $\mathrm{SPEX}_{\alpha}(n,\mathcal{F})$ and let $x$
be its Perron vector, scaled so that its largest entry is $x_{z}=1$. Let
$\sigma$ be a positive constant satisfying $3c\sigma<1-\alpha$ and
$(3c+1)\sigma<\alpha(1-\alpha)$. With $V=V(G)$, let $L=\\{v\in
V:x_{v}>\sigma\\}$ and let $S=V-L$. Also, write $L_{i}(v)=L\cap N_{i}(v)$ and
$S_{i}(v)=S\cap N_{i}(v)$. As in Section 2, all claims below are only asserted
for $n$ large enough unless stated otherwise.

######  Lemma 3.5.

For $n$ sufficiently large, we have that

$\mathrm{spex}_{\alpha}(n,\mathcal{F})\geq\max\left\\{\alpha
n+\frac{k}{\alpha}-k-1-\frac{2k(k+1)}{\alpha^{3}n-\alpha^{2}(k+1+\alpha)+\alpha
k},\alpha n+\frac{k}{\alpha}-k-1-\alpha,\alpha(n-1)\right\\}$

###### Proof.

To obtain the lower bound, observe that we have assumed
$K_{k}+\overline{K_{n-k}}$ is $\mathcal{F}$-free. Thus,
$\mathrm{spex}_{\alpha}(n,\mathcal{F})\geq\lambda_{\alpha}(K_{k}+\overline{K_{n-k}})$
and

$\lambda_{\alpha}(K_{k}+\overline{K_{n-k}})\geq\max\left\\{\alpha
n+\frac{k}{\alpha}-k-1-\frac{2k(k+1)}{\alpha^{3}n-\alpha^{2}(k+1+\alpha)+\alpha
k},\alpha n+\frac{k}{\alpha}-k-1-\alpha,\alpha(n-1)\right\\},$

see for example [7]. ∎

######  Lemma 3.6.

For all $v\in L$, we have $d(v)\geq\left(1-\dfrac{1}{(k+1)\sqrt{n}}\right)n$.

###### Proof.

Suppose to the contrary that there is some $v\in L$ with
$d(v)<\left(1-\dfrac{1}{(k+1)\sqrt{n}}\right)n$. Then,

$\displaystyle\lambda_{\alpha}^{2}x_{v}$ $\displaystyle=\alpha
d(v)\lambda_{\alpha}x_{v}+\alpha(1-\alpha)\sum_{u\sim
v}d(u)x_{u}+(1-\alpha)^{2}\sum_{w\sim v}\sum_{u\sim w}x_{u}$
$\displaystyle\leq\alpha
d(v)\lambda_{\alpha}x_{v}+\alpha(1-\alpha)(d(v)+2e(N_{1}(v))+e(N_{1}(v),N_{2}(v)))$
$\displaystyle+(1-\alpha)^{2}(d(v)+2e(N_{1}(v))+e(N_{1}(v),N_{2}(v)))$
$\displaystyle<\alpha
d(v)\lambda_{\alpha}x_{v}+\alpha(1-\alpha)(d(v)+3cn)+(1-\alpha)^{2}(d(v)+3cn)$
$\displaystyle<\alpha d(v)\lambda_{\alpha}x_{v}+(1-\alpha)(3c+1)n.$

Then

$\lambda_{\alpha}(\lambda_{\alpha}-\alpha d(v))x_{v}<(1-\alpha)(3c+1)n.$

On the other hand, from Lemma 3.5 and
$d(v)<\left(1-\dfrac{1}{(k+1)\sqrt{n}}\right)n$ we have

$\lambda_{\alpha}(\lambda_{\alpha}-\alpha
d(v))x_{v}>\alpha(n-1)\left[\alpha(n-1)-\alpha\left(1-\dfrac{1}{(k+1)\sqrt{n}}\right)n\right]\sigma=\Omega(n^{3/2}).$

which gives a contradiction. ∎

######  Lemma 3.7.

There is some $F^{\prime}\in\mathcal{F}$ such that $F^{\prime}\subseteq
K_{k+1,\infty}$. Consequently, $F^{\prime}\subseteq K_{k+1,m}$ for some fixed
$m$.

###### Proof.

If not, then $K_{k+1,n-k-1}$ is $\mathcal{F}$-free. Since
$\lambda(K_{k+1,n-k-1})>\lambda(K_{k}+(K_{2}\cup\overline{K_{n-k-2}})$, this
contradicts the fact that
$\mathrm{spex}(n,\mathcal{F})\leq\lambda(K_{k}+(K_{2}\cup\overline{K_{n-k-2}})$.
∎

######  Lemma 3.8.

The size of $L$ is $k$.

###### Proof.

First assume for a contradiction that $|L|\geq k+1$. Then there is a set
$L^{\prime}\subseteq L$ with $L^{\prime}=k+1$. Therefore, every vertex $v\in
L^{\prime}$ has $d(v)\geq\left(1-\dfrac{1}{(k+1)\sqrt{n}}\right)n$, and the
common neighborhood of the vertices in $L^{\prime}$ has at least $n-\sqrt{n}$
vertices. This implies that for $n$ large enough, $G\supseteq
K_{k+1,n-\sqrt{n}}$ which contradicts Lemma 3.7.

To show $|L|\geq k$, assume to the contrary that $|L|\leq k-1$. In cases (b)
and (c), we have

$\displaystyle\lambda_{\alpha}^{2}$
$\displaystyle=\lambda_{\alpha}^{2}x_{z}=\alpha
d(z)\lambda_{\alpha}x_{z}+\alpha(1-\alpha)\sum_{u\sim
z}d(u)x_{u}+(1-\alpha)^{2}\sum_{w\sim z}\sum_{u\sim w}x_{u}$
$\displaystyle\leq\alpha d(z)\lambda_{\alpha}+\alpha(1-\alpha)\left(\sum_{u\in
L_{1}(z)}d(u)x_{u}+\sum_{u\in S_{1}(z)}d(u)x_{u}\right)$
$\displaystyle+(1-\alpha)^{2}\left(\sum_{w\sim z}\sum_{u\in
L_{1}(w)}x_{u}+\sum_{w\sim z}\sum_{u\in S_{1}(w)}x_{u}\right)$
$\displaystyle<\alpha
d(z)\lambda_{\alpha}+\alpha(1-\alpha)\left((k-2)n+(d(z)+2e(N_{1}(z))+e(N_{1}(z),N_{2}(z)))\sigma\right)$
$\displaystyle+(1-\alpha)^{2}\left((k-1)n+(2e(N_{1}(z))+e(N_{1}(z),N_{2}(z)))\sigma\right)$
$\displaystyle<\alpha
d(z)\lambda_{\alpha}+\alpha(1-\alpha)\left((k-2)n+(d(z)+3cn)\sigma\right)+(1-\alpha)^{2}\left(3cn\sigma+(k-1)n\right)$
$\displaystyle\leq\alpha d(z)\lambda_{\alpha}+(1-\alpha)((k-1)n+3cn\sigma).$

Therefore,

$\displaystyle\lambda_{\alpha}(\lambda_{\alpha}-\alpha d(z))$
$\displaystyle<(1-\alpha)(k-1+3c\sigma)n.$

But from Lemma 3.5 we have

$\displaystyle\lambda_{\alpha}(\lambda_{\alpha}-\alpha d(z))$
$\displaystyle\geq\alpha(n-1)\left(\alpha
n+\frac{k}{\alpha}-k-1-\frac{4k^{2}}{\alpha^{4}n}-\alpha(n-1)\right)=(1-\alpha)(k-\alpha)n+O(1)$

using $2k(k+1)/(\alpha^{3}n-\alpha^{2}(k+1+\alpha)+ak)\leq
4k^{2}/(\alpha^{4}n)$. Since $3c\sigma<1-\alpha$, these two inequalities give
a contradiction. ∎

It follows from Lemma 3.6 and Lemma 3.8 that $L=k$ and for all $v\in L,$
$d(v)\geq\left(1-\dfrac{1}{(k+1)\sqrt{n}}\right)n$. Let $R$ denote the common
neighborhood of all vertices in $L$. Then
$|R|\geq\left(1-\dfrac{k}{(k+1)\sqrt{n}}\right)n>n-\sqrt{n}$. Let
$E=S\setminus R$, so that $|E|\leq\sqrt{n}$. We will show that $E=\emptyset$
and so $G\supseteq K_{k,n-k}$.

######  Lemma 3.9.

For any $v\in L$, we have $x_{v}\geq 1-\alpha$.

###### Proof.

Assume to the contrary that there is some $v\in L$ with $x_{v}<1-\alpha$. Then
the second-degree eigenvector equation with respect to $z$ gives

$\displaystyle\lambda_{\alpha}(\lambda_{\alpha}-\alpha d(z))$
$\displaystyle\leq\alpha(1-\alpha)\sum_{u\sim
z}d(u)x_{u}+(1-\alpha)^{2}\sum_{w\sim z}\sum_{u\sim w}x_{u}$
$\displaystyle\leq\alpha(1-\alpha)\left(\sum_{u\in
L_{1}(z)}d(u)x_{u}+\sum_{u\in S_{1}(z)}d(u)x_{u}\right)$ $\displaystyle\
+(1-\alpha)^{2}\left(\sum_{w\sim z}\sum_{u\in L_{1}(w)}x_{u}+\sum_{w\sim
z}\sum_{u\in S_{1}(w)}x_{u}\right)$
$\displaystyle\leq\alpha(1-\alpha)\left((k-1)n+(3c+1)\sigma
n\right)+(1-\alpha)^{2}\left((k-1+x_{v})n+(3c+1)\sigma n\right)$
$\displaystyle\leq\left(\alpha(k-1)+(1-\alpha)(k-\alpha)+(3c+1)\sigma\right)(1-\alpha)n.$

On the other hand, from Lemma 3.5 we have
$\lambda_{\alpha}(\lambda_{\alpha}-\alpha d(z))\geq(1-\alpha)(k-\alpha)n+O(1)$
which, since $\alpha(k-1)+(1-\alpha)(k-\alpha)+(3c+1)\sigma<(k-\alpha),$ gives
a contradiction. ∎

Note that since $F^{\prime}\subseteq K_{k+1,m}$, for any $v\not\in L$ we have
$d_{R}(v)<m$.

######  Lemma 3.10.

For any $v\in S$ we have $x_{v}=O(n^{-1})$.

###### Proof.

Let $v=\arg\max_{u\in S}x_{u}$. Then we have

$\displaystyle\lambda_{\alpha}x_{v}$ $\displaystyle\leq\alpha
d(v)x_{v}+(1-\alpha)(k+(m+\sqrt{n})x_{v})$
$\displaystyle\leq\alpha(k+m+\sqrt{n})x_{v}+(1-\alpha)(k+(m+\sqrt{n})x_{v})$
$\displaystyle\leq k+(m+\sqrt{n})x_{v}$

so

$(\lambda_{\alpha}-m-\sqrt{n})x_{v}\leq k\Longrightarrow
x_{v}\leq\frac{k}{\lambda_{\alpha}-m-\sqrt{n}}=O(n^{-1}).$

∎

######  Lemma 3.11.

We have $E=\emptyset$.

###### Proof.

Delete all edges between $E$ and $E\cup R$ and add all missing edges between
$E$ and $L$, to obtain a graph $G^{\prime}$. The deletions decrease
$x^{T}A_{\alpha}x$ by at most

$\alpha|E|(2m+\sqrt{n})\cdot O(n^{-2})+(1-\alpha)|E|(m+\sqrt{n})\cdot
O(n^{-2})=o(1),$

while the additions increase $x^{T}A_{\alpha}x$ by at least
$\alpha|E|(1-\alpha)^{2}.$ If $E\neq\emptyset$ then the net change is
positive. Hence, $G^{\prime}\supseteq F_{0}$ for some $F_{0}\in\mathcal{F}$.
This implies that $e(R)\geq 1$ in case (a) and $e(R)\geq 2$ in case (b).
Either way, it follows that $e(L)<{k\choose 2}$, since $G$ is
$\mathcal{F}$-free. Delete from $G^{\prime}$ all edges in $R$ and add an edge
in $L$, to obtain a subgraph of $H$. The deletions decrease $x^{T}A_{\alpha}x$
by at most

$\alpha|R|\cdot O(n^{1/2})\cdot O(n^{-2})+(1-\alpha)|R|\cdot O(n^{1/2})\cdot
O(n^{-2})=O(n^{-1/2})$

while the addition increases $x^{T}A_{\alpha}x$ by at least $(1-\alpha)^{3}$,
so the net change is again positive. Thus
$\lambda_{\alpha}(G)<\lambda_{\alpha}(G^{\prime})<\lambda_{\alpha}(H)$ which
is a contradiction. ∎

######  Lemma 3.12.

The set $L$ induces a clique.

###### Proof.

Suppose not. Then we transform $G$ into $K_{k}+\overline{K_{n-k}}$ by deleting
all edges in $R$ and adding at least one edge in $L$. The deletions decrease
$x^{T}A_{\alpha}x$ by at most

$\alpha nm\cdot O(n^{-2})+(1-\alpha)\frac{nm}{2}\cdot O(n^{-2})=O(n^{-1}).$

while the additions increase $x^{T}A_{\alpha}x$ by at least $(1-\alpha)^{3}$,
which is a contradiction. ∎

###### Proof of Theorem 1.5.

By Lemma 3.12, we know $G\supseteq K_{k}+\overline{K_{n-k}}.$ In case (a),
$K_{k}+\overline{K_{n-k}}$ is $\mathcal{F}$-saturated, hence
$G=K_{k}+\overline{K_{n-k}}$. In case (b), there is at most one edge in $R$,
which implies $G=K_{k}+(K_{2}\cup\overline{K_{n-k-2}})$. ∎

##  4 Concluding remarks

Our aim in this paper was to study situations where
$\mathrm{SPEX}(n,\mathcal{F})\subseteq\mathrm{EX}(n,\mathcal{F})$ or
$\mathrm{SPEX}_{\alpha}(n,\mathcal{F})\subseteq\mathrm{SPEX}(n,\mathcal{F})$.
In fact, we have given ‘recipes’ which allow one to determine these extremal
graphs in more general situations. Many more applications of these results
could be stated, and in our list of applications we have restricted ourselves
to families for which the edge extremal graphs were studied in previous
papers. There are also applications which follow easily from the methods of
this paper but are not strictly consequences of our main theorems. We list
some such cases below.

  * •

When one has a ‘nice characterization’ of the graphs $X$ such that $K_{k}+X$
is $\mathcal{F}$-free, stronger results can be proved. For example, suppose
$K_{k}+X$ if $\mathcal{F}$-free if and only if $X\not\supseteq P_{3}$; then
one can remove the assumption that $\mathcal{F}$ is finite from Theorem 1.1
(c) and prove an analagous result for the alpha spectrum. This allows one to
prove the following results.

    * –

$\mathrm{SPEX}(n,\\{C_{4},C_{5},\ldots\\})=K_{1}+M_{n-1}.$ This also follows
from the spectral extremal result for $C_{4}$ [47].

    * –

$\mathrm{SPEX}_{\alpha}(n,C_{4})=K_{1}+M_{n-1}$ [56].

    * –

$K_{2k-1}+M_{n-2k+1}$ has the largest (alpha) spectral radius without $k$
disjoint even cycles.

    * –

$K_{3}+M_{n-3}$ has the largest (alpha) spectral radius without 2 disjoint
theta graphs; see [29] for the definition and required extremal result.

Another such ‘nice characterization’ occurs in the spectral result for star
forests; here $K_{k}+X$ is $F$-free if and only if $\Delta(X)<d_{k}$. Thus we
can obtain the corresponding alpha spectral result from [10].

  * •

In some cases our methods work for extremal graphs of the form
$W+\overline{K_{n-|W|}}$, where $W$ is a fixed graph which is neither empty
nor complete. For example, if $\mathcal{F}$ is finite and every graph in
$\mathrm{EX}^{K_{|W|,n-|W|}}(n,\mathcal{F})$ contains
$\mathrm{ex}(|W|,\mathcal{F})$ edges in $W$ and no edges in $V-W$, then under
the other assumptions of Theorem 1.1, we have that any graphs in
$\mathrm{SPEX}(n,\mathcal{F})$ are $W+\overline{K_{n-|W|}}$ where
$W\in\mathrm{EX}(n,|W|)$. As consequence, we obtain the spectral analogues of
Theorems 1.6 and 1.7 of [44].

  * •

As mentioned in the introduction, when
$\mathrm{SPEX}(n,\mathcal{F})=K_{k,n-k}$ then under the assumptions of Theorem
1.5 we can show that $\mathrm{SPEX}_{\alpha}(n,\mathcal{F})=K_{k,n-k}$ for a
certain range of $\alpha$. However, additional arguments would be needed to
characterize $\mathrm{SPEX}_{\alpha}(n,\mathcal{F})$ for every
$\alpha\in[0,1)$.

Additionally, when our methods do not determine the extremal graphs exactly,
one can sometimes still obtain general structural results. For example, let
$\mathcal{F}$ be any finite family of graphs such that
$\mathrm{ex}(n,\mathcal{F})=O(n)$. Let $k=\max\\{\ell:K_{\ell,\infty}\text{ is
}\mathcal{F}\text{-free}\\}<\infty.$ Then the proof of Proposition 2.2 gives
that any $G\in\mathrm{SPEX}(n,\mathcal{F})$ has $G\supseteq K_{k,n-k}$.
Moreover, any vertex in the partite set of $G$ of size $n-k$ has degree at
most $k+m$, where $m$ is the smallest minimum degree of a vertex in the
partite set of size $k+1$ of any $F\in\mathcal{F}$ satisfying $F\subseteq
K_{k+1,\infty}$.

We end by listing some open questions.

  * •

To prove Theorem 1.1 in its generality we require that
$\mathrm{ex}(n,\mathcal{F})=O(n)$. However, many of the techniques in the
proof were originally discovered in the proof of the spectral even-cycle
theorem [13] where the Turán number is much larger. When considering a
specific forbidden family, the structure of the forbidden graph(s) can be used
and in some cases the condition on the Turán number can be relaxed. When
$\alpha=0$, perhaps the assumption that $F-v$ is a forest for some bipartite
$F\in\mathcal{F}$ could be useful. For example, it would be interesting to try
to prove a spectral version of the general result of Faudree and Simonovits
[26]. In any case, it seems possible that our assumption
$\mathrm{ex}(n,\mathcal{F})=O(n)$ could be weakened or modified, and one could
obtain a general result which implies, e.g., the spectral even cycle theorem.

  * •

For the case $\alpha>0$, we do not know whether the assumption that $F-v$ is a
forest could be weakened. For example, if one may assume only that
$F-\\{v_{1},\ldots,v_{k}\\}$ is a forest then perhaps one could determine the
alpha spectral extremal graphs for $k\cdot C_{2\ell}$.

  * •

We would like to obtain a counterexample similar to Proposition 1.2 using a
smaller family $\mathcal{F}$ or ideally a single graph $F$. Alternatively,
perhaps Theorem 1.3 be strengthened when $\mathcal{F}$ consists of a single
forest $F$. It seems reasonable to guess that, for $3/4\leq Q\leq 1$, we have
$\mathrm{SPEX}(n,F)\subseteq\mathrm{EX}^{K_{k}+\overline{K_{n-k}}}(n,F)$ while
for any $Q>1$ this is not necessarily the case. The reason is that, when
$Q\leq 1$ we can use the fact that $X$ is a union of bounded trees or of
cycles; while for certain $Q>1$, certain path-star forests [25] provide
counterexamples.

  * •

The only step in the proof of Theorem 1.1 which prevents us from allowing
$\mathcal{F}$ to be infinite in all cases is Lemma 2.12. We were unable to
modify our arguments to work for all infinite graph families or to find a
counterexample showing this cannot be done. In some cases, the nature of the
graph family $\mathcal{F}$ allows one to prove Lemma 2.12 without resorting to
the argument we use for cases (a)-(c). For example, if
$\mathcal{F}=\\{C_{4},C_{5},\ldots\\}$, then the ‘nice characterization’
argument alluded to above achieves this, but alternatively one can argue
instead of Lemma 2.12 that the existence of a long cycle in the modified graph
$G^{\prime}$ implies the existence of a different long cycle in the original
graph $G$. Ad-hoc arguments of this kind may work for many other natural
infinite families.

  * •

In cases (d) and (e) of Theorem 1.1, it is not too difficult to show that if
$Q<1$, then there is some $R$ such that $e(X)=Rn+O(1)$. Can this be shown for
$Q\geq 1$?

  * •

As mentioned in the introduction, the extremal graphs covered by Theorem 1.5
are more restricted than those covered by Theorem 1.1. Our methods should give
some information about $\mathrm{SPEX}_{\alpha}(n,\mathcal{F})$ when
$\mathcal{F}$ is as in cases (a), (d), (e), or (f) of Theorem 1.1, but we have
not attempted to determine the strongest possible statement one can prove
using our methods.

  * •

When $G=K_{k,n-k}$, we have seen that the extremal function
$\mathrm{ex}^{G}(n,\mathcal{F})$ is relevant to determining the spectral
extrema for many families of forbidden graphs. Perhaps this motivates further
study of this or other ‘restricted extremal problems’; in particular, it would
be interesting to see if there are cases in which determination of
$\mathrm{EX}^{K_{k,n-k}}(n,\mathcal{F})$ is nontrivial while also providing an
application of Theorem 1.1.

## References

  * [1] P.N. Balister, E. Győri, J. Lehel, and R.H. Schelp.  Connected graphs without long paths.  Discrete Mathematics, 308(19):4487–4494, 2008.  Simonovits ’06.
  * [2] Arie Bialostocki, Daniel Finkel, and András Gyárfás.  Disjoint chorded cycles in graphs.  Discrete Mathematics, 308(23):5886–5890, 2008.
  * [3] Bela Bollobás.  Cycles modulo k.  Bulletin of the London Mathematical Society, 9(1):97–98, 1977.
  * [4] Richard A Brualdi and Ernie S Solheid.  On the spectral radius of complementary acyclic matrices of zeros and ones.  SIAM Journal on Algebraic Discrete Methods, 7(2):265–272, 1986\.
  * [5] Neal Bushaw and Nathan Kettle.  Turán Numbers of Multiple Paths and Equibipartite Forests.  Combinatorics, Probability and Computing, 20(6):837–853, 2011\.
  * [6] Yair Caro, Balázs Patkós, and Zsolt Tuza.  Connected Turán number of trees.  arXiv preprint arxiv:2208.06126, 2022.
  * [7] Ming-Zhu Chen, Shuchao Li, Zhao-Ming Li, Yuantian Yu, and Xiao-Dong Zhang.  An $A_{\alpha}$-Spectral Erdős-Sós Theorem.  The Electronic Journal of Combinatorics, 2023.
  * [8] Ming-Zhu Chen, A-Ming Liu, and Xiao-Dong Zhang.  Spectral Extremal Results with Forbidding Linear Forests.  Graphs and Combinatorics, 35:335–351, 2019.
  * [9] Ming-Zhu Chen, A-Ming Liu, and Xiao-Dong Zhang.  On the spectral radius of graphs without a star forest.  Discrete Mathematics, 344(4):112269, 2021.
  * [10] Ming-Zhu Chen, A-Ming Liu, and Xiao-Dong Zhang.  Spectral extremal results on the $\alpha$-index of graphs without minors and star forests.  Pure and Applied Mathematics Quarterly, 18(6):2355 – 2378, 2022\.
  * [11] Ming-Zhu Chen, A-Ming Liu, and Xiao-Dong Zhang.  On the $A_{\alpha}$-spectral radius of graphs without linear forests.  Applied Mathematics and Computation, 450:128005, 2023.
  * [12] Ming-Zhu Chen, A-Ming Liu, and Xiao-Dong Zhang.  The spectral radius of minor free graphs.  arXiv preprint arxiv:2311.06833, 2023.
  * [13] Sebastian Cioabă, Dheer Noal Desai, and Michael Tait.  The spectral even cycle problem.  to appear in Combinatorial Theory, arXiv preprint arXiv:2205.00990.
  * [14] Sebastian Cioabă, Dheer Noal Desai, and Michael Tait.  A spectral Erdős-Sós theorem.  arXiv preprint arxiv:2206.03339, 2022.
  * [15] Sebastian Cioabă, Dheer Noal Desai, and Michael Tait.  The spectral radius of graphs with no odd wheels.  European Journal of Combinatorics, 99:103420, 2022.
  * [16] Péter Csikvári.  Applications of the Kelmans transformation: extremality of the threshold graphs.  The Electronic Journal of Combinatorics, pages P182–P182, 2011\.
  * [17] Dheer Noal Desai.  Spectral Turán problems for intersecting even cycles.  Linear Algebra and its Applications, 2023.
  * [18] P. Erdős and T. Gallai.  On maximal paths and circuits of graphs.  Acta Mathematica Academiae Scientiarum Hungarica, 1959.
  * [19] P. Erdős and L. Pósa.  On the maximal number of disjoint circuits of a graph.  Publ. Math. Debrecen, 1962.
  * [20] P. Erdős and A. Rényi.  Asymmetric graphs.  Acta Mathematica Academiae Scientiarum Hungaricae, 14, 1963.
  * [21] Paul Erdős and Miklós Simonovits.  A limit theorem in graph theory.  In Studia Sci. Math. Hung, 1965.
  * [22] Paul Erdős and Arthur H Stone.  On the structure of linear graphs.  Bulletin of the American Mathematical Society, 52(12):1087–1091, 1946.
  * [23] Longfei Fang, Huiqiu Lin, Jinlong Shu, and Zhiyuan Zhang.  Spectral extremal results on trees.  arXiv preprint arXiv:2401.05786, 2024.
  * [24] Longfei Fang, Mingqing Zhai, and Huiqiu Lin.  Spectral extremal problem on $t$ copies of $\ell$-cycle.  arXiv preprint arxiv:2302.03229, 2023.
  * [25] Tao Fang and Xiying Yuan.  Some results on the Turán number of $k_{1}P_{\ell}\cup k_{2}S_{\ell-1}$.  arXiv preprint arXiv:2211.09432, 2022.
  * [26] Ralph J Faudree and Miklós Simonovits.  On a class of degenerate extremal graph problems.  Combinatorica, 3:83–93, 1983.
  * [27] Lihua Feng, Guihai Yu, and Xiao-Dong Zhang.  Spectral radius of graphs with given matching number.  Linear Algebra and its Applications, 422(1):133–138, 2007.
  * [28] Jun Gao and Xinmin Hou.  The spectral radius of graphs without long cycles.  Linear Algebra and its Applications, 566:17–33, 2019.
  * [29] Yunshu Gao and Naidan Ji.  The extremal function for two disjoint cycles.  Bulletin of the Malaysian Mathematical Sciences Society, 38:1425–1438, 2015.
  * [30] Yunshu Gao and Xue Wang.  The edge condition for independent cycles with chords in bipartite graphs.  Applied Mathematics and Computation, 377:125163, 2020.
  * [31] Ronald Gould, Paul Horn, and Colton Magnant.  Multiply chorded cycles.  SIAM Journal on Discrete Mathematics, 28(1):160–172, 2014.
  * [32] Ronald J Gould.  Results and problems on chorded cycles: A survey.  Graphs and Combinatorics, 38(6):189, 2022.
  * [33] Roland Häggkvist.  Equicardinal disjoint cycles in sparse graphs.  In North-Holland Mathematics Studies, volume 115, pages 269–273. Elsevier, 1985.
  * [34] Daniel J Harvey and David R Wood.  Cycles of given size in a dense graph.  SIAM Journal on Discrete Mathematics, 29(4):2336–2349, 2015.
  * [35] Xiaocong He, Yongtao Li, and Lihua Feng.  Spectral extremal graphs without intersecting triangles as a minor.  arXiv preprint arxiv:2301.06008, 2023.
  * [36] Tao Jiang.  A note on a conjecture about cycles with many incident chords.  Journal of Graph Theory, 46(3):180–182, 2004.
  * [37] Peter Keevash, John Lenz, and Dhruv Mubayi.  Spectral extremal problems for hypergraphs.  SIAM Journal on Discrete Mathematics, 28(4):1838–1854, 2014.
  * [38] G. N. Kopylov.  On maximal paths and cycles in a graph.  Dokl. Akad. Nauk SSSR, 234(1):19–21, 1977.
  * [39] Shuchao Li and Yuantian Yu.  On $A_{\alpha}$ spectral extrema of graphs forbidding even cycles.  Linear Algebra and its Applications, 668:11–27, 2023.
  * [40] Shuchao Li, Yuantian Yu, and Huihui Zhang.  An $A_{\alpha}$-spectral Erdős-Pósa theorem.  Discrete Mathematics, 346(9):113494, 2023.
  * [41] Yongtao Li, Weijun Liu, and Lihua Feng.  A survey on spectral conditions for some extremal graph problems.  arXiv preprint arXiv:2111.03309, 2021.
  * [42] Hong Liu, Bernard Lidicky, and Cory Palmer.  On the Turán number of forests.  The Electronic Journal of Combinatorics, 20(2), 2013.
  * [43] Ruifang Liu and Mingqing Zhai.  A spectral Erdős-Pósa Theorem.  arXiv preprint arxiv:2208.02988, 2022.
  * [44] Yichong Liu and Liying Kang.  Extremal graphs without long paths and a given graph.  arXiv preprint arXiv:2312.00620, 2023.
  * [45] Linyuan Lu, Austin Mohr, and László Székely.  Quest for Negative Dependency Graphs.  In Dmitriy Bilyk, Laura De Carli, Alexander Petukhov, Alexander M. Stokolos, and Brett D. Wick, editors, Recent Advances in Harmonic Analysis and Applications, pages 243–258, New York, NY, 2013. Springer New York.
  * [46] W. Mader.  Homomorphieeigenschaften und mittlere kantendichte von graphen.  Mathematische Annalen, 174:265–268, 1967.
  * [47] Vladimir Nikiforov.  Bounds on graph eigenvalues II.  Linear Algebra and its Applications, 427(2):183–189, 2007.
  * [48] Vladimir Nikiforov.  A spectral condition for odd cycles in graphs.  Linear algebra and its applications, 428(7):1492–1498, 2008.
  * [49] Vladimir Nikiforov.  A spectral Erdős–Stone–Bollobás theorem.  Combinatorics, Probability and Computing, 18(3):455–458, 2009.
  * [50] Vladimir Nikiforov.  The spectral radius of graphs without paths and cycles of specified length.  Linear algebra and its applications, 432(9):2243–2256, 2010.
  * [51] Vladimir Nikiforov.  The spectral radius of graphs without paths and cycles of specified length.  Linear Algebra and its Applications, 432(9):2243–2256, 2010.  Special Issue devoted to Selected Papers presented at the Workshop on Spectral Graph Theory with Applications on Computer Science, Combinatorial Optimization and Chemistry (Rio de Janeiro, 2008).
  * [52] Vladimir Nikiforov.  Analytic methods for uniform hypergraphs.  Linear Algebra and its Applications, 457:455–535, 2014.
  * [53] Vladimir Nikiforov.  Merging the ${A}$-and ${Q}$-spectral theories.  Applicable Analysis and Discrete Mathematics, 11(1):81–107, 2017\.
  * [54] Eva Nosal.  Eigenvalues of graphs.  Master’s thesis, University of Calgary, 1970.
  * [55] Michael Tait.  The Colin de Verdière parameter, excluded minors, and the spectral radius.  Journal of Combinatorial Theory, Series A, 166:42–58, 2019.
  * [56] Gui-Xian Tian, Ya-Xue Chen, and Shu-Yu Cui.  The extremal $\alpha$-index of graphs with no 4-cycle and 5-cycle.  Linear Algebra and its Applications, 619:160–175, 2021.
  * [57] Jacques Verstraëte.  Unavoidable cycle lengths in graphs.  Journal of Graph Theory, 49(2):151–167, 2005.
  * [58] Jing Wang, Liying Kang, and Yisai Xue.  On a conjecture of spectral extremal problems.  Journal of Combinatorial Theory, Series B, 159:20–41, 2023.
  * [59] Herbert S Wilf.  Spectral bounds for the clique and independence numbers of graphs.  Journal of Combinatorial Theory, Series B, 40(1):113–117, 1986\.
  * [60] Xiying Yuan and Zhenan Shao.  On the maximal $\alpha$-spectral radius of graphs with given matching number.  Linear and Multilinear Algebra, 71(10):1681–1690, 2023.
  * [61] Mingqing Zhai and Huiqiu Lin.  Spectral extrema of graphs: forbidden hexagon.  Discrete Mathematics, 343(10):112028, 2020.
  * [62] Mingqing Zhai and Bing Wang.  Proof of a conjecture on the spectral radius of ${C}_{4}$-free graphs.  Linear Algebra and its Applications, 437(7):1641–1647, 2012.
  * [63] Yanni Zhai, Xiying Yuan, and Lihua You.  Spectral extrema of graphs: Forbidden star-path forests.  arXiv preprint arXiv:2302.11839, 2023.
  * [64] Yanting Zhang and Ligong Wang.  The $\alpha$-index of graphs without intersecting triangles/quadrangles as a minor.  arXiv preprint arxiv:2308.07543, 2023.
  * [65] Jiaxin Zheng, Xueyi Huang, and Junjie Wang.  Spectral condition for the existence of a chorded cycle.  arXiv preprint arXiv:2311.13323, 2023.