# Spectral Turán problems for intersecting even cycles

Dheer Noal Desai Department of Mathematics and Statistics, University of
Wyoming<EMAIL_ADDRESS>
###### Abstract

Let $C_{2k_{1},2k_{2},\ldots,2k_{t}}$ denote the graph obtained by
intersecting $t$ distinct even cycles
$C_{2k_{1}},C_{2k_{2}},\ldots,C_{2k_{t}}$ at a unique vertex. In this paper,
we determine the unique graphs with maximum adjacency spectral radius among
all graphs on $n$ vertices that do not contain any
$C_{2k_{1},2k_{2},\ldots,2k_{t}}$ as a subgraph, for $n$ sufficiently large.
When one of the constituent even cycles is a $C_{4}$, our results improve
upper bounds on the Turán numbers for intersecting even cycles that follow
from more general results of Füredi [20] and Alon, Krivelevich and Sudakov
[1]. Our results may be seen as extensions of previous results for spectral
Turán problems on forbidden even cycles $C_{2k},k\geq 2$ (see [8, 34, 44,
45]).

Key words: Spectral radius, Intersecting even cycles, Intersecting even cycles
and paths, Extremal graph.

Mathematics Subject Classification: 05C35.

##  1 Introduction

For any graph $F$, the Turán number $\mathrm{ex}(n,F)$ is the maximum number
of edges in any graph on $n$ vertices that avoids any isomorphic copies of $F$
as subgraphs. The set of $n$-vertex $F$-free graphs with $\mathrm{ex}(n,F)$
many edges is denoted by $\mathrm{EX}(n,F)$ and called the set of extremal
graphs. For the complete graph, $K_{r+1}$, Turán [40] proved that the Turán
graphs $T_{r}(n)$ are the only extremal graphs, where the Turán graph is the
unique complete $r$-partite graph on $n$ vertices with each part having either
$\left\lfloor\frac{n}{r}\right\rfloor$ or $\left\lceil\frac{n}{r}\right\rceil$
vertices.

The celebrated Erdős-Stone-Simonovits theorem [17, 18] extends Turán’s theorem
to other graphs with chromatic number $r+1$ and gives the exact asymptotics
for the Turán numbers of graphs with chromatic number at least three. It
states that if the chromatic number of $F$ is $r+1$, then

$\mathrm{ex}(n,F)=\left(1-\dfrac{1}{r}+o(1)\right)\dfrac{n^{2}}{2}.$

Consequently, when $F$ is a bipartite graph and $r=1$, we only get
$\mathrm{ex}(n,F)=o(n^{2})$ and it remains to determine the exact asymptotics
for several basic bipartite graphs. For example, for bipartite graphs
$K_{s,t}$ with $s\leq t$, the Kővari-Sós-Turán theorem [26] establishes the
upper bound $\mathrm{ex}(n,K_{s,t})=O(n^{2-1/s})$, however matching lower
bounds have only been confirmed for complete bipartite graphs $K_{s,t}$ with
$t\geq s-1!+1$ [2, 21]. Another avenue for difficult Turán problems comes from
even cycles. The order of magnitude for $\mathrm{ex}(n,C_{2k})$ is determined
only for $k=2,3$ and $5$ [23].

Let $C_{k_{1},k_{2},\ldots,k_{t}}$ be the graph obtained by intersecting $t$
cycles of lengths $k_{i}\geq 3$, for $1\leq i\leq t$, at a unique vertex. If
all the the $k_{i}$ are odd, we call such a graph an intersecting odd cycle.
In [15] Erdős, Füredi, Gould and Gunderson determined the exact number
$\mathrm{ex}(n,F)$ and set of extremal graphs $\mathrm{EX}(n,F)$ for
$F=C_{3,3,\ldots,3}$ the Friendship graph and $n$ sufficiently large. More
recently Hou, Qiu, and Liu [24, 25] and Yuan [42] solved the Turán problem for
all other intersecting odd cycles $C_{2k_{1}+1,2k_{2}+1,\ldots,2k_{t}+1}$.

The Turán problem remains wide open for intersecting even cycles
$C_{2k_{1},2k_{2},\ldots,2k_{t}}$. For simplicity, assume that $k_{1}\leq
k_{2}\leq\ldots k_{t-1}\leq k_{t}$.

Füredi [20] and Alon, Krivelevich and Sudakov [1] generalized the Kővari-Sós-
Turán theorem to bipartite graphs $H$ where one of the parts has maximum
degree at most $r$. They determined upper bounds
$\mathrm{ex}(n,H)=O(n^{2-1/r})$. This upper bound follows from Theorem 2.2 of
[1] and we record it below for reference.

######  Theorem 1.1.

[1] Let $H=(A\cup B,F)$ be a bipartite graph with sides $A$ and $B$ of sizes
$|A|=a$ and $|B|=b$, respectively. Suppose that the degrees of all vertices
$b\in B$ in $H$ do not exceed $r$. Let $G=(V,E)$ be a graph on $n$ vertices
with average degree $d=2|E(G)|/n$. If

$\frac{d^{r}}{n^{r-1}}-\binom{n}{r}\left(\frac{a+b-1}{n}\right)^{r}>a-1,$

then $G$ contains a copy of $H$.

When $r=2$, this directly gives that
$\mathrm{ex}(n,H)\leq\dfrac{1}{2}\left(a-1+\frac{(a+b-1)^{2}}{2}-O(1/n)\right)^{1/2}n^{3/2}$.

It follows from Theorem 1.1 that

$\mathrm{ex}(n,C_{2k_{1},2k_{2},\ldots,2k_{t}})\leq\dfrac{1}{2}\left(\kappa+\frac{(2\kappa+t)^{2}}{2}-O(1/n)\right)^{1/2}n^{3/2},$
(1)

where $\kappa=\sum_{i=1}^{t}(k_{i}-1)$.

When $r=2$, Conlon and Lee [11] further showed that
$\mathrm{ex}(n,H)=cn^{3/2}$ only if $H$ contains a $C_{4}$. Thereafter,
Conlon, Janzer and Lee [12] further strengthened Theorem 1.1 as follows.

######  Theorem 1.2.

[12] Let $H$ be a bipartite graph such that in one of the parts all the
degrees are at most $r$ and $H$ does not contain $C_{4}$ as a subgraph. Then
$\mathrm{ex}(n,H)=o(n^{2-1/r}).$

More recently, Sudakov and Tomon [39] strengthened the result as follows.

######  Theorem 1.3.

[39] Let $t\geq 2$ be an integer. Let $H$ be a $K_{t,t}$-free bipartite graph
such that every vertex in one of the parts of $H$ has degree at most $t$. Then
$\mathrm{ex}(n,H)=o(n^{2-1/t}).$

In this paper, we study a spectral version of the Turán problem for
intersecting even cycles. Analogous to the Turán problem, let
$\mathrm{spex}(n,F)$ denote the maximum spectral radius of the adjacency
matrix of any $F$-free graph on $n$ vertices, and $\mathrm{SPEX}(n,F)$ denote
the set of spectral extremal graphs on $n$ vertices with adjacency spectral
radius equal to $\mathrm{spex}(n,F)$ and having no isomorphic copies of $F$ as
subgraphs. Nikiforov [34] pioneered the systematic study of spectral Turán
problems, although several sporadic results appeared earlier. In [30]
Nikiforov proved that the only spectral extremal graphs for $K_{r+1}$ are the
Turán graphs $T_{r}(n)$. When combined with the observation that the average
degree of a graph lower bounds the spectral radius of its adjacency matrix,
Nikiforov’s result implies and strengthens Turán’s theorem for complete
graphs. Additionally, Nikiforov [33], Babai and Guiduli [3] proved spectral
versions of the Kővari-Sós-Turán theorem for complete bipartite graphs
$K_{s,t}$. Moreover, using the average degree bound these match the best known
upper bounds for $\mathrm{ex}(n,K_{s,t})$, obtained by Füredi [22]. Recently,
several papers have been published determining $\mathrm{spex}(n,F)$ for
various families of graphs (see [7, 9, 29, 31, 36, 41, 43, 45, 46]). In fact,
our proof further develops techniques that appear in [7, 8]. Spectral Turán
problems fit into the broader framework of Brualdi-Solheid problems [6] that
investigate the maximum spectral radius among all graphs belonging to a
specified family of graphs. Several results are known in this area (see [4, 5,
14, 19, 35, 37, 38]).

As mentioned earlier, solving Turán problems for even cycles has proven to be
a difficult task. Nikiforov conjectured the spectral extremal graphs for even
cycles in [34]. Recently, the conjectures were proved and
$\mathrm{SPEX}(n,C_{2k})$ were determined for all values of $k$ when $n$ is
sufficiently large. The cases $k=2$ was covered in [34, 45], the case $k=3$
was covered in [44], and all other values of $k$ were covered in [8].

In [10] Cioabă, Feng, Tait and Zhang solved the spectral Turán problem for
friendship graphs $C_{3,3,\ldots,3}$. Further, Li and Peng [27] solved the
spectral extremal graphs for all other intersecting odd cycles
$C_{2k_{1}+1,2k_{2}+1,\ldots,2k_{t}+1}$. In [13], the authors generalized the
results of [10] to intersecting cliques.

Let $M_{k}:=\left\lfloor\frac{k}{2}\right\rfloor\sqcup\gamma K_{1}$, where
$\gamma=k\mod 2$, denote a maximal matching on $k$ vertices. Let
$S_{n,k}:=K_{k}\vee(n-k)K_{1}$, denote the join of a clique on $k$ vertices
and an independent set on $n-k$ vertices, and $S_{n,k}^{+}$ be the graph
obtained by adding an edge to the independent set of $S_{n,k}.$ Finally, let
$F_{n,k}:=K_{k}\vee
M_{n-k}=K_{k}\vee\left(\left\lfloor\dfrac{n-k}{2}\right\rfloor
K_{2}\sqcup\gamma K_{1}\right)$ with $\gamma=n-k\mod 2$, be the graph obtained
from $S_{n,k}$ by adding a maximal matching in the independent set of
$S_{n,k}$. For an integer $k$, let $k^{\prime}:=k-1$. We prove the following
theorems for intersecting even cycles.

######  Theorem 1.4.

Let $\max\\{k_{1},k_{2},\ldots,k_{t}\\}\geq 3$ and
$\kappa:=\sum_{i=1}^{t}k_{i}^{\prime}$. If $G$ is a graph of sufficiently
large order $n$, with $\lambda(G)\geq\lambda(S_{n,\kappa}^{+})$ then $G$
contains $C_{2k_{1},2k_{2},\ldots,2k_{t}}$ unless $G=S_{n,\kappa}^{+}$.

In Theorem 1.4, we are assuming that there is at least one even cycle with
more than $6$ vertices. In case all the even cycles have four vertices, then
we have the following theorem.

######  Theorem 1.5.

If $G$ is a graph of sufficiently large order $n$, with
$\lambda(G)\geq\lambda(F_{n,t})$, then $G$ contains $C_{4,4,\ldots,4}$ unless
$G=F_{n,t}$, where $C_{4,4,\ldots,4}$ denotes the intersecting even cycle
consisting of $t$ cycles of length four that intersect at a unique vertex.

A consequence of Theorems 1.4 and 1.5 is that
$\mathrm{ex}(n,C_{2k_{1},2k_{2},\ldots,2k_{t}})\leq\frac{1}{2}(\kappa+o(1))n^{3/2}$.
This improves the bounds in (1) and is not covered by Theorem 1.2 if $k_{i}=2$
for some $i$, since one of the even cycles is a $4$-cycle.

