The Spectral Radius, Maximum Average Degree and Cycles of Consecutive Lengths of Graphs

Abstract

In this paper, we study the relationship between spectral radius and maximum average degree of graphs. By using this relationship and the previous technique of Li and Ning in (J Graph Theory 103:486–492, 2023), we prove that, for any given positive number $\varepsilon <\frac{1}{3}$, if n is a sufficiently large integer, then any graph G of order n with $\rho (G)>\sqrt{\left\lfloor \frac{n^{2}}{4}\right\rfloor }$ contains a cycle of length t for all integers $t\in [3,(\frac{1}{3}-\varepsilon )n]$, where $\rho (G)$ is the spectral radius of G. This improves the result of Li and Ning (2023).

1 Introduction

All graphs considered in this paper are finite, undirected and simple. For a graph G, let ${\overline{G}}$ denote the complement of G. The vertex set and edge set of G are denoted by V(G) and E(G), respectively. For a subset B of V(G), let G[B] be the subgraph of G induced by B, and let $G-B$ be the graph $G[V(G)-B]$. For a vertex u of G, let $G-u=G-\left\{ u\right\}$, and let $d_{G}(u)$ be the degree of u in G. The vertex u is called a cut vertex of G if $G-u$ has more components than G. Let $\delta (G)$ denote the minimum degree of G. The spectral radius of G, denoted by $\rho (G)$, is the largest eigenvalue of its adjacency matrix. By Perron–Frobenius Theorem, $\rho (G)$ has a non-negative eigenvector. A non-negative eigenvector corresponding to $\rho (G)$ is called a Perron vector of G. If G is connected, then any Perron vector of G has positive entries. For any terminology used but not defined here, one may refer to [1, 5].

For a graph G, the maximum average degree of G, denoted by mad(G), is defined as

$$\begin{aligned} \max _{\emptyset \ne S\subseteq V(G)}\frac{2|E(G[S])|}{|S|}. \end{aligned}$$

Clearly, mad$(G)\le \rho (G)$ (see [1]). A subset $B\ne \emptyset$ of V(G) is called critical, if the average degree of G[B] equals mad(G), i.e., $2|E(G[B])|=$ mad$(G)\cdot |B|$. A pseudoforest is a graph of which each component contains at most one cycle. As is well known (see [10]), a graph can be decomposed into k pseudoforests if and only if its maximum average degree is at most 2k. For more study on the relationship between decomposition into pseudoforests of a graph and its maximum average degree, one may refer to [6, 7].

For a certain integer n, let $K_{n}$ and $C_{n}$ be the complete graph and the cycle on n vertices, respectively. For two vertex-disjoint graphs $G_{1}$ and $G_{2}$, let $G_{1}\cup G_{2}$ be the disjoint union of them, and let $G_{1}\vee G_{2}$ be the graph obtained from $G_{1}$ and $G_{2}$ by adding all the edges between $V(G_{1})$ and $V(G_{2})$.

In 2008, Nikiforov [12] studied spectral radius condition for cycles of consecutive lengths in graphs, and proposed the following open problem.

Problem 1 (Nikiforov [12]). What is the maximum positive number $c_{0}$ such that for any given real number $0<\varepsilon <c_{0}$ and sufficiently large n, every graph G of order n with $\rho (G)>\sqrt{\left\lfloor \frac{n^{2}}{4}\right\rfloor }$ contains a cycle of length t for every integer $3\le t\le (c_{0}-\varepsilon )n$.

Considering the graph $K_{s}\vee \overline{K_{n-s}}$ (see [12]), where $s=\left\lfloor \frac{(3-\sqrt{5})n}{4}\right\rfloor$, we see that $c_{0}\le \frac{3-\sqrt{5}}{2}=0.38196\cdots$. Nikiforov [12] proved that $c_{0}\ge \frac{1}{320}$. Ning and Peng [14] slightly refined this result by showing $c_{0}\ge \frac{1}{160}$. Very recently, Zhai and Lin [18] proved that $c_{0}\ge \frac{1}{7}$; Li and Ning [11] improved these results to $c_{0}\ge \frac{1}{4}$. For other related results, one may refer to [19].

As one main result of this paper, we prove that $c_{0}\ge \frac{1}{3}$. The rest of this paper is organized as follows. In Sect. 2, we study the relationship between spectral radius and maximum average degree of graphs. In Sect. 3, we give a proof of $c_{0}\ge \frac{1}{3}$.

