Proof. Define a quadratic polynomial $f(x_1,x_2,\ldots ,x_k)=\sum _{i=1}^{k-1}x_ix_{i+1}.$ We first prove the left-hand inequality in (2.1). Let $x_j={\min }\{x_i \,|\, 1\le i\le k\}.$ We have

$$ \begin{align*} f(x_1,x_2,\ldots,x_k)&\ge x_1x_j+\cdots+x_{j-1}x_j+x_jx_{j+1}+x_jx_{j+2}+\cdots+x_jx_k\\ &=x_j(x_1+\cdots+x_{j-1}+x_{j+1}+\cdots+x_k)\\ &=x_j(n-x_j)\\ &\ge n-1. \end{align*} $$

This proves the first inequality in (2.1). The lower bound $n-1$ is attained for $x_1=n-k+1, x_2=\cdots =x_k=1.$

Now we prove the second inequality in (2.1). The case $k=2$ is an elementary fact: $f(x_1,x_2)=x_1 x_2\le \lfloor n/2\rfloor \cdot \lceil n/2\rceil $ , where equality holds when $x_1=\lfloor n/2\rfloor $ and $x_2=\lceil n/2\rceil .$ The case $k=3$ reduces to the case $k=2$ as follows:

$$ \begin{align*} f(x_1,x_2,x_3)=x_2(x_1+x_3)\le \lfloor n/2\rfloor\cdot \lceil n/2\rceil, \end{align*} $$

where equality holds when $x_2=\lfloor n/2\rfloor $ and $x_1+x_3=\lceil n/2\rceil .$ Next, suppose $k\ge 4.$ Denote by $f_{\max }$ the maximum value of $f.$ If $x_1{\kern-1pt}>{\kern-1pt}1,$ with $x_1^{\prime }{\kern-1pt}={\kern-1pt}1, x_2^{\prime }{\kern-1pt}={\kern-1pt}x_2, x_3^{\prime }{\kern-1pt}={\kern-1pt}x_3{\kern-1pt}+{\kern-1pt}x_1{\kern-1pt}-{\kern-1pt}1$ and $x_i^{\prime }=x_i$ for $i\ge 4$ , then

$$ \begin{align*} f(x_1^{\prime}, x_2^{\prime},\ldots,x_k^{\prime})-f(x_1,x_2,\ldots,x_k)=(x_1-1)x_4>0. \end{align*} $$

Similarly analysing the variable $x_k,$ we deduce that $f_{\max }$ can only be attained at some $x_1,\ldots ,x_k$ when $x_1=x_k=1,$ which we now assume. With $x_2^{\prime }=1, x_3^{\prime }=x_3, x_4^{\prime }=x_4+x_2-1$ and $x_i^{\prime }=x_i$ for $i=5,\ldots ,k-1$ ,

$$ \begin{align*} f(1,1,x_3^{\prime}, x_4^{\prime},\ldots,x_{k-1}^{\prime},1)-f(1,x_2,x_3,\ldots,x_{k-1},1)=(x_2-1)(x_5-1)\ge 0. \end{align*} $$

Hence, $f_{\max }$ can be attained at a certain $(1,1,x_3,\ldots ,x_{k-1},1).$ Successively applying this argument, we deduce that $f_{\max }$ can be attained at $(1,1,\ldots ,1,x_{k-2},x_{k-1},1).$ Now $(x_{k-2}+1)+(x_{k-1}+1)=n-k+4$ and so

$$ \begin{align*} f(1,1,\ldots,1,x_{k-2},x_{k-1},1)&=(x_{k-2}+1)(x_{k-1}+1)+k-5\\ &\le \lfloor (n-k+4)/2\rfloor\cdot \lceil (n-k+4)/2\rceil+k-5. \end{align*} $$

This proves the second inequality in (2.1). The upper bound is attained at $x_1=x_2=\cdots =x_{k-3}=x_k=1, x_{k-2}=\lfloor (n-k+2)/2\rfloor $ and $x_{k-1}=\lceil (n-k+2)/2\rceil .$

Proof. We will repeatedly use the condition that G is a $[p+2,p]$ -graph without necessarily mentioning it. Denote $\Delta =\Delta (G)$ and choose a vertex $x\in V(G)$ such that $\textrm {deg}(x)=\Delta .$ Let $S=N(x)$ and $T=V(G)\setminus S.$ Then, $|S|=\Delta .$

Suppose that G is triangle-free. Then, S is an independent set. Since G is a $[p+2,p]$ -graph, $\Delta \le p+1.$ We assert that $\Delta =p$ and hence G is p-regular, since $\delta (G)\ge p$ by the assumption. Otherwise, $\Delta =p+1.$ Since $n\ge 2p+3,\ |T|\ge p+2.$ Thus, $G[T]$ contains an edge $uv$ and $|\{u\}\cup S|=p+2$ implies that $\textrm {deg}_S(u)\ge p.$ Similarly, $\textrm {deg}_S(v)\ge p.$ Since $p+p=2p>p+1=|S|,$ we have $N_S(u)\cap N_S(v)\neq \emptyset .$ Let $w\in N_S(u)\cap N_S(v).$ Then, $wuvw$ is a triangle, which is a contradiction. This shows that G is p-regular.