Interestingly, very recently, Fang, Zhai and Lin [28] found similar spectral
extremal graphs for disjoint even cycles and showed that
$\mathrm{SPEX}(n,tC_{2k})=S_{n,lt-1}^{+}$ for $k\geq 3$, and
$\mathrm{SPEX}(n,tC_{4})=F_{n,2t-1}$. We note that Theorems 1.4 and 1.5 along
with the results from [28] may be viewed as extensions of the spectral Turán
theorem on even cycles proved in [8, 34, 44, 45].

We end this section with some results that either follow from Theorems 1.4 and
1.5, or their proofs are almost identical to those given for Theorems 1.4 and
1.5.

######  Remark 1.

Observe that the intersecting even cycle $C_{2k_{1},2k_{2},\ldots.2k_{t}}$
also contains other bipartite graphs $H$ that are not contained in
$S_{n,\kappa}^{+}$ or $F_{n,t}$ (depending on whether or not $H$ is a subgraph
of an intersecting even cycle where at least one of the even cycles has more
than four vertices). This implies that for $n$ sufficiently large,
$\mathrm{EX}(n,C_{2k_{1},2k_{2},\ldots.2k_{t}})=\mathrm{EX}(n,H)\in\\{S_{n,\kappa}^{+},F_{n,t}\\}$.
Note that the size of the smallest color class of $H$ must also be $\kappa+1$
(or $t+1$), for it to not be a subgraph of $S_{n,\kappa}^{+}$ (or $F_{n,t}$).

As an application of our observations in Remark 1, we determine the spectral
extremal graphs for the following families of graphs. Let
$\mathcal{CP}_{2k_{1},\ldots,2k_{t_{1}};2p_{1},\ldots,2p_{t_{2}}}$ be the
graph obtained by intersecting $t_{1}$ even cycles of lengths $2k_{i}\geq 4$,
for $i\leq t_{1}$, and $t_{2}$ even paths on $2p_{i}$ vertices where
$2p_{i}\geq 4$, for $i\leq t_{2}$ at a unique vertex. Equivalently, we can
obtain $\mathcal{CP}_{2k_{1},\ldots,2k_{t_{1}};2p_{1},\ldots,2p_{t_{2}}}$ from
$C_{2k_{1},\ldots,2k_{t_{1}},2p_{1},\ldots,2p_{t_{2}}}$ by deleting one edge
from each of the constituent $C_{2p_{i}}$, where the deleted edge was adjacent
to the central vertex, for all $1\leq i\leq t_{2}$. Clearly,
$\mathcal{CP}_{2k_{1},\ldots,2k_{t_{1}};2p_{1},\ldots,2p_{t_{2}}}\subset
C_{2k_{1},\ldots,2k_{t_{1}},2p_{1},\ldots,2p_{t_{2}}}$. Then the following two
results for intersecting even cycles and paths directly follow from Theorems
1.4 and 1.5.

######  Theorem 1.6.

Let $\max\\{k_{1},k_{2},\ldots,k_{t_{1}},p_{1},p_{2},\ldots,p_{t_{2}}\\}\geq
3$ where $t_{1}+t_{2}\geq 1$, and
$\kappa:=\left(\sum_{i=1}^{t_{1}}k_{i}\right)+\left(\sum_{i=1}^{t_{2}}p_{i}\right)-(t_{1}+t_{2})$.
If $G$ is a graph of sufficiently large order $n$ and
$\lambda(G)\geq\lambda(S_{n,\kappa}^{+})$ then $G$ contains
$\mathcal{CP}_{2k_{1},\ldots,2k_{t_{1}};2p_{1},\ldots,2p_{t_{2}}}$ unless
$G=S_{n,\kappa}^{+}$.

######  Theorem 1.7.

Let $k_{i}=p_{j}=2$ for $0\leq i\leq t_{1},0\leq j\leq t_{2}$ where
$t_{1}+t_{2}\geq 1$, and $t:=t_{1}+t_{2}$. If $G$ is a graph of sufficiently
large order $n$ and $\lambda(G)\geq\lambda(F_{n,t})$ then $G$ contains
$\mathcal{CP}_{2k_{1},\ldots,2k_{t_{1}};2p_{1},\ldots,2p_{t_{2}}}$ unless
$G=F_{n,t}$.

######  Remark 2.

The intersecting even cycles $C_{2k_{1},\ldots,2k_{t}}$ also contain several
other connected bipartite subgraphs with a smallest color class consisting of
exactly $\kappa+1$ vertices, apart from those mentioned above. Some of these,
however, are subgraphs of $S_{n,\kappa}^{+}$ (or $F_{n,\kappa=t}$). For
example, consider the graphs obtained by deleting at most one edge from every
constituent cycle of $C_{2k_{1},\ldots,2k_{t}}$, where none of the deleted
edges are adjacent to the central vertex. If at least one edge is deleted,
such graphs are not contained in $S_{n,\kappa}$ but are contained in
$S_{n,\kappa}^{+}$ (or $F_{n,\kappa=t}$).

######  Remark 3.

Let $H$ be a connected bipartite subgraph of $C_{4,4,\ldots,4}$, the
intersecting even cycle consisting of $t$ cycles of length four that intersect
at a unique vertex. If

$H\subset F_{n,t}$, then $H\subset S_{n,t}^{+}$. To see this, first note that
if $H\subset F_{n,t}$, it follows from Theorem 1.7 that $H$ must be obtained
from $C_{4,4,\ldots,4}$ by deleting at least one edge not adjacent to its
center. Next, observe that any graph obtained from $C_{4,4,\ldots,4}$ by
deleting an edge not adjacent to its center, must be contained in
$S_{n,t}^{+}$ as well.

It follows from Remarks 2 and 3 that if $H\subset
C_{2k_{1},2k_{2},\ldots,2k_{t}}$, $H\subset S_{n,\kappa}^{+}$ (or
$F_{n,\kappa=t}$) and the size of the smallest color class of $H$ is
$\kappa+1$, then in fact, $H$ is not contained in $S_{n,\kappa}$. We are now
ready to state our final theorem which has an almost identical proof to that
for Theorems 1.4 and 1.5. We therefore, do not include an independent proof
for it, to avoid redundancy, but include additional remarks to describe slight
modifications required for the same Lemmas to hold true.

######  Theorem 1.8.

Let $k_{1},k_{2},\ldots,k_{t}\geq 2$ and
$\kappa:=\left(\sum_{i=1}^{t}k_{i}\right)-t$. Let $H$ be a connected subgraph
of $C_{2k_{1},2k_{2},\ldots,2k_{t}}$ with a smallest color class consisting of
$\kappa+1$ vertices. If either $\max\\{k_{1},k_{2},\ldots,k_{t}\\}\geq 3$ and
$H\subset S_{n,\kappa}^{+}$ or $k_{1}=k_{2}=\ldots=k_{t}$ and $H\subset
F_{n,\kappa}$, then for sufficiently larger order $n$,
$\mathrm{SPEX}(n,H)=S_{n,\kappa}$.

##  2 Organization and Notation

For an integer $k$, let $k^{\prime}:=k-1$. In what follows, whenever we will
be using $t$ positive integers $k_{1},k_{2},\ldots,k_{t}\geq 2$, to define an
intersecting even cycle $C_{2k_{1},2k_{2},\ldots,2k_{t}}$, we will assume
without loss of generality that $k_{1}\leq k_{2}\leq\ldots\leq k_{t}$ and
$k_{1}\geq 2$. Also, let
$\kappa:=\sum_{i=1}^{t}(k_{i}-1)=\sum_{i=1}^{t}k_{i}^{\prime}$. We wish to
show that $\mathrm{SPEX}(n,C_{2k_{1},2k_{2},\ldots 2k_{t}})=S_{n,\kappa}$
whenever we have $k_{t}\geq 3$ and $\mathrm{SPEX}(n,C_{2k_{1},2k_{2},\ldots
2k_{t}})=F_{n,t}=K_{t}\vee\left(\left\lfloor\frac{n-t}{2}\right\rfloor
K_{2}\cup\gamma K_{1}\right)$, where $\gamma=n-t\mod 2$.

For $n$ sufficiently large, let $G$ denote some graph in
$\mathrm{SPEX}(n,C_{2k_{1},2k_{2},\ldots,2k_{t}})$.

Let $\mathrm{x}$ be the scaled Perron vector whose maximum entry is equal to
$1$ and let $z$ be a vertex having Perron entry $\mathrm{x}_{z}=1$. We define
positive constants $\eta,\epsilon$ and $\alpha$ satisfying

$\displaystyle\begin{split}\eta&<\min\left\\{\frac{1}{10\kappa},\frac{1}{(\kappa+t)}\cdot\left[\left(1-\frac{4}{5\kappa}\right)\left(\kappa-\frac{1}{16\kappa^{2}}\right)-(\kappa-1)\right]\right\\}\\\
\epsilon&<\min\left\\{\eta,\frac{\eta}{2},\frac{1}{16\kappa^{3}},\frac{\eta}{32\kappa^{3}+2}\right\\}\\\
\alpha&<\min\left\\{\eta,\frac{\epsilon^{2}}{20\kappa}\right\\}.\end{split}$
(2)

We leave the redundant conditions in these inequalities so that when we
reference this choice of constants it is clear what we are using.

Let $L$ be the set of vertices in $V(G)$ having “large” weights and
$S=V\setminus L$ be the vertices of “small” weights,

$L:=\\{v\in V(G)|\mathrm{x}_{v}\geq\alpha\\},S:=\\{v\in
V(G)|\mathrm{x}_{v}<\alpha\\}.$

Also, let $M\supset L$ be the set of vertices of “not too small” a weight:

$M:=\\{v\in V(G)|\mathrm{x}_{v}\geq\alpha/4\\}.$

Denote by $L^{\prime}\subset L$ the following subset of vertices of “very
large” weights:

$L^{\prime}:=\\{v\in L|\mathrm{x}_{v}\geq\eta\\}.$

For any set of vertices $A\subset V(G)$ and constant $\gamma$, let
$A^{\gamma}=\\{v\in V(G)|\mathrm{\mathbf{x}}_{v}\geq\gamma\\}$.

For any graph $H=(V,E)$, let $N_{i}(u)$ be the vertices at distance $i$ from
some vertex $u\in V$. For any set of vertices $A\subset V$, let
$A_{i}=A_{i}(u)=A\cap N_{i}(u)$. Thus, for the graph $G$, $L_{i}(u),S_{i}(u)$
and $M_{i}(u)$ are the sets of vertices in $L,S$ and $M$ respectively, at
distance $i$ from $u$. If the vertex is unambiguous from context, we will use
$L_{i}$, $S_{i},$ and $M_{i}$ instead. Let $d(u):=|N_{1}(u)|$ and
$d_{A}(u):=|A_{1}(u)|$ denote the degree of $u$ in $H$ and the number of
neighbors of $u$ lying in $A$, respectively. In case the graph $H$ is not
clear from context, we will use $d_{H}(u)$ instead of $d(u)$ to denote the
degree of $u$ in $H$. Also, let $H[A]$ denote the induced subgraph of $H$ by
the set of vertices $A$, and for two disjoint subsets $A,B\subset V$, let
$H[A,B]$ denote the bipartite subgraph of $H$ induced by the sets $A$ and $B$
that has vertex set $A\cup B$ and edge set consisting of all edges with one
vertex in $A$ and the other in $B$. Finally, let $E(A)$, $E(A,B)$ and $E(H)$
denote the set of edges of $H[A]$, $H[A,B]$ and $H$, respectively, and
$e(A),e(A,B)$, and $e(H)$ denote the cardinalities $|E(A)|$, $|E(A,B)|$ and
$|E(H)|$, respectively.