2 Spectral Radius and Maximum Average Degree

In this section, we study the relationship between spectral radius and maximum average degree of graphs. To prove the main result of this section, we need several lemmas. The first one is from [1], and the second one is the Theorem 8.1.3 of [5].

Lemma 2.1

([1]) If H is a subgraph of a connected graph G, then $\rho (H)\le \rho (G)$, with equality if and only if $H=G$.

Lemma 2.2

([5]) Let G be a connected graph with a Perron vector ${\textbf{x}}=(x_{w})_{w\in V(G)}$. For an edge $uv_{1}$ and a non-edge $uv_{2}$ of G, let $G^{'}$ be the graph obtained from G by deleting the edge $uv_{1}$, and adding the edge $uv_{2}$. If $x_{v_{1}}\le x_{v_{2}}$, then $\rho (G^{'})>\rho (G)$.

The following lemma can be deduced from Proposition 2.2 and Theorem 2.3 of [9].

Lemma 2.3

([9]) Let G be a connected graph on n vertices and m edges with $\delta (G)\ge k$. Then $\rho (G)\le \frac{k-1}{2}+\sqrt{2\,m-kn+\frac{(k+1)^{2}}{4}}$. Equality holds if and only if G is either a k-regular graph or a bidegreed graph in which each vertex is of degree either k or $n-1$.

We firstly study critical subsets in graphs.

Lemma 2.4

Let G be a graph, and let B and C be two critical subsets of V(G). If $B\cap C\ne \emptyset$, then $B\cap C$ is a critical subset of V(G).

Proof

Set mad$(G)=k$, where k is a rational number. Clearly, a subset $S\ne \emptyset$ of V(G) is critical if and only if $2|E(G[S])|=k|S|$. Note that $|B|+|C|=|B\cup C|+|B\cap C|$. Since each edge e of $G[B\cup C]$ is counted at most once in $|E(G[B])|+|E(G[C])|$ except that e is counted precisely twice for $e\in E(G[B\cap C])$, we have

$$\begin{aligned} |E(G[B])|+|E(G[C])|\le |E(G[B\cup C])|+|E(G[B\cap C])|~~(*). \end{aligned}$$

Since B and C are two critical subsets of V(G), we have $2|E(G[B])|=k|B|$ and $2|E(G[C])|=k|C|$. By $(*)$ we have

$$\begin{aligned} 2|E(G[B\cup C])|+2|E(G[B\cap C])|\ge k|B|+k|C|=k|B\cup C|+k|B\cap C|. \end{aligned}$$

Since $2|E(G[B\cup C])|\le k|B\cup C|$ and $2|E(G[B\cap C])|\le k|B\cap C|$ by definition of k, we have $2|E(G[B\cup C])|= k|B\cup C|$ and $2|E(G[B\cap C])|= k|B\cap C|$. Thus $B\cap C$ is a critical subset of V(G). This completes the proof. $\square$

For two integers $k\ge 1$ and $n\ge 2k+1$, let ${\mathcal {G}}^{k}_{n}$ be the set of graphs on n vertices with maximum average degree at most 2k.

Theorem 2.5

For two integers $k\ge 1$ and $n\ge 2k+1$, let G be an extremal graph with maximum spectral radius in ${\mathcal {G}}^{k}_{n}$. Then $G=K_{k}\vee H$, where H is a graph on $n-k$ vertices with $\genfrac(){0.0pt}1{k+1}{2}$ edges.

Proof

Note that mad$(K_{2k+1})=2k$ and $K_{k}\vee (K_{k+1}\cup \overline{K_{n-1-2k}})\in {\mathcal {G}}^{k}_{n}$. Thus, for any graph $H'$ on $n-k$ vertices with $\genfrac(){0.0pt}1{k+1}{2}$ edges, the graph $K_{k}\vee H'$ is in ${\mathcal {G}}^{k}_{n}$. Now let G be an extremal graph with maximum spectral radius in ${\mathcal {G}}^{k}_{n}$. Then $\rho (G)\ge \rho (K_{k}\vee (K_{k+1}\cup \overline{K_{n-1-2k}}))\ge 2k$ as $K_{k}\vee (K_{k+1}\cup \overline{K_{n-1-2k}})\in {\mathcal {G}}^{k}_{n}$.