Let $y\in S$ and denote $C=N(y).$ Then, C is an independent set and $|C|=p.$ Denote $D=T\setminus C.$ The structure of G is illustrated in Figure 2.

Figure 2

The structure of G.

Since $n\ge 2p+3,$ we have $|D|=n-2p\ge 3.$ Thus, D is not a clique, since G is triangle-free. Let z and f be any two distinct nonadjacent vertices in $D.$ Since $|\{z,f\}\cup S|=p+2, |\{z,f\}\cup C|=p+2$ , and S and C are independent sets,

$$ \begin{align*} \textrm{deg}_S(z)+\textrm{deg}_S(f)=|[\{z,f\}, S]|\ge p \quad \textrm{and} \quad \textrm{deg}_C(z)+\textrm{deg}_C(f)=|[\{z,f\}, C]|\ge p. \end{align*} $$

Note that $S\cap C=\emptyset $ and $\textrm {deg}(z)=\textrm {deg}(f)=p.$ We must have

(2.3) $$ \begin{align} |[\{z,f\}, S]|=p \quad \textrm{and} \quad |[\{z,f\}, C]|=p. \end{align} $$

We assert that D is an independent set. Otherwise, D contains two adjacent vertices $u_1$ and $u_2.$ Let $u_3\in D\setminus \{u_1, u_2\}.$ Since G is triangle-free, $u_3$ is nonadjacent to at least one vertex in $\{u_1, u_2\},$ say, $u_1$ . Setting $z=u_1$ and $f=u_3$ in (2.3), we deduce that $|[\{u_1,u_3\}, S\cup C]|=2p.$ However, since both $u_1$ and $u_3$ have degree $p,$ and $u_1$ already has a neighbour $u_2\not \in S\cup C,$ we have $|[\{u_1,u_3\}, S\cup C]|\le 2p-1,$ which is a contradiction.

Observe that now (2.3) holds for any two distinct vertices z and f in $D.$ Equation (2.3) has the equivalent form

(2.4) $$ \begin{align} \textrm{deg}_S(z)+\textrm{deg}_S(f)=p \quad \textrm{and} \quad \textrm{deg}_C(z)+\textrm{deg}_C(f)=p. \end{align} $$

Then, (2.4) and $|D|\ge 3$ imply that for any vertex $z\in D,$

(2.5) $$ \begin{align} \textrm{deg}_S(z)=\textrm{deg}_C(z)=p/2. \end{align} $$

To see this, in contrast, first suppose $\textrm {deg}_S(z)>p/2.$ Then, by the first equality in (2.4), for any two other vertices $f,r\in D$ , we have $\textrm {deg}_S(f)<p/2$ and $\textrm {deg}_S(r)<p/2,$ yielding $\textrm {deg}_S(f)+\textrm {deg}_S(r)<p,$ which contradicts (2.4). If $\textrm {deg}_S(z)<p/2,$ the same argument gives a contradiction. A similar analysis with C in place of S shows $\textrm {deg}_C(z)=p/2.$ Thus, we have proved (2.5). In particular, $q\triangleq p/2$ is a positive integer, that is, p is even. Now choose an arbitrary but fixed vertex $t\in D$ and denote $B=N_S(t), C_2=N_C(t), A=S\setminus B$ and $C_1=C\setminus C_2$ (see the illustration in Figure 2). We have

$$ \begin{align*} |A|=|B|=|C_1|=|C_2|=q. \end{align*} $$

Since G is p-regular of order $n\ge 2p+3,$ it is impossible that $p=2.$ Otherwise, G would be a $2$ -regular graph of order $\ge 7,$ which is not a $[4,2]$ -graph. Thus, $p\ge 4$ and $q\ge 2.$

Choose any two distinct vertices $v_1, v_2\in C_2.$ Then, $|\{v_1, v_2\}\cup S|=p+2$ implies that $|[\{v_1, v_2\}, S]|\ge p.$ Since G is triangle-free, $N(v_i)\cap B=\emptyset $ for $i=1, 2.$ Hence, $N_S(v_i)=N_A(v_i)$ for $i=1, 2.$ However, $|A|=q.$ We have $N_S(v_i)=A$ and $\textrm {deg}_A(v_i)=q$ for $i=1,2,$ implying that every vertex in $C_2$ is adjacent to every vertex in $A.$