In Section 3 we give some background graph theory lemmas and prove preliminary
lemmas on the spectral radius and Perron vector of spectral extremal graphs.
We reiterate that every lemma applies to both the spectral extremal graphs
when the forbidden graph is an intersecting cycle and when it is some
$H\subset C_{2k_{1},\ldots,2k_{t}}$ as in the statement for Theorem 1.8.
Observations specific to Theorem 1.8 appear only in Remarks 4 and 5. In
Section 4 we progressively refine the structure of our spectral extremal
graphs. Using these results, we prove Theorem 1.4 and 1.5 in Section 5.

##  3 Lemmas from spectral and extremal graph theory

In this section we record several lemmas that will be used subsequently. Some
lemmas involve calculations that require $n$ to be sufficiently large, without
stating this explicitly. We begin this section by recording two known results.

######  Lemma 3.1.

[8] For a non-negative symmetric matrix $B$, a non-negative non-zero vector
$\mathbf{\mathrm{y}}$ and a positive constant $c$, if
$B\mathbf{\mathrm{y}}\geq c\mathbf{\mathrm{y}}$ entrywise, then
$\lambda(B)\geq c$.

######  Lemma 3.2 (Erdős-Gallai [16]).

Any graph on $n$ vertices with no subgraph isomorphic to a path on $\ell$
vertices has at most $\dfrac{(\ell-2)n}{2}$ edges.

It is easy to see that any bipartite graph is contained in a complete
bipartite graph, where the color classes in either graphs have the same sizes.
The following lemma is the version of this known result on intersecting even
cycles, and we record it here to refer to subsequently.

######  Lemma 3.3.

For $1\leq i\leq t$, $k_{i}\geq 3$, and
$\sum_{i=1}^{t}k_{i}^{\prime}\leq\kappa$, the bipartite graph
$K_{\kappa+1,\kappa+t}$ contains all intersecting cycles
$C_{2k_{1},\ldots,2k_{t}}$.

###### Proof.

The intersecting cycle $C_{2k_{1},\ldots,2k_{t}}$ is a bipartite graph, whose
smaller part (which contains the center of the intersecting cycle) has
$\left(\sum_{i=1}^{t}k_{i}^{\prime}\right)+1\leq\kappa+1$ vertices and larger
part has $\kappa+t$ vertices. It is clear from this that
$C_{2k_{1},\ldots,2k_{t}}\subset K_{\kappa+1,\kappa+t}$.

∎

######  Remark 4.

Note that, if $H$ is a subgraph of $C_{2k_{1},\ldots,2k_{t}}$, with $\kappa$
as defined above, then $H$ is also contained in $K_{\kappa+1,\kappa+t}$.

The following lemma will be used to show that any
$C_{2k_{1},\ldots,2k_{t}}$-free graph $G$ cannot contain a large path in
$E(G[N_{1}(v)]\cup G[N_{1}(v),N_{2}(v)])$, for any vertex $v$ of $G$.

######  Lemma 3.4.

Let $1\leq i\leq t$, $k_{i}\geq 2$, with
$\sum_{i=1}^{t}k_{i}^{\prime}\leq\kappa$ and $H=(V,E)$ be a graph whose
vertices are partitioned into two sets $U$ and $W$. If $E=E(H[U])\cup
E(H[U,W])$, and $H$ has a path on $4\kappa+t$ vertices, then $H$ has $t$
disjoint paths of lengths $2k_{i}^{\prime}+1$, $1\leq i\leq t$, and all the
endpoints of the paths are in $U$.

###### Proof.

We will prove the lemma by first proving the following claim.

######  Claim 3.4.1.

If $H$ contains a path with $4k_{i}^{\prime}+1$ vertices then $H$ must contain
a path of length $2k_{i}^{\prime}+1$ with both end points in $U$.

###### Proof.

If $H$ has a path on $4k_{i}^{\prime}+1$ vertices, then there must be a
subpath $v_{1}v_{2}\ldots v_{4k_{i}^{\prime}}$ of length $4k_{i}^{\prime}$
where we may assume without loss of generality that $v_{1}\in U$. We proceed
to show that $v_{1}v_{2}\ldots v_{4k_{i}^{\prime}}$ contains a path
$v_{i_{0}}v_{i_{0}+1}\ldots v_{i_{0}+2k_{i}^{\prime}}$ of length
$2k_{i}^{\prime}+1$ with both endpoints in $U$ via contradiction. To do this
assume to the contrary that there is no such subpath of length
$2k_{i}^{\prime}+1$ with both endpoints in $U$.

Since $v_{1}\in U$, we have that $v_{2k_{i}^{\prime}+1}\in W$. Then both
$v_{2k_{i}^{\prime}},v_{2k_{i}^{\prime}+2}\in U$. Now, if $v_{2}\in U$ then we
have a contradiction that $v_{2}\ldots v_{2k_{i}^{\prime}+2}$ is a path of
length $2k_{i}^{\prime}+1$ with both endpoints in $U$. So assume $v_{2}\in W$
and therefore $v_{3}\in U$. Thus $v_{2k_{i}^{\prime}+3}\in W$ and
$v_{2k_{i}^{\prime}+4}\in U$. Proceeding similarly we get

$v_{4}\in W,v_{5}\in U,v_{2k_{i}^{\prime}+5}\in
W,\ldots,v_{2k_{i}^{\prime}-2}\in W,v_{2k_{i}^{\prime}-1}\in
U,v_{4k_{i}^{\prime}-1}\in W,v_{4k_{i}^{\prime}}\in U,\text{ and finally
}v_{2k_{i}^{\prime}}\in W,$

a contradiction. Thus there must exist a path $v_{i_{0}}v_{i_{0}+1}\ldots
v_{i_{0}+2k_{i}^{\prime}}$ in $v_{1}v_{2}\ldots v_{4k_{i}^{\prime}}$ with both
endpoints in $U$. ∎

Next assume that $H$ contains a path $v_{1}v_{2}\ldots v_{4\kappa+t}$ of
length $4\kappa+t$. Then using our previous claim we have that the path
$v_{1}v_{2}\ldots v_{4k_{1}^{\prime}+1}$ must have a subpath with
$2k_{1}^{\prime}+1$ vertices, both of whose endpoints are in $U$. Similarly,
the path $v_{4k_{1}^{\prime}+2}v_{4k_{1}^{\prime}+3}\ldots
v_{4k_{1}^{\prime}+4k_{2}^{\prime}+2}$, must contain a subpath with
$2k_{2}^{\prime}+1$ vertices, both of whose endpoints are in $U$. In general,
we have that the path
$v_{4(\sum_{j=1}^{i-1}k_{j}^{\prime})+i}v_{4(\sum_{j=1}^{i-1}k_{j}^{\prime})+i+1}\ldots
v_{4(\sum_{j=1}^{i}k_{j}^{\prime})+i}$ must contain a subpath with
$2k_{i}^{\prime}+1$ vertices both of whose endpoints are in $U$, for all
$1\leq i\leq t$.

Thus, the statement of the lemma follows. ∎

We can combine Lemmas 3.2 and 3.4 to get the following Lemma for disjoint
paths in a subgraph.

######  Lemma 3.5.

Suppose that $t\geq 1$, $k_{i}^{\prime}\geq 1$ for all $1\leq i\leq t$, and
$\kappa=\sum_{i=1}^{t}k_{i}^{\prime}$. For a graph $\hat{H}$ on $n$ vertices,
let $U\sqcup W$ be a partition of its vertices. If

$e(U)+e(U,W)>\frac{\left(4\kappa+t-2\right)}{2}n$ (3)

then there exist $t$ disjoint paths of orders $2k_{i}^{\prime}+1$, for $1\leq
i\leq t$, with both ends in $U$.

Further, if

$2e(U)+e(U,W)>\frac{\left(4\kappa+t-2\right)}{2}(|U|+n)$ (4)

then there exist $t$ disjoint paths of orders $2k_{i}^{\prime}+1$, for $1\leq
i\leq t$, with both ends in $U$.

###### Proof.

Let $H$ be the subgraph of $\hat{H}$ on the same vertex set $U\sqcup W$ with
edge set $E(U)\sqcup E(U,W)$. Then by applying Lemma 3.2 on $H$ and the
assumption $e(U)+e(U,W)>\frac{\left(4\kappa+t-2\right)}{2}n$, we have that $H$
must contain a path of order $4\kappa+t$. Applying Lemma 3.4 on the subgraph
$H$ of $\hat{H}$ which is partitioned into two sets $U$ and $W$, we have that
$H$ and therefore $\hat{H}$ contains $t$ disjoint paths of lengths
$2k_{i}^{\prime}+1$ for all $1\leq i\leq t$.

Similarly, if $e(U)>\frac{\left(4\kappa+t-2\right)}{2}|U|$, we have that
$\hat{H}[U]$ and therefore $\hat{H}$ contains $t$ disjoint paths of lengths
$2k_{i}^{\prime}+1$ for all $1\leq i\leq t$. Thus, if $\hat{H}$ does not
contain $t$ disjoint paths of lengths $2k_{i}^{\prime}+1$ for all $1\leq i\leq
t$, we must have that
$2e(U)+e(U,W)=e(U)+e(U)+e(U,W)\leq\frac{\left(4\kappa+t-2\right)}{2}(|U|+n)$.
∎

The following result on the sum of degree squares of a graph generalizes
Theorem 2 of [32] to the case where the forbidden graphs are intersecting even
cycles.

######  Theorem 3.6.

Let $G$ be a graph with $n$ vertices and $m$ edges. If $G$ does not contain a
$C_{2k_{1},2k_{2},\ldots,2k_{t}}$ where $k_{1}\geq 2$, then

$\sum_{u\in V(G)}d_{G}^{2}(u)<(4\kappa+t)(n-1)n.$ (5)

###### Proof.

Let $u$ be any vertex of $G$. Now

$\begin{split}\sum_{v\in
N_{1}(u)}\left(d(v)-1\right)=2e(G[N_{1}(u)])+e(G[N_{1}(u),N_{2}(u)])&\leq\frac{(4\kappa+t-2)}{2}\left(|N_{1}(u)|+(|N_{1}(u)|+|N_{2}(u)|)\right)\\\
&\leq(2\kappa+t/2-1)(d(u)+n-1).\end{split}$ (6)

Thus,

$\begin{split}\sum_{u\in V(G)}d_{G}^{2}(u)=\sum_{u\in V(G)}\sum_{v\in
N_{1}(u)}d(v)&\leq\sum_{u\in V(G)}(2\kappa+t/2-1)(d(u)+n-1)+d(u)\\\
&\leq(4\kappa+t)e(G)+(2\kappa+t/2-1)(n-1)n\\\
&<(4\kappa+t)(n-1)n.,\end{split}$ (7)

where the last inequality uses $e(G)\leq\binom{n}{2}$. ∎

The following result follows from the works of Füredi [20], and Alon,
Krivelevich and Sudakov [1]. The latter is recorded as Theorem 1.1 above.

######  Lemma 3.7.

[1, 20] Let $H$ be a bipartite graph with maximum degree at most two on one
side, then there exists a positive constant $C$ such that

$\mathrm{ex}(n,H)\leq Cn^{3/2}.$