Case 1. G is connected. Let ${\textbf{x}}=(x_{w})_{w\in V(G)}$ be a Perron vector of G. Without loss of generality, assume that $x_{u_{1}}\ge x_{u_{2}}\ge \cdots \ge x_{u_{n}}$, where $u_{i}$ for $1\le i\le n$ are the vertices of G.

Now we shall prove that $d_{G}(u_{i})=n-1$ for any $1\le i\le k$. If this is not true, then there is an integer $1\le i_{0}\le k$ such that $d_{G}(u_{i_{0}})<n-1$. Let w be a vertex of G not adjacent to $u_{i_{0}}$. Let $G_{1}$ be the graph obtained from G by adding the edge $wu_{i_{0}}$. By Lemma 2.1 we have $\rho (G_{1})>\rho (G)$. Thus mad$(G_{1})>2k$ by the choice of G. Let B be a critical subset of $V(G_{1})$. Clearly, $w,u_{i_{0}}\in B$. Then $2|E(G_{1}[B])|=$mad$(G_{1})\cdot |B|>2k|B|$, implying that $2|E(G_{1}[B])|\ge 2k|B|+2$ by parity. Thus $2|E(G[B])|=2|E(G_{1}[B])|-2\ge 2k|B|$. Hence $2|E(G[B])|=2k|B|$ as mad$(G)\le 2k$. So, B is also a critical subset of V(G) and mad$(G)=2k$.

Let $B_{j}$ for $1\le j\le \ell$ be all the critical subsets of V(G) containing vertices w and $u_{i_{0}}$, where $\ell \ge 1$. Let $S=\cap _{1\le j\le \ell }B_{j}$. Note that $w,u_{i_{0}}\in S$. By Lemma 2.4 we have that S is a critical subset of V(G). Let $S_{0}=S-\left\{ w\right\}$. Since $|E(G[S])|=|E(G[S_{0}])|+d_{G[S]}(w)$, $2|E(G[S])|=2k|S|$ and $2|E(G[S_{0}])|\le 2k|S_{0}|$, we have

$$\begin{aligned} 2d_{G[S]}(w)=2|E(G[S])|-2|E(G[S_{0}])|\ge 2k|S|-2k|S_{0}|=2k, \end{aligned}$$

implying that $d_{G[S]}(w)\ge k$. Since w is not adjacent to $u_{i_{0}}$, there is a vertex in $S-\left\{ u_{1},u_{2},...,u_{k}\right\}$, say $u_{t}$ with $t\ge k+1$, such that w is adjacent to $u_{t}$. Let $G_{2}$ be the graph obtained from G by adding the edge $wu_{i_{0}}$ and deleting the edge $wu_{t}$. By Lemma 2.1 we have $\rho (G_{2})>\rho (G)$ as $x_{u_{i_{0}}}\ge x_{u_{t}}$. Since G is an extremal graph with maximum spectral radius in ${\mathcal {G}}^{k}_{n}$, we have mad$(G_{2})>2k$. Let C be a critical subset of $V(G_{2})$. Then $2|E(G_{2}[C])|>2k|C|$, implying that $w,u_{i_{0}}\in C$ and $u_{t}\notin C$. Using a similar discussion as on B, we can show that C is also a critical subset of V(G) containing vertices $u_{i_{0}}$ and w. By the definition of S, we have $S\subseteq C$. However, this is a contradiction, since $u_{t}\in S$ and $u_{t}\notin C$. Thus we obtain that $d_{G}(u_{i})=n-1$ for any $1\le i\le k$.

Consequently, $G=K_{k}\vee H$, where H is a graph on $n-k$ vertices. From $2|E(G)|\le 2k|G|=2kn$ we obtain $|E(H)|\le \genfrac(){0.0pt}1{k+1}{2}$. Since G is an extremal graph with maximum spectral radius in ${\mathcal {G}}^{k}_{n}$, we have $|E(H)|=\genfrac(){0.0pt}1{k+1}{2}$ by Lemma 2.1.