Choose any two distinct vertices $v_3, v_4\in C_1.$ Then, $|\{v_3, v_4\}\cup C_2\cup B|=p+2.$ Since $\{v_3, v_4\}\cup C_2$ is an independent set and $[C_2, B]=\emptyset ,$ we have $|[\{v_3, v_4\}, B]|\ge p.$ However, $|B|=q.$ Hence, $N_B(v_j)=B$ for $j=3,4.$ This shows that every vertex in $C_1$ is adjacent to every vertex in $B.$ Consequently, every vertex in B has exactly q neighbours in $D.$

Choose any vertex $v_5\in B.$ Denote $M=N_D(v_5).$ We have $|M|=q.$ Since G is triangle-free and every vertex in B is adjacent to every vertex in $C_1,$ the neighbourhood of any vertex in M is disjoint from $C_1.$ Thus, the q neighbours of any vertex of M in C are exactly the vertices of $C_2,$ implying that every vertex in M is adjacent to every vertex in $C_2.$ The neighbourhood of any vertex in $C_2$ is $A\cup M.$ For the same reason, for any vertex $v_6\in B$ with $v_6\neq v_5,$ we must have $N_D(v_6)=M.$ Hence, the neighbourhood of any vertex in M is $B\cup C_2.$

We assert that $M=D.$ Otherwise, let $v_7\in D\setminus M.$ Take a vertex $v_8\in C_1.$ Note that $B\cup C_2$ is an independent set of cardinality p and $[v_7, B\cup C_2]=\emptyset .$ Denote $R=\{v_7, v_8\}\cup B\cup C_2.$ Then, $|R|=p+2$ and hence $G[R]$ has size at least $p.$ However, the size of $G[R]$ is at most $|[v_8, B]|+1=q+1<p,$ which is a contradiction. Finally, since G is p-regular, every vertex in A must be adjacent to every vertex in $C_1.$ Denote $V_1=A, V_2=C_1, V_3=B, V_4=D, V_5=C_2$ and set $V_6=V_1.$ Then, each $V_i$ is an independent set of cardinality $q=p/2$ and every vertex in $V_i$ is adjacent to every vertex in $V_{i+1}$ for $i=1,2,\ldots ,5.$ This proves that $G=C_5^{(q)}.$ Note that we have shown above that $q=|D|\ge 3,$ implying that $p=2q\ge 6.$

Conversely, let $H=C_5^{(q)}$ , where $q=p/2$ and $p\ge 6$ is even. We will prove that H is a triangle-free $[p+2,p]$ -graph. Write $H=H_1\vee H_2\vee H_3\vee H_4\vee H_5\vee H_1$ , where each $H_i=\overline {K_q}$ and $\vee $ is the join operation on two vertex-disjoint graphs. If H contains a triangle, it must lie in $H[V(H_i)\cup V(H_{i+1})]$ for some i ( $H_6\triangleq H_1$ ). However, this is a bipartite graph, containing no triangle.

Let $U\subseteq V(H)$ with $|U|=p+2.$ We need to show $e(H[U])\ge p.$ Denote $I=\{i \mid U\cap V(H_i)\neq \emptyset ,1\le i\le 5\}.$ Since $|H_i|=q$ for $1\le i\le 5$ and $|U|=p+2,$ we have $|I|\ge 3.$ Denote $x_i=|U\cap V(H_i)|$ for $1\le i\le 5.$ Then, $0\le x_i\le q.$ We distinguish three cases.

Case 1: $|I|=3.$ There are at least two consecutive integers in I ( $1$ and $5$ are regarded as consecutive here). Without loss of generality, suppose $1,2\in I.$ Then, $1\le x_1,\,x_2\le q$ and $x_1+x_2\ge p+2-q=q+2.$ Hence, $e(H[U])\ge x_1x_2\ge 2q=p.$

Case 2: $|I|=4.$ Without loss of generality, suppose $I=\{1,2,3,4\}.$ Then, $e(H[U])=x_1x_2+x_2x_3+x_3x_4$ , where each $x_i$ is a positive integer and $x_1+x_2+x_3+x_4=p+2.$ Applying Lemma 2.1, we have $e(H[U])\ge (p+2)-1=p+1>p.$

Case 3: $|I|=5.$ Now, $e(H[U])=x_1x_2+x_2x_3+x_3x_4+x_4x_5+x_5x_1$ , where each $x_i$ is a positive integer and $x_1+x_2+x_3+x_4+x_5=p+2.$ Applying Lemma 2.2, we have $e(H[U])\ge 2(p+2)-5=2p-1>p.$

In every case, H is a $[p+2,p]$ -graph. This completes the proof.

Proof. Let G be a $2$ -connected $[4,2]$ -graph of order at least $7.$ Since G is $2$ -connected, $\delta (G)\ge 2.$ By the case $p=2$ of Lemma 2.4, G contains a triangle $C_3.$ Then, successively applying Theorem 1.3, we deduce that G is pancyclic.