The following is a result of Conlon and Lee which implies that equality occurs
in Lemma 3.7 if and only if $H$ contains a $C_{4}$. We record this as it
appears in Theorem 1.3 of [11].

######  Lemma 3.8.

[11] For any bipartite graph $H$ with maximum degree two on one side
containing no $C_{4}$, there exist positive constants $C$ and $\delta$ such
that

$\mathrm{ex}(n,H)=Cn^{3/2-\delta}.$

In particular, if we apply Lemma 3.8 to intersecting even cycles without any
$C_{4}$, we get the following lemma.

######  Lemma 3.9.

For any intersecting cycle $C_{2k_{1},2k_{2},\ldots,2k_{t}}$ containing no
$C_{4}$, there exist positive constants $C$ and $\delta$ such that

$\mathrm{ex}(n,C_{2k_{1},2k_{2},\ldots,2k_{t}})=C(n^{3/2-\delta}).$ (8)

Next we determine bounds for the spectral radius of a spectral extremal graph
$G$.

######  Lemma 3.10.

$\sqrt{\kappa
n}\leq\dfrac{\kappa-1+\sqrt{(\kappa-1)^{2}+4\kappa(n-\kappa)}}{2}\leq\lambda(G)\leq\sqrt{(4\kappa+t)(n-1)}<\sqrt{5\kappa
n}$.

###### Proof.

The lower bound is obtained from the spectral radius of $S_{n,\kappa}$. The
upper bound is obtained by using the second-degree eigenvalue-eigenvector
equation along with Lemma 3.8:

Let $u\in V(G)$. We use Lemma 3.5 over the graph $G[N_{1}(u)\cup N_{2}(u)]$
with $U=N_{1}(u)$ and $W=N_{2}(u)$. We know that $|N_{1}(u)|=d(u)$. Also,
there cannot be $t$ disjoint paths on $2k_{i}^{\prime}+1$ vertices, for $1\leq
i\leq t$ in $G[N_{1}(u)\cup N_{2}(u)]$ with both end points in $N_{1}(u)$,
else $G[\\{u\\}\cup N_{1}(u)\cup N_{2}(u)]$ contains a
$C_{2k_{1},2k_{2},\ldots,2k_{t}}$ with center $u$. So (4) implies that

$\begin{split}2e(N_{1}(u))+e(N_{1}(u),N_{2}(u))&\leq\frac{\left(4\kappa+t-2\right)}{2}(2|N_{1}(u)|+|N_{2}(u)|)\\\
&\leq(2\kappa+t/2-1)(d(u)+n-1).\end{split}$ (9)

The spectral radius of a non-negative matrix is at most the maximum of the
row-sums of the matrix. Applying this result for $A^{2}(G)$ and its spectral
radius $\lambda^{2}$ and using (9), we obtain that

$\begin{split}\lambda^{2}&\leq\max_{u\in V(G)}\big{\\{}\sum_{w\in V(G)}\
A^{2}_{u,w}\big{\\}}=\max_{u\in V(G)}\big{\\{}\sum_{v\in N(u)}d(v)\big{\\}}\\\
&=\max_{u\in V(G)}\big{\\{}d(u)+2e(N_{1}(u))+e(N_{1}(u),N_{2}(u))\\}\\\
&\leq(2\kappa+t/2)(d(u)+(2\kappa+t/2-1)(n-1)\\\
&<(4\kappa+t)(n-1).\end{split}$ (10)

Thus, $\lambda<\sqrt{(4\kappa+t)(n-1)}<\sqrt{5\kappa n}$, since
$t\leq\sum_{i=1}^{t}k_{i}^{\prime}=\kappa$. ∎

We will now determine upper bounds for the number of vertices in the sets $L$
and $M$ that consist of vertices with relatively large weights.

######  Lemma 3.11.

There exists a positive constant $\delta$ such that
$|L|\leq\dfrac{n^{1-\delta}}{\alpha}$ and
$|M|\leq\dfrac{4n^{1-\delta}}{\alpha}$.

###### Proof.

We will break the proof into two cases depending on whether or not there
exists a positive constant $\delta$ such that $\mathrm{ex}(n,C_{2k_{1},\ldots
2k_{t}})\leq\dfrac{\sqrt{\kappa}}{2}n^{3/2-\delta}$ (that is, depending on
whether or not $C_{2k_{1},\ldots,2k_{t}}$ contains a $C_{4}$). The proof for
the second case also proves the first case without any $C_{4}$. However we
include both proofs to exhibit the need for more delicate techniques when
$\mathrm{ex}(n,F)=\Theta(n^{3/2})$.

######  Case 1.

$\mathrm{ex}(n,C_{2k_{1},\ldots,2k_{t}})\leq\dfrac{\sqrt{\kappa}}{2}n^{3/2-\delta}$

For any $v\in V$, we have that

$\lambda\mathrm{x}_{v}=\sum_{u\sim v}\mathrm{x}_{u}\leq d(v).$ (11)

Combining this with the lower bound in Lemma 3.10 gives $\sqrt{\kappa
n}\mathrm{x}_{v}\leq\lambda\mathrm{x}_{v}\leq d(v)$. Summing over all vertices
$v\in L$ gives

$|L|\sqrt{\kappa n}\alpha\leq\sum_{v\in L}d(v)\leq\sum_{v\in V}d(v)\leq
2e(G)\leq
2\mathrm{ex}(n,C_{2k_{1},2k_{2},\ldots,2k_{t}})\leq\sqrt{\kappa}n^{3/2-\delta}.$
(12)

Thus, $|L|\leq\dfrac{n^{1-\delta}}{\alpha}$. A similar argument shows that
$|M|\leq\dfrac{4n^{1-\delta}}{\alpha}$.

######  Case 2.

$\mathrm{ex}(n,C_{2k_{1},\ldots,2k_{t}})=\Theta(n^{3/2})$

Let $G\in\mathrm{SPEX}(n,C_{2k_{1},2k_{2},\ldots,2k_{t}})$ where $2=k_{1}\leq
k_{2}\leq\ldots\leq k_{t}$. We will show that
$|L|<n^{3/4}<\dfrac{n^{1-\delta}}{\alpha}$. Assume to the contrary that
$|L|\geq n^{3/4}$. Every vertex in $|L|$ has degree at least $\sqrt{\kappa
n}\alpha$. We know by our observations in (1) and Lemma 3.7 that there is some
positive constant $C$ such that
$e(G)\leq\mathrm{ex}(n,C_{2k_{1},2k_{2},\ldots,2k_{t}})\leq Cn^{3/2}$. Thus,
at most $n^{3/4}$ vertices in $L$ have degree $2Cn^{3/4}$ and consequently, at
least $|L|-n^{3/4}$ vertices of $L$ have degree less than $2Cn^{3/4}$. Let
$\mathbb{L}$ denote this subset of vertices of $L$ with degree less than
$2Cn^{3/4}$. If $|L|>n^{3/4}$, we will show a contradiction by proving that
$\mathbb{L}=\emptyset$. To this end, let us assume there is a vertex
$v\in\mathbb{L}$. Then $d(v)<2Cn^{3/4}$. Now let $H$ denote the graph with
vertex set $N_{1}(v)\cup N_{2}(v)$ and $E(H)=E(N_{1}(v),N_{2}(v))$. Then

$\kappa n\alpha\leq\kappa
n\mathrm{\mathbf{x}}_{v}\leq\lambda^{2}\mathrm{\mathbf{x}}_{v}=\sum_{u\sim
v}\sum_{w\sim v}\mathrm{\mathbf{x}}_{w}\leq C_{1}n^{3/4}+\sum_{u\sim
v}\sum_{\begin{subarray}{c}w\sim v\\\ w\in
N_{2}(v)\end{subarray}}\mathrm{\mathbf{x}}_{w}.$

Thus, $e(N_{1}(v),N_{2}(v))\geq\displaystyle\sum_{u\sim
v}\sum_{\begin{subarray}{c}w\sim v\\\ w\in
N_{2}(v)\end{subarray}}\mathrm{\mathbf{x}}_{w}\geq\kappa
n\mathrm{\mathbf{x}}_{v}-C_{1}n^{3/4}\geq(\kappa-\epsilon)n\mathrm{\mathbf{x}}_{v}$,
where we may take $\epsilon>0$ as small as required by taking $n$ sufficiently
large. Note that we used
$e(N_{1})\leq\dfrac{4\kappa+t-2}{2}|N_{1}|\leq(4\kappa+t-2)Cn^{3/4}$).

For any constant $\gamma$, let $\mathbb{L}^{\gamma}$ denote the set of
vertices $\\{v\in\mathbb{L}\textrm{ such that
}\mathrm{\mathbf{x}}_{v}\geq\gamma\\}$. Let $\sigma:=\dfrac{\alpha}{4\kappa}$.

In the following, we will show that $|\mathbb{L}^{\gamma}|=0$ for all
$\gamma\geq\alpha.$ First we will show that if $|\mathbb{L}^{\gamma}|=0$ for
some $\gamma$, then $|\mathbb{L}^{\gamma-\sigma}|=0$. Clearly, since
$|\mathbb{L}^{\gamma}|=0$ for all $\gamma>1$, this will inductively give us
that $\mathbb{L}^{\alpha}=\mathbb{L}=\emptyset$. To do this we will show the
existence of disjoint paths $P_{2k_{i}^{\prime}+1}$ for $1\leq i\leq t$ in
$H$, with both end points in $N_{1}$.

Given $\mathbb{L}^{\gamma}=\emptyset$, recall that for
$v\in\mathbb{L}^{\gamma-\sigma}$,

$\begin{split}\kappa n(\gamma-\sigma)&\leq\kappa
n\mathrm{\mathbf{x}}_{v}\leq\lambda^{2}\mathrm{\mathbf{x}}_{v}=\sum_{u\sim
v}\sum_{w\sim v}\mathrm{\mathbf{x}}_{w}\leq C_{1}n^{3/4}+\sum_{u\sim
v}\sum_{\begin{subarray}{c}w\sim v\\\
w\in\mathbb{L}_{2}^{\gamma}(v)\end{subarray}}\mathrm{\mathbf{x}}_{w}+\sum_{u\sim
v}\sum_{\begin{subarray}{c}w\sim v\\\ w\in
N_{2}(v)\setminus\mathbb{L}_{2}^{\gamma}(v)\end{subarray}}\mathrm{\mathbf{x}}_{w}\\\
&\leq C_{1}n^{3/4}+\sum_{u\sim v}\sum_{\begin{subarray}{c}w\sim v\\\ w\in
N_{2}(v)\setminus\mathbb{L}_{2}^{\gamma}(v)\end{subarray}}\gamma=C_{1}n^{3/4}+e(N_{1}(v),N_{2}(v)\setminus\mathbb{L}_{2}^{\gamma}(v))\gamma.\end{split}$
(13)

Since $\sigma:=\dfrac{\alpha}{4\kappa}$,

$\begin{split}\left(\dfrac{2\kappa-0.5}{2}\right)n=\kappa
n\left(1-\dfrac{1}{4\kappa}\right)\leq\kappa
n\left(1-\dfrac{\sigma}{\gamma}\right)=\kappa
n\left(\dfrac{\gamma-\sigma}{\gamma}\right)\leq
C_{2}n^{3/4}+e(N_{1}(v),N_{2}(v)\setminus\mathbb{L}_{2}^{\gamma}(v))\end{split}$
(14)

for some positive constant $C_{2}=C_{1}/\gamma$. Thus,