Case 2. G is not connected. Let Q be a component of G with $\rho (Q)=\rho (G)$. Let $|Q|=n_{1}<n$. If $n_{1}\le 2k$, then $\rho (G)=\rho (Q)\le n_{1}-1\le 2k-1$, a contradiction. Thus $n_{1}\ge 2k+1$. So, Q is a connected extremal graph with maximum spectral raidus in ${\mathcal {G}}^{k}_{n_{1}}$. Similar to Case 1, we can show that $Q=K_{k}\vee H_{0}$, where $H_{0}$ is a graph on $n_{1}-k$ vertices with $\genfrac(){0.0pt}1{k+1}{2}$ edges. Let $H_{1}=H_{0}\cup \overline{K_{n-n_{1}}}$. Then $K_{k}\vee H_{1}\in {\mathcal {G}}^{k}_{n}$. Since Q is a proper subgraph of $K_{k}\vee H_{1}$, we have $\rho (G)=\rho (Q)<\rho (K_{k}\vee H_{1})$ by Lemma 2.1. This contradicts the choice of G.

By the above discussion, we have that $G=K_{k}\vee H$, where H is a graph on $n-k$ vertices with $\genfrac(){0.0pt}1{k+1}{2}$ edges. This completes the proof. $\square$

As in [15], a matrix $A=(a_{ij})_{n\times n}$ is called a stepwise matrix, if it is deduced that $a_{hk}=1$ from $a_{ij}=1$ with $i<j$, whenever $h<k\le j$ and $h\le i$. Following [2], we can (easily) show that the adjacency matrix of the graph H in Theorem 2.5 is a stepwise matrix. However, it seems hard to characterize the structure of H completely for general values of n and k. For a similar problem on determining the extremal graphs with maximum spectral radius among all connected graphs of order n and size m, it is only known for special values of n and m (see [2,3,4]). In particular, when k is given and n is sufficiently large, by a very similar proof as Lemma 2.8 of [20], we can obatin that the extremal graph $G=K_{k}\vee H$ in Theorem 2.5 has a local degree sequence majorization (see Lemma 2.8 of [20] for the definition). Hence the graph H in Theorem 2.5 must be the disjoint union of the star graph of order $\genfrac(){0.0pt}1{k+1}{2}+1$ and $n-k-1-\genfrac(){0.0pt}1{k+1}{2}$ isolated vertices when n is large enough.

Corollary 2.6

For two integers $k\ge 1$ and $n\ge 2k+1$, let G be a graph in ${\mathcal {G}}^{k}_{n}$. Then $\rho (G)<\frac{k-1}{2}+\sqrt{kn+\frac{(k+1)^{2}}{4}}$.

Proof

By Theorem 2.5 we have $\rho (G)\le \rho (K_{k}\vee H)$, where H is a graph on $n-k$ vertices with $\genfrac(){0.0pt}1{k+1}{2}$ edges. Clearly, $K_{k}\vee H$ is a connected graph with kn edges and $\delta (K_{k}\vee H)\ge k$. By Lemma 2.3, we have that $\rho (K_{k}\vee H)\le \frac{k-1}{2}+\sqrt{kn+\frac{(k+1)^{2}}{4}}$. Note that equality can not hold, since $K_{k}\vee H$ is neither a k-regular graph nor a bidegreed graph in which each vertex is of degree either k or $n-1$. Thus $\rho (G)\le \rho (K_{k}\vee H)<\frac{k-1}{2}+\sqrt{kn+\frac{(k+1)^{2}}{4}}$. This completes the proof. $\square$

3 Spectral Radius and Cycles of Consecutive Lengths

As pointed out in [11], to attack Nikiforov’s problem, one main technique is to use both Gould–Haxell–Scott Theorem [8] and Voss and Zuluaga’s theorem [17], together with Sun–Das inequality [16], to find a subgraph with large connectivity and average degree, which also contains cycles of consecutive lengths. We will use Corollary 2.6 and the method used in Li and Ning [11] to find a required one.

For a graph G, let ec(G) and oc(G) denote the length of a longest even cycle and the length of a longest odd cycle of G, respectively. To prove the main result of this section, we need some preliminaries. The whole machine from [11] due to Li and Ning includes the following four results. The first one is from [17], and the second one is from [8].

Theorem 3.1

([17]) Let G be a 2-connected graph with $\delta (G)\ge k\ge 3$ having at least $2k+1$ vertices. Then $ec(G)\ge 2k$, and $oc(G)\ge 2k-1$ if G is non-bipartite.

Theorem 3.2

([8]) For any real number $c>0$, there exits a constant $K:=K(c)=\frac{7.5\times 10^{5}}{c^{5}}$ such that the following holds. Let G be a graph on $n\ge \frac{45K}{c^{4}}$ vertices with $\delta (G)\ge cn$. Then G contains a cycle of length t for every even $t\in [4,ec(G)-K]$ and every odd $t\in [K,oc(G)-K]$.