$\begin{split}\dfrac{(2\kappa-0.6)}{2}n\leq
e(N_{1}(v),N_{2}(v)\setminus\mathbb{L}_{2}^{\gamma}(v)),\end{split}$ (15)

Thus, there is $P_{2\kappa+1}$ in $H$ and a $P_{2\kappa-1}$ in $H$ with both
end points in $N_{1}$.

Since $\kappa=\sum_{i=1}^{t}k_{i}^{\prime}$, $k_{1}^{\prime}=1$, and $t\geq
2$, it implies that $k_{t}^{\prime}+1\leq\kappa$. Thus, $2k_{t}^{\prime}+1\leq
2\kappa-1$, and there must exist $P_{2k_{i}^{\prime}+1}$ in $H$ with both end
points in $N_{1}$ for all $1\leq i\leq t$. It remains to show that we can find
disjoint paths $P_{2k_{i}^{\prime}+1}$ in $H$ with both end points in $N_{1}$
for all $1\leq i\leq t$.

Say we have shown the existence of $j$ disjoint paths, $P_{2k_{j}^{\prime}+1}$
for $1\leq j<t$, in $H$ with both end points in $N_{1}$. We will next show by
induction that there is a disjoint $P_{2k_{j+1}^{\prime}+1}$ as well, oriented
such that both its end points lie in $N_{1}$. Let $H_{j+1}$ be the induced
subgraph of $H$ with vertex set
$V(H)\setminus(\sqcup_{i=1}^{j}P_{2k_{j}}^{\prime}+1)$. Now, if $W$ is any
finite set of vertices in $V(H)$, recall that

$\begin{split}\kappa
n(\gamma-\sigma)&\leq\lambda^{2}\mathrm{\mathbf{x}}_{v}=\sum_{u\sim
v}\sum_{w\sim v}\mathrm{\mathbf{x}}_{w}\leq C_{1}n^{3/4}+\sum_{u\sim
v}\sum_{\begin{subarray}{c}w\sim v\\\ w\in
N_{2}(v)\setminus\mathbb{L}_{2}^{\gamma}(v)\end{subarray}}\mathrm{\mathbf{x}}_{w}\\\
&\leq C_{1}n^{3/4}+\sum_{\begin{subarray}{c}u\sim v\\\ v\in
W\end{subarray}}\sum_{\begin{subarray}{c}w\sim v\\\ w\in
N_{2}(v)\setminus\mathbb{L}_{2}^{\gamma}(v)\end{subarray}}+\sum_{u\sim
v}\sum_{\begin{subarray}{c}w\sim v\\\ w\in
N_{2}(v)\setminus\mathbb{L}_{2}^{\gamma}(v)\\\ w\in
W\end{subarray}}\mathrm{\mathbf{x}}_{w}+\sum_{\begin{subarray}{c}u\sim v\\\
v\not\in W\end{subarray}}\sum_{\begin{subarray}{c}w\sim v\\\ w\in
N_{2}(v)\setminus\mathbb{L}_{2}^{\gamma}(v)\\\ w\not\in
W\end{subarray}}\mathrm{\mathbf{x}}_{w}\\\ &\leq
C_{2}n^{3/4}+\sum_{\begin{subarray}{c}u\sim v\\\ v\not\in
W\end{subarray}}\sum_{\begin{subarray}{c}w\sim v\\\ w\in
N_{2}(v)\setminus\mathbb{L}_{2}^{\gamma}(v)\\\ w\not\in
W\end{subarray}}\gamma,\end{split}$ (16)

for some positive constant $C_{2}$ and $n$ is taken to be sufficiently large.
In particular, if $W$ is the set of vertices of $V(H)$,
$W=\sqcup_{i=1}^{j}P_{2k_{j}}^{\prime}+1$, we have

$\kappa n(\gamma-\sigma)\leq C_{2}n^{3/4}+\sum_{\begin{subarray}{c}u\sim v\\\
v\not\in W\end{subarray}}\sum_{\begin{subarray}{c}w\sim v\\\ w\in
N_{2}(v)\setminus\mathbb{L}_{2}^{\gamma}(v)\\\ w\not\in
W\end{subarray}}\gamma=C_{2}n^{3/4}+e(H_{j+1})\gamma.$

Thus, $e(H_{j+1})>\dfrac{2\kappa-1}{2}n$ and there must exist a path
$P_{2k_{j+1}^{\prime}+1}$ in $H_{j+1}$ with both end points in $N_{1}$. By
induction, there exist all $t$ disjoint paths of lengths
$P_{2k_{j}^{\prime}+1}$ in $H$ with both end points in $N_{1}$, for all $1\leq
j\leq t$. These disjoint paths create the intersecting even cycle
$C_{2k_{1},2k_{2},\ldots,2k_{t}}$ along with $v$, the central vertex. This is
a contradiction, hence
$\mathbb{L}^{\gamma-\delta}=\mathbb{L}^{\gamma}=\emptyset$. Proceeding
similarly, we can show that
$\mathbb{L}^{\gamma-\delta}=\mathbb{L}^{\gamma-2\delta}=\ldots=\mathbb{L}^{\alpha}(=\mathbb{L})$,
thus $|\mathbb{L}|=0$, a contradiction. Therefore, we must have that
$|L|<n^{3/4}<\dfrac{n^{1-\delta}}{\alpha}$. Similarly, we can prove that
$|M|\leq\dfrac{4n^{1-\delta}}{\alpha}$.

∎

In our final lemma for this section, we determine lower bounds for the Perron
entries in terms of the spectral radius of $G$.

######  Lemma 3.12.

The graph $G$ is connected and for any vertex $v\in V(G)$, we have that

$\mathrm{x}_{v}\geq\dfrac{1}{\lambda(G)}>\dfrac{1}{\sqrt{5\kappa n}}.$

###### Proof.

Say $z$ is a vertex with maximum eigenweight $\mathrm{x}_{z}=1$. Then
$\sqrt{\kappa n}\leq\lambda\leq d(z)$. Now suppose to the contrary that $G$ is
not connected. Say $V_{1}\ni z$ and $V_{2}$ are two connected components of
$G$. Then $\lambda(G[V_{1}])=\lambda$. Next, for any $u\in V_{2}$, let
$\hat{G}$ be the graph obtained from $G$, having an identical vertex set and
$E(\hat{G})=E(G[V_{1}])\cup\\{uz\\}$. Then, $G[V_{1}]$ is a proper subgraph of
$\hat{G}$. Additionally, $\hat{G}[V_{1}\cup\\{u\\}]$ is connected and contains
$G[V_{1}]$ as a proper subgraph. Therefore
$\lambda<\lambda(\hat{G}[V_{1}\cup\\{u\\}])=\lambda(\hat{G})$. Since
$G\in\mathrm{SPEX}(n,C_{2k_{1},\ldots,2k_{t}})$, we must have that
$C_{2k_{1},\ldots,2k_{t}})\subset\hat{G}$.

*Now, $u$ must be a part of the $C_{2k_{1},\ldots,2k_{t}}$ created in $\hat{G}$. However, $d_{\hat{G}}(u)=1$, so $u$ cannot be in any $C_{{2k_{1},\ldots,2k_{t}}}$, and $\hat{G}$ is $C_{{2k_{1},\ldots,2k_{t}}}$-free. But this contradicts the fact that $G\in\mathrm{SPEX}(n,C_{2k_{1},\ldots,2k_{t}})$. Thus, $G$ must be a connected graph. [Note the remark given after the end of the proof, to see a slight modification to the arguments in this paragraph* for purposes of Theorem 1.8].

Now let $v$ be an arbitrary vertex of $G$. If $v$ is adjacent to any vertex
with eigenweight $1$, then clearly $\lambda\mathrm{x}_{v}\geq 1$ and therefore
$\mathrm{x}_{v}\geq\frac{1}{\lambda}$ and we are done. However, if $v$ is not
adjacent to $z$ and assume to the contrary that
$\mathrm{x}_{v}<\frac{1}{\lambda(G)}$, then we modify $G$ to obtain the graph
$G^{\prime}$ as follows. Let $V(G^{\prime})=V(G)$, and
$E(G^{\prime})=(E(G)\setminus\\{uv:uv\in E(G)\\})\cup\\{zv\\}$. Then by the
same arguments as above for $\hat{G}$ we can show that $G^{\prime}$ is
$C_{2k_{1},\ldots,2k_{t}}$-free. Moreover,
$\mathrm{x}^{T}A(G^{\prime})\mathrm{x}-\mathrm{x}^{T}A(G)\mathrm{x}=2(1-\lambda\mathrm{x}_{v})>0$,
so $\lambda(G^{\prime})>\lambda(G)$, a contradiction. Hence,
$\mathrm{x}_{v}\geq\frac{1}{\lambda}$. ∎

######  Remark 5.

Note the following version of the arguments in the proof of Lemma 3.12 that is
relevant for the purposes of Theorem 1.8:

*Now if $\hat{G}$ contains a copy of $H\subset C_{2k_{1},\ldots,2k_{t}}$, then $u$ must be a part of the $H$ created in $\hat{G}$. However, $d_{\hat{G}}(u)=1$ and $d_{G}(z)\geq\lambda>2\kappa+t+1=|V(C_{2k_{1},\ldots,2k_{t}})|$ for $n$ large enough. So, if $\hat{G}$ contains a copy of $H$, then $G$ must also have contained a copy of $H$, a contradiction. Thus, $G$ must be a connected graph.

##  4 Structural results for extremal graphs

In this section, we continue to revise our estimations for the structure of
$G$. We continue our use of auxiliary constants $\alpha,\epsilon,$ and $\eta$.
We assume $n$ to be large enough for all lemmas in this section.

We begin by showing that the degree of any vertex in $L$ is linearly growing
with respect to $n$ and therefore using Theorem 3.6 it follows that $L$ has
constant size.

######  Lemma 4.1.

Any vertex $v\in L$ has degree $d(v)\geq\dfrac{\alpha}{10(4\kappa+t-1)}n$.
Moreover,
$|L|<\dfrac{100(4\kappa+t)^{3}}{\alpha^{2}}<\dfrac{12500\kappa^{3}}{\alpha^{2}}$.

###### Proof.

Assume to the contrary that there exists a vertex $v\in L$ of degree
$d(v)<\dfrac{\alpha}{10(4\kappa+t-1)}n$. Let $\mathrm{x}_{v}=c\geq\alpha$. The
second degree eigenvector-eigenvalue equation with respect to the vertex $v$
gives that

$\begin{split}\kappa
nc\leq\lambda^{2}c=\lambda^{2}\mathrm{x}_{v}=\sum_{\begin{subarray}{c}u\sim
v\\\ w\sim u\end{subarray}}\mathrm{x}_{w}&\leq d(v)c+2e(N_{1}(v))+\sum_{u\sim
v}\sum_{\begin{subarray}{c}w\sim u,\\\ w\in
N_{2}(v)\end{subarray}}\mathrm{x}_{w}\\\ &\leq(4\kappa+t-1)d(v)+\sum_{u\sim
v}\sum_{\begin{subarray}{c}w\sim u,\\\ w\in
M_{2}(v)\end{subarray}}\mathrm{x}_{w}+\sum_{u\sim
v}\sum_{\begin{subarray}{c}w\sim u,\\\ w\in N_{2}\setminus
M_{2}(v)\end{subarray}}\mathrm{x}_{w},\end{split}$ (17)