The following two lemmas are from [11].

Lemma 3.3

([11]) Let G be a graph on n vertices. If $ec(G)\le 2k$ where $k\ge 1$ is an integer, then $|E(G)|\le \frac{(2k+1)(n-1)}{2}$.

Lemma 3.4

([11]) Let G be a graph. For any $v\in V(G)$, we have $\rho ^{2}(G)\le \rho ^{2}(G-v)+2d_{G}(v)$.

The following fact (from Theorem 1 of [13]) will be used in the proof of Theorem 3.5.

Fact 1. For a graph G on n vertices, if $\rho (G)>\sqrt{\left\lfloor \frac{n^{2}}{4}\right\rfloor }$, then G contains a triangle.

Theorem 3.5

For any real number $0<\varepsilon <\frac{1}{3}$, there is a positive integer $N:=N(\varepsilon )$ satisfying: if G is a graph on $n\ge N$ vertices satisfying $\rho (G)>\sqrt{\left\lfloor \frac{n^{2}}{4}\right\rfloor }$, then G contains the cycle $C_{r}$ for all integers $r\in [3,(\frac{1}{3}-\varepsilon )n]$.

Proof

Let $c=\frac{1}{7}$ and $K=K(\frac{1}{7})$ be given as in Theorem 3.2. Let $0<\varepsilon <\frac{1}{3}$ be fixed and let $N(\varepsilon )$ be sufficiently large such that all the inequalities appeared in the following hold when $n\ge N(\varepsilon )$. (A specified value of $N(\varepsilon )$ can be given in our proof, though we will not do this.) Thus we can assume that n is sufficiently large in the following discussion.

Let k be the least integer such that $k\ge \frac{1}{2}\cdot$mad(G). Then mad$(G)\le 2k$. We will prove $k>\frac{n}{6}$. Suppose $k\le \frac{n}{6}$. Note that G is in ${\mathcal {G}}^{k}_{n}$ defined in Sect. 3. By Corollary 2.6, we have that

$$\begin{aligned} \rho (G)<\frac{k-1}{2}+\sqrt{kn+\frac{(k+1)^{2}}{4}}. \end{aligned}$$

Since $\rho (G)\ge \sqrt{\left\lfloor \frac{n^{2}}{4}\right\rfloor }\ge \sqrt{\frac{n^{2}-1}{4}}$, we obtain that

$$\begin{aligned} \frac{k-1}{2}+\sqrt{kn+\frac{(k+1)^{2}}{4}}>\sqrt{\frac{n^{2}-1}{4}}, \end{aligned}$$

implying that

$$\begin{aligned} k>\frac{\frac{n^{2}-1}{4}+\sqrt{\frac{n^{2}-1}{4}}}{n+1+\sqrt{\frac{n^{2}-1}{4}}}. \end{aligned}$$

For large n, it is easy to check that

$$\begin{aligned} \frac{\frac{n^{2}-1}{4}+\sqrt{\frac{n^{2}-1}{4}}}{n+1+\sqrt{\frac{n^{2}-1}{4}}}>\frac{n}{6}. \end{aligned}$$

Hence $k>\frac{n}{6}$, implying that $\frac{1}{2}$mad$(G)>\left\lfloor \frac{n}{6}\right\rfloor$, i.e., mad$(G)>2\left\lfloor \frac{n}{6}\right\rfloor$.

Let B be a critical subset of V(G). Then $2|E(G[B])|\ge 2\left\lfloor \frac{n}{6}\right\rfloor \cdot |B|$. Let $G_{0}$ be an induced subgraph of G with maximum $|V(G_{0})|$ such that $2|E(G_{0})|\ge 2\left\lfloor \frac{n}{6}\right\rfloor \cdot |V(G_{0})|$. (Such $G_{0}$ exists as G[B] exists.)

If $G_{0}\ne G$, let $V(G)-V(G_{0})=\left\{ u_{1},u_{2},...,u_{\ell }\right\}$, where $\ell =|V(G)|-|V(G_{0})|\ge 1$. For any $1\le i\le \ell$, let $G_{i}$ be the subgraph of G induced by $V(G_{0})\cup \left\{ u_{1},u_{2},...,u_{i}\right\}$. If

$$\begin{aligned} \sum _{1\le i\le \ell }d_{G_{i}}(u_{i})>\left\lfloor \frac{n}{6}\right\rfloor \cdot \ell , \end{aligned}$$