where the last inequality follows from $e(N_{1}(v))\leq(2\kappa+t/2-1)d(v)$.
Since $d(v)<\dfrac{\alpha}{10(4\kappa+t-1)}n$ by our assumption and
$c\geq\alpha$, we have

$(\kappa-0.1)nc<\sum_{u\sim v}\sum_{\begin{subarray}{c}w\sim u,\\\ w\in
M_{2}(v)\end{subarray}}\mathrm{x}_{w}+\sum_{u\sim
v}\sum_{\begin{subarray}{c}w\sim u,\\\ w\in N_{2}\setminus
M_{2}(v)\end{subarray}}\mathrm{x}_{w}.$ (18)

From $d(v)<\frac{\alpha}{10(4\kappa+t-1)}$ and Lemma 3.11, we get that

$\sum_{u\sim v}\sum_{\begin{subarray}{c}w\sim u,\\\ w\in
M_{2}(v)\end{subarray}}\mathrm{x}_{w}\leq
e(N_{1}(v),M_{2}(v))\leq(2\kappa+t/2-1)(d(v)+|M|)<(2\kappa+t/2-1)\left(\dfrac{\alpha}{10(4\kappa+t-1)}n+\dfrac{4n^{1-\delta}}{\alpha}\right).$

For $n$ sufficiently large, we have that

$(2\kappa+t/2-1)\left(\dfrac{\alpha}{10(4\kappa+t-1)}n+\dfrac{4n^{1-\delta}}{\alpha}\right)\leq.9n\alpha\leq.9nc,$

and consequently using Lemma 3.8,

$(\kappa-1)nc<\sum_{u\sim v}\sum_{\begin{subarray}{c}w\sim u,\\\ w\in
N_{2}\setminus M_{2}(v)\end{subarray}}\mathrm{x}_{w}\leq
e(N_{1}(v),N_{2}\setminus
M_{2}(v))\dfrac{\alpha}{4}\leq(2\kappa+t/2-1)n\dfrac{\alpha}{4}.$

This is a contradiction because $\kappa\geq t\geq 2$ and $c\geq\alpha$. Hence,
$d(v)\geq\dfrac{\alpha}{10(4\kappa+t-1)}n$ for all $v\in L$. Thus, for $n$
sufficiently large we have that
$d^{2}(v)\geq\left(\dfrac{\alpha}{10(4\kappa+t-1)}n\right)^{2}$ for all $v\in
L$.

Combined with Theorem 3.6 this gives us that

$|L|\left(\dfrac{\alpha}{10(4\kappa+t-1)}n\right)^{2}\leq\sum_{v\in
L}d^{2}(v)\leq\sum_{v\in V(G)}d^{2}(v)<(4\kappa+t)(n-1)n.$

Therefore,

$|L|\leq\dfrac{(4\kappa+t)(n-1)n(10(4\kappa+t-1))^{2}}{\alpha^{2}n^{2}}<\dfrac{100(4\kappa+t)^{3}}{\alpha^{2}}\leq\dfrac{12500\kappa^{3}}{\alpha^{2}},$

where we have used $t\leq\kappa$ in the last inequality. ∎

We will now refine our arguments in the proof above to improve degree
estimates for the vertices in $L^{\prime}$.

######  Lemma 4.2.

If $v$ is a vertex in $L^{\prime}$ with $\mathrm{x}_{v}=c$, then $d(v)\geq
cn-\epsilon n$.

###### Proof.

Our proof is again by contradiction. The second degree eigenvalue-eigenvector
equation with respect to the vertex $v$ gives

$\begin{split}knc&\leq\lambda^{2}c=\sum_{u\sim v}\sum_{w\sim
u}\mathrm{x}_{w}=d(v)c+\sum_{u\sim v}\sum_{\begin{subarray}{c}w\sim u,\\\
w\neq v\end{subarray}}\mathrm{x}_{w}\\\ &\leq d(v)c+\sum_{u\in
S_{1}}\sum_{\begin{subarray}{c}w\sim u\\\ w\in L_{1}\cup
L_{2}\end{subarray}}\mathrm{x}_{w}+2e(S_{1})\alpha+2e(L)+e(L_{1},S_{1})\alpha+e(N_{1},S_{2})\alpha.\end{split}$
(19)

The observation that the subgraph of $G$ with edge set $E[N_{1}]\cup
E[N_{1},N_{2}]$ has at most $(2k+t/2-1)n$ edges, which follows form Lemma 3.5,
along with $e(N_{1})\leq(2\kappa+t/2-1)d(v)$ implies that

$\displaystyle 2e(S_{1})$ $\displaystyle\leq(4\kappa+t-2)n,$ $\displaystyle
e(L_{1},S_{1})$ $\displaystyle\leq(2\kappa+t/2-1)n,$ $\displaystyle
e(N_{1},S_{2})$ $\displaystyle\leq(2\kappa+t/2-1)n.$

Combining these inequalities with Lemma 4.1, we deduce that

$\begin{split}&2e(S_{1})\alpha+2e(L)+e(L_{1},S_{1})\alpha+e(N_{1},S_{2})\alpha\\\
\leq&(4\kappa+t-2)n\alpha+2\binom{|L|}{2}+(2\kappa+t/2-1)n\alpha+(2\kappa+t/2-1)n\alpha\\\
\leq&10\kappa n\alpha,\end{split}$ (20)

for $n$ sufficiently large. Hence,

$\kappa nc\leq d(v)c+\sum_{u\in S_{1}}\sum_{\begin{subarray}{c}w\sim u\\\ w\in
L_{1}\cup L_{2}\end{subarray}}\mathrm{x}_{w}+10\kappa n\alpha\leq
d(v)c+e(S_{1},L_{1}\cup L_{2})+10\kappa n\alpha\leq d(v)c+e(S_{1},L_{1}\cup
L_{2})+\frac{\epsilon^{2}n}{2},$ (21)

where the last inequality is by (2). Thus, using $d(v)<cn-\epsilon n$, we get
that

$\left(\kappa-c+\epsilon\right)nc<\left(\kappa n-d(v)\right)c\leq
e(S_{1},L_{1}\cup L_{2})+\frac{\epsilon^{2}n}{2}.$ (22)

Since $v\in L^{\prime}$, by (2) we have $c\geq\eta>\epsilon$. Using
$\epsilon<c\leq 1$, we obtain that

$e(S_{1},L_{1}\cup L_{2})>(\kappa-c)nc+\epsilon
nc-\frac{\epsilon^{2}n}{2}>(\kappa-1)nc+\frac{\epsilon^{2}n}{2}.$ (23)

We show that $G$ contains a $K_{\kappa+1,\kappa+t}$ which gives a
contradiction using Lemma 3.3. We first prove the following claim.

######  Claim 4.2.1.

If $\delta:=\frac{\epsilon\alpha^{2}}{12500\kappa^{3}}$, then there are at
least $\delta n$ vertices inside $S_{1}$ with degree at least $\kappa$ in the
bipartite subgraph $G[S_{1},L_{1}\cup L_{2}]$.

###### Proof.

Assume to the contrary that less than $\delta n$ vertices in $S_{1}$ have
degree at least $\kappa$ in $G[S_{1},L_{1}\cup L_{2}]$. Then
$e(S_{1},L_{1}\cup L_{2})<(\kappa-1)|S_{1}|+|L|\delta
n<(\kappa-1)(c-\epsilon)n+\epsilon n$, because $|S_{1}|\leq d(z)$ and by Lemma
4.1. Combining this with (23) gives
$(\kappa-1)nc-(\kappa-2)n\epsilon>e(S_{1},L_{1}\cup
L_{2})\geq(\kappa-1)nc+\frac{\epsilon^{2}n}{2}$, a contradiction. ∎

Let $D$ be the set of vertices of $S_{1}$ that have degree at least $\kappa$
in $G[S_{1},L_{1}\cup L_{2}]$. Thus $|D|\geq\delta n$. Since there are only
$\binom{|L|}{\kappa}\leq\binom{12500\kappa^{3}/\alpha^{2}}{\kappa}$ options
for any vertex in $D$ to choose a set of $\kappa$ neighbors from, it implies
that there exists some set of $\kappa$ vertices in $L_{1}\cup L_{2}$ with at
least $\delta
n/\binom{|L|}{\kappa}\geq\frac{\epsilon\alpha^{2}n}{12500\kappa^{3}}/\binom{12500\kappa^{3}/\alpha^{2}}{\kappa}$
common neighbors in $D$. For $n$ large enough, this quantity is at least
$\kappa+t$, thus $K_{\kappa+1,\kappa+t}\subset G[S_{1},L_{1}\cup
L_{2}\cup\\{v\\}]$, and we get our desired contradiction. ∎

An important takeaway of Lemma 4.2 is that $d(z)\geq(1-\epsilon)n$ and for any
$v\in L^{\prime}$ we have $d(v)\geq(\eta-\epsilon)n$. By (2), it follows that
the neighborhoods of $z$ and $v$ intersect. So $L^{\prime}\subset\\{z\\}\cup
N_{1}(z)\cup N_{2}(z)$.

Next we bound the number of edges in a bipartite graph contained in the closed
2-ball around $z$ : $N_{2}[z]$.

######  Lemma 4.3.

For $z$ the vertex with $\mathbf{\mathrm{x}}_{z}=1$, we have
$(1-\epsilon)\kappa n\leq e(S_{1},\\{z\\}\cup L_{1}\cup
L_{2})\leq(\kappa+\epsilon)n$.

###### Proof.

To obtain the lower bound, we use (21). Given $\mathrm{x}_{z}=1$, we have

$\kappa n(1)\leq d(z)+e(S_{1},L_{1}\cup L_{2})+\frac{\epsilon^{2}n}{2}.$

Since $e(S_{1},\\{z\\}\cup L_{1}\cup L_{2})=e(S_{1},L_{1}\cup L_{2})+d(z)$,
the lower bound follows as $\frac{\epsilon^{2}n}{2}<\kappa\epsilon n$.

To obtain the upper bound, we assume toward a contradiction that for the
vertex $z$, we have $e(S_{1},\\{z\\}\cup L_{1}\cup L_{2})>(\kappa+\epsilon)n$.
We will obtain a contradiction via Lemma 3.3 by showing that
$K_{\kappa+1,\kappa+t}\subset G$. For this we prove the following claim.

######  Claim 4.3.1.

Let $\delta:=\frac{\epsilon\alpha^{2}}{12500\kappa^{3}}$. With respect to the
vertex $z$ there are at least $\delta n$ vertices inside $S_{1}$ with degree
$\kappa$ or more in $G[S_{1},L_{1}\cup L_{2}]$.

###### Proof.

Assume to the contrary that less than $\delta n$ vertices in $S_{1}$ have
degree at least $\kappa$ in $G[S_{1},L_{1}\cup L_{2}]$. Then
$e(S_{1},L_{1}\cup L_{2})<(\kappa-1)|S_{1}|+|L|\delta n<(\kappa-1)n+\epsilon
n$, because $|S_{1}|\leq n$ and by Lemma 4.1. This contradicts our assumption
that $e(S_{1},\\{z\\}\cup L_{1}\cup L_{2})>(\kappa+\epsilon)n$. ∎