then

$$\begin{aligned} 2|E(G)|=2|E(G_{0})|+2\sum _{1\le i\le \ell }d_{G_{i}}(u_{i})>2\left\lfloor \frac{n}{6}\right\rfloor \cdot |V(G_{0})|+2\left\lfloor \frac{n}{6}\right\rfloor \cdot \ell =2\left\lfloor \frac{n}{6}\right\rfloor \cdot |V(G)|, \end{aligned}$$

implying that $G_{0}=G$ by the choice of $G_{0}$, a contradiction. Thus

$$\begin{aligned} \sum _{1\le i\le \ell }d_{G_{i}}(u_{i})\le \left\lfloor \frac{n}{6}\right\rfloor \cdot \ell . \end{aligned}$$

If $G_{0}=G$, the above equality holds trivially, if we assume that $\ell =0$ and $\sum _{1\le i\le \ell }d_{G_{i}}(u_{i})=0$ (this assumption does not affect the following discussion).

Let $H_{0}=G_{0}$. If there is some vertex $v_{1}\in V(H_{0})$ with $d_{H_{0}}(v_{1})<\left\lfloor \frac{n}{6}\right\rfloor$, let $H_{1}=H_{0}-v_{1}$. Repeating this process as far as possible, we obtain some vertices $v_{1},v_{2},...,v_{t}$ in $V(H_{0})$ with $t\ge 1$, such that $d_{H_{i-1}}(v_{i})<\left\lfloor \frac{n}{6}\right\rfloor$ for any $1\le i\le t$, where $H_{i}$ is the subgraph of $H_{0}$ induced by $V(H_{0})-\left\{ v_{1},v_{2},...,v_{i}\right\}$. Let $H=H_{t}$ (and let $H=H_{0}$ if $\delta (H_{0})\ge \left\lfloor \frac{n}{6}\right\rfloor$, i.e. $t=0$). Since

$$\begin{aligned} 2|E(H_{0})|=2|E(G_{0})|\ge 2\left\lfloor \frac{n}{6}\right\rfloor \cdot |V(G_{0})|=2\left\lfloor \frac{n}{6}\right\rfloor \cdot |V(H_{0})| \end{aligned}$$

and

$$\begin{aligned} 2|E(H_{0})|=2|E(H)|+2\sum _{1\le i\le t}d_{H_{i-1}}(v_{i})<2|E(H)|+2t\left\lfloor \frac{n}{6}\right\rfloor , \end{aligned}$$

we have

$$\begin{aligned} 2|E(H)|>2\left\lfloor \frac{n}{6}\right\rfloor \cdot (|V(H_{0})|-t)=2\left\lfloor \frac{n}{6}\right\rfloor \cdot |V(H)|. \end{aligned}$$

This implies that E(H) is not empty and thus $t<|V(H_{0})|$. Note that $\delta (H)\ge \left\lfloor \frac{n}{6}\right\rfloor$, since the process stops at step t. Recall that $|E(H)|\ge \left\lfloor \frac{n}{6}\right\rfloor \cdot |V(H)|$.

(i) Even cycle.

Since

$$\begin{aligned} |E(H)|\ge \left\lfloor \frac{n}{6}\right\rfloor \cdot |V(H)|>\frac{2\left\lfloor \frac{n}{6}\right\rfloor \cdot (|V(H)|-1)}{2}, \end{aligned}$$

we have $ec(H)\ge 2\left\lfloor \frac{n}{6}\right\rfloor \ge \frac{n}{3}-2$ by Lemma 3.3. Recall that $\delta (H)\ge \left\lfloor \frac{n}{6}\right\rfloor \ge \frac{|V(H)|}{7}$. By Theorem 3.2, H contains a cycle $C_{r}$ with each integer $r\in [4,ec(H)-K]$ for large n. Thus G contains a cycle $C_{r}$ with each integer $r\in [4,(\frac{1}{3}-\varepsilon )n]$ for large n.

(ii) Odd cycle.

Let $h=|V(H)|$. Then $n=h+\ell +t$. Note that $h\ge \frac{n}{3}-1$ as $2|E(H)|\ge 2\left\lfloor \frac{n}{6}\right\rfloor \cdot |V(H)|$. By Lemma 3.4 we have that