Hence, there is a subset $D\subset S_{1}$ with at least $\delta n$ vertices
such that every vertex in $D$ has degree at least $\kappa$ in
$G[S_{1},L_{1}\cup L_{2}]$. Since there are only at most
$\binom{|L|}{\kappa}\leq\binom{12500\kappa^{3}/\alpha^{2}}{\kappa}$ options
for every vertex in $D$ to choose a set of $\kappa$ neighbors from, we have
that there exists some set of $\kappa$ vertices in $L_{1}\cup
L_{2}\setminus\\{z\\}$ having a common neighborhood with at least $\delta
n/\binom{|L|}{\kappa}\geq\delta
n/\binom{12500\kappa^{3}/\alpha^{2}}{\kappa}=\frac{\epsilon\alpha^{2}}{12500\kappa^{3}}n/\binom{12500\kappa^{3}/\alpha^{2}}{\kappa}\geq\kappa+t$
vertices. Thus, $K_{\kappa,\kappa+t}\subset G[S_{1},L_{1}\cup L_{2}]$ and
$K_{\kappa+1,\kappa+t}\subset G[S_{1},L_{1}\cup L_{2}\cup\\{z\\}]$, a
contradiction by Lemma 3.3. Hence $e(S_{1},\\{z\\}\cup L_{1}\cup
L_{2})\leq(\kappa+\epsilon)n$. ∎

Next we show that all the vertices in $L^{\prime}$ in fact have Perron weight
close to the maximum.

######  Lemma 4.4.

For all vertices $v\in L^{\prime}$, we have
$d(v)\geq\left(1-\frac{1}{8\kappa^{3}}\right)n$ and
$\mathbf{\mathrm{x}}_{v}\geq 1-\frac{1}{16\kappa^{3}}$. Moreover,
$|L^{\prime}|=\kappa$.

###### Proof.

Suppose we are able to show that $\mathbf{\mathrm{x}}_{v}\geq
1-\frac{1}{16\kappa^{3}}$, then using Lemma 4.2 and by (2) we have that
$d(v)\geq\left(1-\frac{1}{8\kappa^{3}}\right)n$. Then because every vertex
$v\in L^{\prime}$ has $d(v)\geq\left(1-\frac{1}{8\kappa^{3}}\right)n$, we must
have that $|L^{\prime}|\leq k$ else $G[S_{1},L^{\prime}]$ contains a
$K_{\kappa+1,\kappa+t}$, a contradiction by Lemma 3.3.

Next, if $|L^{\prime}|\leq\kappa-1$ then using Lemma 4.3 and (21) applied to
the vertex $z$ we have

$\kappa n\leq\lambda^{2}\leq e(S_{1},L^{\prime}\setminus L)+e(S_{1},L_{1}\cup
L_{2})\eta+\frac{\epsilon
n^{2}}{2}\leq(\kappa-1)n+(\kappa+\epsilon)n\eta+\frac{\epsilon^{2}n}{2}<\kappa
n$

where the last inequality holds by (2) and gives the contradiction. Thus
$|L^{\prime}|=\kappa$. Thus, all we need to show is that
$\mathbf{\mathrm{x}}_{v}\geq 1-\frac{1}{16\kappa^{3}}$ for any $v\in
L^{\prime}$.

Now towards a contradiction assume that there is some vertex in $v\in
L^{\prime}$ such that $\mathbf{\mathrm{x}}_{v}<1-\frac{1}{16\kappa^{3}}$. Then
refining (21) with respect to the vertex $z$ we have that

$\begin{split}\kappa n&\leq\lambda^{2}<e(S_{1}(z),\\{z\\}\cup L_{1}(z)\cup
L_{2}(z)\setminus\\{v\\})+|N_{1}(z)\cap
N_{1}(v)|\mathbf{\mathrm{x}}_{v}+\frac{\epsilon^{2}n}{2}\\\
&<(\kappa+\epsilon)n-|S_{1}(z)\cap N_{1}(v)|+|N_{1}(z)\cap
N_{1}(v)|\left(1-\frac{1}{16\kappa^{3}}\right)+\frac{\epsilon^{2}n}{2}\\\
&=\kappa n+\epsilon n+|L_{1}(z)\cap N_{1}(v)|-|N_{1}(z)\cap
N_{1}(v)|\frac{1}{16\kappa^{3}}+\frac{\epsilon^{2}n}{2}.\end{split}$ (24)

Thus, using Lemma 4.1 we have $\frac{|N_{1}(z)\cap
N_{1}(v)|}{16\kappa^{3}}<\epsilon n+\frac{\epsilon^{2}n}{2}+|L|\leq 2\epsilon
n$.

But, $v\in L^{\prime}$, thus $\mathbf{\mathrm{x}}_{v}\geq\eta$ and
$d(v)\geq\left(\eta-\epsilon\right)n$, and so $|N_{1}(z)\cap
N_{1}(v)|\geq\left(\eta-2\epsilon\right)n>32\kappa^{3}\epsilon n$ by (2), a
contradiction. ∎

Now we have $|L^{\prime}|=\kappa$ and every vertex in $L^{\prime}$ has degree
at least $\left(1-\frac{1}{8\kappa^{3}}\right)n$. Thus, the common
neighborhood of vertices in $L^{\prime}$ has at least
$\left(1-\frac{1}{8\kappa^{2}}\right)n$ vertices. Let $R$ denote the set of
vertices in this common neighborhood. Let $\mathcal{E}$ be the set of
remaining “exceptional” vertices not in $L^{\prime}$ or $R$. Thus
$|\mathcal{E}|\leq\frac{n}{8\kappa^{2}}$. We will now show that
$\mathcal{E}=\emptyset$ and thus $G$ contains a large complete bipartite
subgraph $K_{\kappa,n-\kappa}$. For this, we will first prove a bound on the
sum of Perron weights in the neighborhood of any vertex.

######  Lemma 4.5.

For any vertex $v\in V(G)$, the Perron weight in the neighborhood of $v$
satisfies $\displaystyle\sum_{w\sim
v}\mathbf{\mathrm{x}}_{w}\geq\kappa-\frac{1}{16\kappa^{2}}$.

###### Proof.

Clearly if $v\in L^{\prime}$, we have

$\sum_{w\sim
v}\mathbf{\mathrm{x}}_{w}=\lambda\mathbf{\mathrm{x}}_{v}\geq\lambda\left(1-\epsilon\right)\geq
k-\frac{1}{16k^{2}}.$

If $v\in R$, then

$\sum_{w\sim v}\mathbf{\mathrm{x}}_{w}\geq\sum_{\begin{subarray}{c}w\sim v\\\
w\in
L^{\prime}\end{subarray}}\mathbf{\mathrm{x}}_{w}\geq\kappa\left(1-\frac{1}{16\kappa^{3}}\right)=\kappa-\frac{1}{16\kappa^{2}}.$

Finally, let $v\in\mathcal{E}$. If $\sum_{w\sim
v}\mathbf{\mathrm{x}}_{w}<\kappa-\frac{1}{16\kappa^{2}}$, consider the graph
$H$ obtained from $G$ by deleting all edges adjacent to $v$ and adding the
edges $uv$ for all $u\in L^{\prime}$. Now since $\sum_{w\sim
v}\mathbf{\mathrm{x}}_{w}<\kappa-\frac{1}{16\kappa^{2}}$ we have that
$\mathrm{x}^{T}A(H)\mathrm{x}>\mathrm{x}^{T}A(G)\mathrm{x}$, and so by the
Rayleigh principle $\lambda(H)>\lambda(G)$. However, there are no new
intersecting even cycles $C_{2k_{1},2k_{2},\ldots,2k_{t}}$ that have
isomorphic copies in $H$ but no isomorphic copies in $G$. To see this, assume
to the contrary that there is an isomorphic copy of
$C_{2k_{1},2k_{2},\ldots,2k_{t}}$ in $H$ but not in $G$. Then the
$C_{2k_{1},2k_{2},\ldots,2k_{t}}$ has $2\kappa+t+1$ vertices
$v_{1}(=v),v_{2},\ldots,v_{2\kappa+t+1}$ and $v$ has at most $\kappa$
neighbors in $C_{2k_{1},2k_{2},\ldots,2k_{t}}$ all of which lie in
$L^{\prime}$. However, the common neighborhood of $L^{\prime}$, in $G$, has at
least $\left(1-\frac{1}{8\kappa^{2}}\right)n>2\kappa+t+1$ vertices. Therefore,
$G$ must already contain an isomorphic of $C_{2k_{1},2k_{2},\ldots,2k_{t}}$, a
contradiction. ∎

Let $K_{a,b}^{p},$ and $K_{a,b}^{m}$ denote the graphs obtained from the
complete bipartite graph $K_{a,b}$ by adding into the part of size $b$ a path
$P_{3}$ on $3$ vertices, and a matching with two edges $K_{2}\cup K_{2}$,
respectively. So, $K_{a,b}^{p}=K_{a}\vee((b-3)K_{1}\cup P_{3})$ and
$K_{a,b}^{m}=K_{a}\vee((b-4)K_{1}\cup 2K_{2})$. Then we can make the following
observation.

######  Lemma 4.6.

Let $2\leq k_{1}\leq k_{2}\leq\ldots\leq k_{t}$ and
$\kappa:=\sum_{i=1}^{t}k_{i}^{\prime}$. If $k_{t}=2$, then $K_{t,2t_{1}}^{p}$
contains the intersecting even cycle $C_{4,4,\ldots,4}$ consisting of $t$
intersecting $4$-cycles. If $k_{t}\geq 3$, then the graphs
$K_{\kappa,\kappa+t+1}^{p}$ and $K_{\kappa,\kappa+t+1}^{m}$ both contain the
intersecting even cycles $C_{2k_{1},2k_{2},\ldots,2k_{t}}$.

It follows from Lemma 4.6 that if $k_{t}=2$ then every vertex in $G[R]$ has
degree less than 2. Further, if $k_{t}\geq 3$ then $e(R)\leq 1$. Moreover, any
vertex $v\in\mathcal{E}$ is adjacent to at most $\kappa+t+1$ vertices in $R$,
else $K_{\kappa+1,\kappa+t}\subset G[L^{\prime}\cup\\{v\\},R]$, a
contradiction by Lemma 3.3. Finally, any vertex in $\mathcal{E}$ is adjacent
to at most $\kappa-1$ vertices in $L^{\prime}$ by the definition of
$\mathcal{E}$. We are now ready to show that $\mathcal{E}$ is empty and
therefore $S=R$, so $G$ must contain the complete bipartite graph
$K_{\kappa,n-\kappa}$.

######  Lemma 4.7.

The set $\mathcal{E}$ is empty and $G$ contains the complete bipartite graph
$K_{\kappa,n-\kappa}$.

###### Proof.

Assume to the contrary that $\mathcal{E}\neq\emptyset$. Recall that any vertex
$r\in R$ satisfies $\mathbf{\mathrm{x}}_{r}<\eta$. Therefore, any vertex
$v\in\mathcal{E}$ must satisfy

$\sum_{u\sim
v}\mathbf{\mathrm{x}}_{u}=\lambda\mathbf{\mathrm{x}}_{v}=\sum_{\begin{subarray}{c}u\sim
v\\\ u\in L^{\prime}\cup
R\end{subarray}}\mathbf{\mathrm{x}}_{u}+\sum_{\begin{subarray}{c}u\sim v\\\
u\in\mathcal{E}\end{subarray}}\mathbf{\mathrm{x}}_{u}\leq\kappa-1+\left(\kappa+t\right)\eta+\sum_{\begin{subarray}{c}u\sim
v\\\ u\in\mathcal{E}\end{subarray}}\mathbf{\mathrm{x}}_{u}.$

Combining this with Lemma 4.5 gives