$$\begin{aligned} \rho ^{2}(G)-\rho ^{2}(H)\le 2\sum _{1\le i\le \ell }d_{G_{i}}(u_{i})+2\sum _{1\le i\le t}d_{H_{i-1}}(v_{i})\le 2\left\lfloor \frac{n}{6}\right\rfloor \cdot (\ell +t)\le \frac{n}{3}(n-h), \end{aligned}$$

implying that

$$\begin{aligned} \rho ^{2}(H)\ge \frac{n^{2}-1}{4}-\frac{n}{3}(n-h)=\frac{hn}{3}-\frac{n^{2}}{12}-\frac{1}{4}. \end{aligned}$$

We shall prove that H is non-bipartite. Note that

$$\begin{aligned} \rho (H)\ge \frac{2|E(H)|}{|V(H)|}\ge 2\left\lfloor \frac{n}{6}\right\rfloor \ge \frac{n}{3}-2. \end{aligned}$$

By Fact 1, G is non-bipartite, since $\rho ^{2}(G)>\left\lfloor \frac{n^{2}}{4}\right\rfloor$. If H is bipartite, then $n-h\ge 1$ and $\rho (H)\le \frac{h}{2}$ by Fact 1. Thus $\frac{n}{3}-2\le \frac{h}{2}$, implying that $h\ge \frac{2}{3}n-4$. But then

$$\begin{aligned} \rho ^{2}(H)\ge \frac{hn}{3}-\frac{n^{2}}{12}-\frac{1}{4}>\frac{h^{2}}{4} \end{aligned}$$

as $\frac{2}{3}n-4\le h\le n-1$, implying that H contains a triangle by Fact 1. Thus H is non-bipartite.

Let $F_{0}=H$. If $F_{0}$ has a cut vertex, say $p_{1}$, let $F_{1}=F_{0}-p_{1}$. If $F_{1}$ has a cut vertex, say $p_{2}$, let $F_{2}=F_{1}-p_{2}$. Repeating this process as far as possible, we obtain some vertices $p_{1},p_{2},...,p_{s}$ of $F_{0}$ such that $p_{i}$ is a cut vertex of $F_{i-1}$ for each $1\le i\le s$, where $F_{i}$ is the subgraph of $F_{0}$ induced by $V(F_{0})-\left\{ p_{1},p_{2},...,p_{i}\right\}$. Let $F=F_{s}$. Then F has no cut vertices as the process stops at step s.

We claim that $s\le 5$. Otherwise the graph $F_{6}$ exists. Clearly, $F_{6}$ has at least 7 components. Thus $F_{6}$ has a vertex with degree at most $\frac{|V(F_{6})|}{7}<\frac{n}{7}$. Note that $\delta (F_{6})\ge \delta (F_{0})-6=\delta (H)-6\ge \frac{n}{6}-7$. Then $\frac{n}{6}-7<\frac{n}{7}$, a contradiction. So we obtain that $s\le 5$. Then $|V(F)|\ge h-5\ge \frac{n}{3}-6$ and $\delta (F)\ge \delta (F_{0})-5\ge \frac{n}{6}-6$.

By Lemma 3.4, we have that

$$\begin{aligned} \rho ^{2}(H)-\rho ^{2}(F)\le 2\sum _{1\le i\le s}d_{F_{i-1}}(p_{i})\le 2s(h-1)\le 10(h-1), \end{aligned}$$

implying that

$$\begin{aligned} \rho ^{2}(F)\ge \rho ^{2}(H)-10(h-1)\ge \frac{hn}{3}-\frac{n^{2}}{12}-\frac{1}{4}-10(h-1). \end{aligned}$$

Note that

$$\begin{aligned} 2|E(F)|\ge 2|E(H)|-2\sum _{1\le i\le s}d_{H}(p_{i})\ge 2|E(H)|-2s(h-1). \end{aligned}$$

Recall that $2|E(H)|\ge 2\left\lfloor \frac{n}{6}\right\rfloor \cdot h$. Then $2|E(F)|\ge 2\left\lfloor \frac{n}{6}\right\rfloor \cdot h-10h$ as $s\le 5$. Thus

$$\begin{aligned} \frac{2|E(F)|}{|V(F)|}\ge \frac{2|E(F)|}{h}\ge \frac{n}{3}-12. \end{aligned}$$

Hence $\rho (F)\ge \frac{2|E(F)|}{|V(F)|}\ge \frac{n}{3}-12$.

Since F has no cut vertices and $\delta (F)\ge \frac{n}{6}-6\ge 2$, each component of F is 2-connected. Let Q be a component of F such that $\rho (Q)=\rho (F)$. Then $\rho (Q)\ge \frac{n}{3}-12$ and thus $|V(Q)|\ge \rho (Q)+1\ge \frac{n}{3}-11$. Note that Q is 2-connected and $\delta (Q)\ge \frac{n}{6}-6\ge \frac{|V(Q)|}{7}$.

Now we shall prove that Q is non-bipartite. Recall that H is non-bipartite. We can assume that $Q\ne H$. Then F has another component, say $Q_{1}$. Since $\delta (F)\ge \left\lfloor \frac{n}{6}\right\rfloor -s$, we have $|V(Q_{1})|\ge \left\lfloor \frac{n}{6}\right\rfloor -s+1$. So $|V(Q)|\le h-s-(\left\lfloor \frac{n}{6}\right\rfloor -s+1)\le h-\frac{n}{6}$. If $\frac{n}{3}-12>\frac{h-\frac{n}{6}}{2}$, then $\rho (Q)\ge \frac{n}{3}-12>\frac{|V(Q)|}{2}$, implying that Q contains a triangle. Thus we can assume that $\frac{n}{3}-12\le \frac{h-\frac{n}{6}}{2}$, i.e., $h\ge \frac{5}{6}n-24$. When $\frac{5}{6}n-24\le h\le n$ and n is sufficiently large, it is easy to show that

$$\begin{aligned} \frac{hn}{3}-\frac{n^{2}}{12}-\frac{1}{4}-10(h-1)>\frac{(h-\frac{n}{6})^{2}}{4} \end{aligned}$$

(which is equivalent to $\frac{5}{3}\frac{h}{n}-(\frac{h}{n})^{2}-\frac{13}{36}>\frac{40h-39}{n^{2}}$, where $\frac{5}{6}-\frac{24}{n}\le \frac{h}{n}\le 1$). Thus

$$\begin{aligned} \rho ^{2}(Q)=\rho ^{2}(F)\ge \frac{hn}{3}- \frac{n^{2}}{12}-\frac{1}{4}-10(h-1)>\frac{(h-\frac{n}{6})^{2}}{4}\ge \frac{|V(Q)|^{2}}{4}. \end{aligned}$$

Then Q contains a triangle by Fact 1. Hence Q is non-bipartite.

Recall that $|V(Q)|\ge \frac{n}{3}-11$ and $\delta (Q)\ge \frac{n}{6}-6$. By Theorem 3.1 we have that

$$\begin{aligned} oc(Q)\ge \min \left\{ 2\delta (Q)-1,|V(Q)|\right\} \ge \frac{n}{3}-13. \end{aligned}$$

By Theorem 3.2, Q contains a cycle $C_{r}$ for all odd integers $r\in [K,\frac{n}{3}-13-K]$ for $n\ge N(\varepsilon )$. By Theorem 1 of [12], there is an integer $N_{0}$($:=10^{4}$, see [11]) such that the graph G on $n\ge N(\varepsilon )\ge N_{0}$ vertices contains a cycle $C_{r}$ for all integers $r\in [3,\frac{n}{320}]$ as $\rho (G)>\sqrt{\left\lfloor \frac{n^{2}}{4}\right\rfloor }$. Then G contains a cycle $C_{r}$ for all odd integers $r\in [3,(\frac{1}{3}-\varepsilon )n]$ for sufficiently large n.

By (i) and (ii), we have that G contains a cycle $C_{r}$ for all integers $r\in [3,(\frac{1}{3}-\varepsilon )n]$ for sufficiently large n. This completes the proof. $\square$

Using Corollary 2.6, we can only obtain mad$(G)\ge 2\left\lfloor \frac{n}{6}\right\rfloor$ if $\rho (G)>\sqrt{\left\lfloor \frac{n^{2}}{4}\right\rfloor }$. To improve the current constant $\frac{1}{3}$ in Theorem 3.5, one needs to obtain a larger constant $C>\frac{1}{3}$, such that mad$(G)\ge (C-\varepsilon )n$ if $\rho (G)>\sqrt{\left\lfloor \frac{n^{2}}{4}\right\rfloor }$. To do this, we need to strengthen Corollary 2.6 by using Theorem 2.5 when $n\le 6k$ (i.e., we need to reduce the upper bound in Corollary 2.6 by $\Theta (k)$).