$\begin{split}\frac{\displaystyle\sum_{\begin{subarray}{c}u\sim v\\\
u\in\mathcal{E}\end{subarray}}\mathbf{\mathrm{x}}_{u}}{\lambda\mathbf{\mathrm{x}}_{v}}\geq\frac{\lambda\mathbf{\mathrm{x}}_{v}-(\kappa-1)-(\kappa+t)\eta}{\lambda\mathbf{\mathrm{x}}_{v}}\geq
1-\dfrac{(\kappa-1)+(\kappa+t)\eta}{\kappa-\frac{1}{16\kappa^{2}}}\geq\frac{4}{5\kappa},\end{split}$
(25)

where the last inequality follows from (2). Now consider the matrix
$B=A(G[\mathcal{E}])$ and vector $y:=\mathbf{\mathrm{x}}_{|_{\mathcal{E}}}$
(the restriction of the vector $\mathbf{\mathrm{x}}$ to the set
$\mathcal{E}$). We see that for any vertex $v\in\mathcal{E}$

$B\mathbf{\mathrm{y}}_{v}=\sum_{\begin{subarray}{c}u\sim v\\\
u\in\mathcal{E}\end{subarray}}\mathbf{\mathrm{x}}_{u}\geq\frac{4}{5\kappa}\lambda\mathbf{\mathrm{x}}_{v}=\frac{4}{5\kappa}\lambda\mathbf{\mathrm{y}}_{v}.$

Hence, by Lemma 3.1, we have that
$\lambda(B)\geq\frac{4}{5\kappa}\lambda\geq\frac{4}{5}\sqrt{\frac{n}{\kappa}}$.
Moreover,
$\frac{n}{8\kappa^{2}}\geq|\mathcal{E}|>\lambda(B)\geq\frac{4}{5}\sqrt{\frac{n}{\kappa}}$,
so $\mathcal{E}$ must have sufficiently many vertices to apply Lemma 3.10 if
$n$ is sufficiently large and $|\mathcal{E}|\neq 0$. This is a contradiction
to Lemma 3.10 which gives
$\lambda(B)\leq\sqrt{5\kappa|\mathcal{E}|}\leq\sqrt{5\kappa\frac{n}{8\kappa^{2}}}=\sqrt{\frac{5n}{8\kappa}}$,
else $\mathcal{E}$ contains $C_{2k_{1},2k_{2},\ldots,2k_{t}}$. Therefore,
$\mathcal{E}$ must be empty. ∎

##  5 Proof of Theorems 1.4 and 1.5

It follows from Lemma 4.7 that $G$ contains the complete bipartite graph
$K_{\kappa,n-\kappa}$, where the part on $\kappa$ vertices is the set
$L^{\prime}$ and the part on $n-\kappa$ vertices is the set $R$. By Lemma 4.6,
if $k_{t}=2$, then $G[R]\subset M_{n-\kappa}=M_{n-t}$, so $G\subseteq
F_{n,t}$, and if $k_{t}\geq 3$, then $e(R)\leq 1$ in $G$. Hence $G\subset
S_{n,\kappa}^{+}$. Since adding more edges will only increase the spectral
radius, we see that the spectral radius is maximized if the vertices of
$L^{\prime}$ induce a clique $K_{\kappa}$ and the number of edges in $R$ is as
large as possible. Thus $G\cong F_{n,t}$ (and $G\cong S_{n,\kappa}^{+})$, for
$k=2$ (and $k\geq 3$, respectively). ∎

Acknowledgements: The author is grateful to Prof. Sebastian Cioabă and Prof.
Michael Tait for their useful advice during the preparation of this paper.

## References

  * [1] Noga Alon, Michael Krivelevich, and Benny Sudakov.  Turán numbers of bipartite graphs and related Ramsey-type questions.  Combinatorics, Probability and Computing, 12(5-6):477–494, 2003\.
  * [2] Noga Alon, Lajos Rónyai, and Tibor Szabó.  Norm-graphs: variations and applications.  Journal of Combinatorial Theory, Series B, 76(2):280–290, 1999\.
  * [3] László Babai and Barry Guiduli.  Spectral extrema for graphs: the Zarankiewicz problem.  The Electronic Journal of Combinatorics, 16(1):R123, 2009.
  * [4] Abraham Berman and Xiao-Dong Zhang.  On the spectral radius of graphs with cut vertices.  Journal of Combinatorial Theory, Series B, 83(2):233–240, 2001\.
  * [5] Béla Bollobás, Jonathan Lee, and Shoham Letzter.  Eigenvalues of subgraphs of the cube.  European Journal of Combinatorics, 70:125–148, 2018.
  * [6] 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\.
  * [7] Sebastian Cioabă, Dheer Noal Desai, and Michael Tait.  A spectral Erdős-Sós theorem.  arXiv e-prints, pages arXiv–2206, 2022.
  * [8] Sebastian Cioabă, Dheer Noal Desai, and Michael Tait.  The spectral even cycle problem.  arXiv preprint arXiv:2205.00990, 2022.
  * [9] Sebastian Cioabă, Dheer Noal Desai, and Michael Tait.  The spectral radius of graphs with no odd wheels.  European Journal of Combinatorics, 99:103420, 2022.
  * [10] Sebastian Cioabă, Lihua Feng, Michael Tait, and Xiao-Dong Zhang.  The maximum spectral radius of graphs without friendship subgraphs.  The Electronic Journal of Combinatorics, 27(4), 2020.
  * [11] David Conlon and Joonkyung Lee.  On the extremal number of subdivisions.  International Mathematics Research Notices, 2021(12):9122–9145, 2021.
  * [12] David Conlon, Joonkyung Lee, and Oliver Janzer.  More on the extremal number of subdivisions.  Combinatorica, 41(4):465–494, 2021.
  * [13] Dheer Noal Desai, Liying Kang, Yongtao Li, Zhenyu Ni, Michael Tait, and Jing Wang.  Spectral extremal graphs for intersecting cliques.  Linear Algebra and its Applications, 644:234–258, 2022.
  * [14] Mark N Ellingham and Xiaoya Zha.  The spectral radius of graphs on surfaces.  Journal of Combinatorial Theory, Series B, 78(1):45–56, 2000.
  * [15] Paul Erdős, Zoltan Füredi, Ronald J Gould, and David S Gunderson.  Extremal graphs for intersecting triangles.  Journal of Combinatorial Theory, Series B, 64(1):89–100, 1995.
  * [16] Paul Erdős and Tibor Gallai.  On maximal paths and circuits of graphs.  Acta Math. Acad. Sci. Hungar. v10, pages 337–356, 1959.
  * [17] Paul Erdos and Miklós Simonovits.  A limit theorem in graph theory.  Studia Sci. Math. Hungar, 1(51-57):51, 1966.
  * [18] Paul Erdős and Arthur H Stone.  On the structure of linear graphs.  Bulletin of the American Mathematical Society, 52(12):1087–1091, 1946.
  * [19] Miroslav Fiedler and Vladimir Nikiforov.  Spectral radius and hamiltonicity of graphs.  Linear Algebra and its Applications, 432(9):2170–2173, 2010.
  * [20] Zoltán Füredi.  On a Turán type problem of Erdős.  Combinatorica, 11(1):75–79, 1991.
  * [21] Zoltán Füredi.  New asymptotics for bipartite Turán numbers.  Journal of Combinatorial Theory, Series A, 75(1):141–144, 1996\.
  * [22] Zoltán Füredi.  An upper bound on Zarankiewicz’problem.  Combinatorics, Probability and Computing, 5(1):29–33, 1996.
  * [23] Zoltán Füredi and Miklós Simonovits.  The history of degenerate (bipartite) extremal graph problems.  Erdős Centennial, pages 169–264, 2013.
  * [24] Xinmin Hou, Yu Qiu, and Boyuan Liu.  Extremal graph for intersecting odd cycles.  arXiv preprint arXiv:1510.08373, 2015.
  * [25] Xinmin Hou, Yu Qiu, and Boyuan Liu.  Turán number and decomposition number of intersecting odd cycles.  Discrete Mathematics, 341(1):126–137, 2018.
  * [26] P Kővári, Vera T Sós, and Paul Turán.  On a problem of Zarankiewicz.  In Colloquium Mathematicum, volume 3, pages 50–57. Polska Akademia Nauk, 1954.
  * [27] Yongtao Li and Yuejian Peng.  The spectral radius of graphs with no intersecting odd cycles.  Discrete Mathematics, 345(8):112907, 2022.
  * [28] Fang Longfei, Zhai Mingqing, and Lin Huiqiu.  Spectral extremal problem on $t$ copies of $\ell$-cycle.  arXiv preprint arXiv:2302.03229, 2023.
  * [29] Mei Lu, Huiqing Liu, and Feng Tian.  A new upper bound for the spectral radius of graphs with girth at least 5.  Linear Algebra and its Applications, 414(2-3):512–516, 2006.
  * [30] Vladimir Nikiforov.  Bounds on graph eigenvalues II.  Linear Algebra and its Applications, 427(2-3):183–189, 2007.
  * [31] Vladimir Nikiforov.  A spectral condition for odd cycles in graphs.  Linear Algebra and its Applications, 428(7):1492–1498, 2008.
  * [32] Vladimir Nikiforov.  Degree powers in graphs with a forbidden even cycle.  The Electronic Journal of Combinatorics, 16(1):R107, 2009.
  * [33] Vladimir Nikiforov.  A contribution to the Zarankiewicz problem.  Linear Algebra and its Applications, 432(6):1405–1411, 2010.
  * [34] Vladimir Nikiforov.  The spectral radius of graphs without paths and cycles of specified length.  Linear Algebra and its Applications, 432(9):2243–2256, 2010.
  * [35] Eva Nosal.  Eigenvalues of graphs.  Master’s thesis, University of Calgary, 1970.
  * [36] Lingsheng Shi and Zhipeng Song.  Upper bounds on the spectral radius of book-free and/or ${K}_{2,l}$-free graphs.  Linear Algebra and its Applications, 420(2-3):526–529, 2007.
  * [37] Richard P Stanley.  A bound on the spectral radius of graphs with $e$ edges.  Linear Algebra and its Applications, 87:267–269, 1987.
  * [38] Dragan Stevanović, Mustapha Aouchiche, and Pierre Hansen.  On the spectral radius of graphs with a given domination number.  Linear Algebra and its Applications, 428(8-9):1854–1864, 2008.
  * [39] Benny Sudakov and István Tomon.  Turán number of bipartite graphs with no ${K}_{t,t}$.  Proceedings of the American Mathematical Society, 148(7):2811–2818, 2020.
  * [40] Paul Turán.  On an external problem in graph theory.  Mat. Fiz. Lapok, 48:436–452, 1941.
  * [41] Herbert S Wilf.  Spectral bounds for the clique and independence numbers of graphs.  Journal of Combinatorial Theory, Series B, 40(1):113–117, 1986\.
  * [42] Long-Tu Yuan.  Extremal graphs for the $k$-flower.  Journal of Graph Theory, 89(1):26–39, 2018.
  * [43] Wanlian Yuan, Bing Wang, and Mingqing Zhai.  On the spectral radii of graphs without given cycles.  The Electronic Journal of Linear Algebra, 23:599–606, 2012.
  * [44] Mingqing Zhai and Huiqiu Lin.  Spectral extrema of graphs: forbidden hexagon.  Discrete Mathematics, 343(10):112028, 2020.
  * [45] 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.
  * [46] Mingqing Zhai, Bing Wang, and Longfei Fang.  The spectral Turán problem about graphs with no $6$-cycle.  Linear Algebra and its Applications, 590:22–31, 2020.