1.15

1 Introduction↩︎

For a graph \(G\), we denote the sizes of \(V(G)\) and \(E(G)\) by \(n(G)\) and \(e(G)\), respectively. All graphs are simple in this paper. By an (\(\ell\) mod \(k\))-cycle (resp. (\(\ell\) mod \(k\))-path), we mean a cycle (resp. path) of length \(\ell\) modulo \(k\). Let \(\mathcal{C}_{\ell\bmod k}\) be the set of all \((\ell\bmod k)\)-cycles. For a family \(\mathcal{F}\) of graphs, we denote by \(ex(n,\mathcal{F})\) the maximum number of edges in an \(n\)-vertex graph containing no member of \(\mathcal{F}\) as a subgraph. Determining \(ex(n,\mathcal{C}_{\ell\bmod k})\) has attracted extensive attention in extremal graph theory.

Burr and Erdős [1] conjectured in 1976 that such an \(n\)-vertex graph can contain at most a linear number of edges in \(n\). Bollobás [2] gave a positive answer to this conjecture. Erdős then asked what the exact value of the maximum number of edges in such a graph is.

Let \(G\) be an \(n\)-vertex graph with no \((\ell \bmod k)\)-cycles for some integers \(k>\ell\geq 0\) such that \(k\mathbb{Z}+\ell\) contains an even integer. Then \(k\) is odd or \(\ell\) is even. The cases \(k\leq 2\) are somewhat trivial. If \((k, \ell)=(1,0)\), or equivalently, \(G\) has no cycles, then one can see that \(e(G)\leq n-1\) and the equality holds if and only if \(G\) is a tree. A famous result states that if \((k, \ell)=(2,0)\), then \(e(G)\leq \frac{3}{2} (n-1)\) and, for \(2\mid (n-1)\), the equality holds if and only if each block of \(G\) is a triangle. The first non-trivial case is \(k=3\). Chen and Saito [3] showed that if \((k, \ell)=(3,0)\) then \(e(G)\leq 2(n-2)\) for \(n\geq 3\) and the equality holds if and only if \(G\) is isomorphic to \(K_{2,n-2}\). Dean et al. [4] and, independently, Saito [5] showed that for \(n\geq 5\) if \((k, \ell)=(3,2)\), then \(e(G)\leq 3(n-3)\) and the equality holds if and only if \(G\) is isomorphic to \(K_{3,n-3}\). Bai et al. [6] showed that if \((k, \ell)=(3,1)\), then \(e(G)\leq \frac{5}{3} (n-1)\) and, for \(9\mid (n-1)\), the equality holds if and only if each block of \(G\) is a Petersen graph.

For the case \(k=4\), since \(k\mathbb{Z}+\ell\) contains an even integer, it suffices to consider \(\ell=0\) or \(\ell=2\). Győri et al. [7] showed that if \((k, \ell)=(4,0)\), then \(e(G)\leq \frac{19}{12} (n-1)\) and they also constructed a family of graphs attaining this bound. Gao et al. [8] showed that if \((k, \ell)=(4,2)\), then \(e(G)\leq \frac{5}{2} (n-1)\) and, for \(4\mid (n-1)\), the equality holds if and only if each block of \(G\) is \(K_5\).

For general \(k\geq 3\), Bai et al. [9] showed that \(e(G)\leq (k-1)(n-k+1)\) if \(\ell=0\), and the bound is sharp when \(k\) is odd and \(n\geq 2k-3\). Their method also implies that \(e(G)\leq k(n-k)\) if \(\ell=2\), and the bound is sharp when \(k\) is odd and \(n\geq 2k\). It is mentioned that the latter result can also be obtained from the results of Gao et al. [10].

Let \(ex_2(n,\mathcal{F})\) be the maximum number of edges in a \(2\)-connected \(n\)-vertex graph with no graphs in \(\mathcal{F}\). It is not difficult to see that if a 2-connected graph contains no even cycles, then it is an odd cycle. So, \(ex_2(n, \mathcal{C}_{0 \bmod 2})=n\) when \(n\ge 3\) is odd and it is meaningless when \(n\) is even. By examining the characterization of extremal graphs for \(ex(n,\mathcal{C}_{\ell\bmod k})\) when \(k\in \{3,4\}\), one can observe that \(ex_2(n,\mathcal{C}_{\ell\bmod k}) = ex(n,\mathcal{C}_{\ell\bmod k})\) for \((\ell,k)\in \{(0,3),(2,3)\}\) for large \(n\), whereas the two parameters differ for \((\ell,k)\in \{(1,3),(0,4),(2,4)\}\). Very recently, Chu, Park, and Ryu [11] determined \(ex_2(n,\mathcal{C}_{0\bmod 4})\).

In this paper, we determine both \(ex_2(n,\mathcal{C}_{1\bmod 3})\) and \(ex_2(n,\mathcal{C}_{2\bmod 4})\), thereby completing the determination of the extremal number for \(2\)-connected graphs with no cycles of length congruent to a fixed residue modulo \(k\) for all \(k\le 4\).

It is not difficult to deduce that \(ex_2(n,\mathcal{C}_{2\bmod 4}) = 2n-2\), and that the extremal graphs are obtained from \(K_{2,n-2}\) by adding one edge in each part for \(n\ge 6\) (see Section 5). We therefore focus primarily on determining \(ex_2(n,\mathcal{C}_{1\bmod 3})\). Note that the value \(ex_2(4,\mathcal{C}_{1\bmod 3})\) is not defined as any \(2\)-connected \(4\)-vertex graph contains a \(4\)-cycle. The following is our main theorem.

As a consequence of Theorem 2, we characterize the extremal graphs for \(ex(n,\mathcal{C}_{1\bmod 3})\) for all values of \(n\), see Subsection 2.3.

Organization↩︎

The rest of this paper is organized as follows. In Section 2, we define the extremal graph families \(\mathcal{H}_n\) for \(ex_2(n,\mathcal{C}_{1\bmod 3})\), establish their basic properties, and also characterize all extremal graphs for \(ex(n,\mathcal{C}_{1\bmod 3})\). Section 3 collects several results needed in our proofs. The proof of Theorem 2, concerning \(2\)-connected graphs without \((1 \bmod 3)\)-cycles, is given in Section 4. Section 5 concludes with determining \(ex_2(n,\mathcal{C}_{2\bmod 4})\) and an open problem on \(ex_2(n,\mathcal{C}_{2\bmod 2k})\) for \(k\ge 3\).

2 Extremal graph families↩︎

2.1 Extensions and extendable pairs↩︎

Let \(i\in [1,3]\) and \(H\) be a graph. For two distinct vertices \(x,y\in V(H)\), we call \(\{x,y\}\) an \(i\)-extendable pair of \(H\) if \(H\) has no \((-i\bmod 3)\)-paths between \(x\) and \(y\). If \(\{x,y\}\) is an \(i\)-extendable pair of \(H\) and \(L\) is the graph obtained from \(H\) by adding an \((x,y)\)-path of length \(i+1\) which is internally vertex-disjoint with \(H\), then we call \(L\) an \(i\)-extension of \(H\). If \(H\) has exactly one \(i\)-extension up to isomorphism, then we will use \(L_i(H)\) to denote an \(i\)-extension of \(H\). We denote by \(\mathcal{L}_i(H)\) the set of \(i\)-extensions of \(H\). For a family \(\mathcal{H}\) of graphs, we set \(\mathcal{L}_i(\mathcal{H})=\bigcup_{H\in\mathcal{H}}\mathcal{L}_i(H)\).

A thread of a graph is a path whose internal vertices all have degree exactly \(2\). A thread of length \(k\) is called a \(k\)-thread. We call a thread (resp.\(k\)-thread) from \(x\) to \(y\) an \((x,y)\)-thread (resp.\((x,y)\)-\(k\)-thread). Note that every \(2\)-extension or \(3\)-extension of a graph always contains a \(3\)-thread. The length of a walk \(W\), denoted by \(\ell(W)\), is the number of edges in \(W\).

One can find in Table 1 the value of \(f(n)\) for small \(n\). We finish this subsection with a simple observation on the values of \(f(n)\).

2.2 Definition of \(\mathcal{H}_n\)↩︎

We define a graph class \(\mathcal{H}_n\) whose members are \(2\)-connected graphs on \(n\) vertices with \(f(n)\) edges and no \(\mathrm{(}1 \mathrm{\ mod\ 3)}\)-cycles. Later, we will show that \(\mathcal{H}_n\) consists precisely of the extremal graphs in our main theorem when \(n\geq 3\) and \(n\neq 4\).

For a graph \(G\), we denote by \(G^-\) a graph obtained from \(G\) by removing exactly one edge. First, we define the graphs \(H_n\) for each \(n\in\{3\}\cup[5,11]\), as follows (see Figure 1):

• \(H_3\) is isomorphic to \(C_3\);

• \(H_5\) is isomorphic to \(C_5\);

• \(H_6\) is the union of a \(C_3\) and a \(C_5\) which have an edge in common;

• \(H_7\) is obtained from a \(K_4\) by subdividing all edges of a \(K_{1,3}\) exactly once;

• \(H_8\) is obtained from a \(K_4\) by subdividing all edges of a \(C_4\) exactly once;

• \(H_9\) is obtained from a \(K_{3,3}\) by subdividing all edges of a \(3K_2\) exactly once;

• \(H_{10}\) is the Petersen graph;

• \(H_{11}\) is obtained from a \(K_5^-\) by subdividing all edges incident to \(x\) or \(y\) exactly once, where \(x\) and \(y\) are nonadjacent vertices in \(K_5^-\).

Now we define the class \(\mathcal{H}_n\) for all \(n\geq 3\), \(n\neq 4\):

• For \(n\in\{3,5,6,7,9,10,11\}\), \(\mathcal{H}_n=\{H_n\}\);

• \(\mathcal{H}_8=\{H_8,L_2(H_6)\}\) (see Figure 2);

• \(\mathcal{H}_{12}=\mathcal{L}_3(H_9)\cup\mathcal{L}_2(\mathcal{H}'_{10})\), where \(\mathcal{H}'_{10}=\mathcal{L}_3(H_7)\cup\mathcal{L}_2(\mathcal{H}_8)\) (see Figures 3 and 4);

• \(\mathcal{H}_{13}=\{L_3(H_{10})\}\);

• \(\mathcal{H}_{16}=\mathcal{L}_3(\mathcal{H}_{13})\);

• for even \(n\geq 14\) with \(n\neq 16\), \(\mathcal{H}_n=\mathcal{L}_3(\mathcal{H}_{n-3})\cup\mathcal{L}_2(\mathcal{H}_{n-2})\);

• for odd \(n\geq 15\), \(\mathcal{H}_n=\mathcal{L}_2(\mathcal{H}_{n-2})\).

Recall that \(H_{10}\) is the Petersen graph. We denote by \(H_{10}^-\) the graph obtained from \(H_{10}\) by removing an arbitrary edge.

2.3 Extremal graphs for \(ex(n,\mathcal{C}_{1\bmod 3})\)↩︎

By Theorem 1, when \(9 \mid (n-1)\), the extremal graphs for \(ex(n,\mathcal{C}_{1\bmod 3})\) are precisely the graphs whose blocks are isomorphic to the Petersen graph \(H_{10}\). However, a complete characterization for the remaining cases \(9 \nmid (n-1)\) was not previously known. In this subsection, using the graphs in \(\mathcal{H}_n\) from the previous section together with Theorem 2, we establish a complete characterization of the extremal graphs for \(ex(n,\mathcal{C}_{1\bmod 3})\) that holds for all \(n\), regardless of whether \(9\) divides \(n-1\). We remark that in [12], all extremal graphs for \(\operatorname{ex}(n,\mathcal{C}_{2\bmod 4})\) are characterized, even when \(4 \nmid (n-1)\).

3 Some results needed in our proofs↩︎

To find a \((1\bmod 3)\)-cycle, a common and effective approach is to seek two internally vertex-disjoint paths between given vertices and then analyze their lengths to obtain a cycle satisfying the desired length condition. The lemmas below will play an important role in our proofs.

We denote by \(N_2(G)\) the set of vertices with degree \(2\) in \(G\).

A vertex cut \(S\) of \(G\) is essential if \(G-S\) has at least two nontrivial components. We call a connected graph essentially \(k\)-connected if it contains no essential vertex cut of size at most \(k-1\). The following lemma follows directly from the proof of Theorem 2 in [6].

For \(p\geq 3\) and \(i\in[0,3]\), let \(K^{(i)}_{3,p}\) be a graph obtained from \(K_{3,p}\) by adding exactly \(i\) edges between vertices in the partite set of size three. We remark that \(K_{3,p}^{(0)}=K_{3,p}\), \(K_{3,p}^{(1)}=(K_1\cup K_2)\vee pK_1\), \(K_{3,p}^{(2)}=P_3\vee pK_1\), and \(K_{3,p}^{(3)}=K_3\vee pK_1\). Let \(W_p\) be the wheel of order \(p+1\), which is the graph obtained from a cycle \(C_p\) by adding a new vertex \(u\) and \(p\) edges from \(u\) to all vertices of the cycle \(C_p\). That is, \(W_p=K_1\vee C_p\). The following theorem characterizes 3-connected graphs without two disjoint cycles.

For a graph \(H\), we use \(H^*\) to denote the graph obtained from \(H\) by subdividing its every edge exactly once. Let \(\hat{W}_4\) denote the graph obtained from \(W_4\) by subdividing every edge of some \(K_{2,3}\) in \(W_4\) exactly once, \(K'_{3,3}\) the graph obtained from \(K_{3,3}\) by subdividing every edge of some \(C_4\) in \(K_{3,3}\) exactly once, and \(\hat{K}_{3,p}^{(i)}\) the graph obtained from \(K_{3,p}^{(i)}\) by subdividing every edge of a \(K_{3,p}\) exactly once, as shown in Figure 6. Notice that \(K_{3,p}^*=\hat{K}_{3,p}^{(0)}\). The following lemma is needed.

The proof of Lemma 3 will be given in Subsection 4.2.

4 Proofs↩︎

An inner-vertex in a block is a vertex that is not a cut-vertex of \(G\). A graph is a block-chain if it has exactly two end blocks, where an end block is a block of \(G\) containing exactly one cut-vertex of \(G\).

4.1 Proof of Theorem 2↩︎

By Fact 8, \(ex_2(n,\mathcal{C}_{1\bmod 3})\geq f(n)\) for \(n\geq 3\), \(n\neq 4\). Now let \(G\) be a 2-connected \(n\)-vertex graph without \((1\bmod 3)\)-cycles that has maximum number of edges. Then \(e(G)\geq f(n)\). We will show that \(e(G)=f(n)\) and \(G\in\mathcal{H}_n\) by using induction on \(n\).

If \(n=3,5\) or \(6\), then a graph contains no \((1\bmod 3)\)-cycles if and only if it contains no 4-cycles. We have \(e(G)\leq ex(n,C_4)=f(n)\). Note that \(H_3,H_5,H_6\) are the only \(2\)-connected extremal graphs for \(ex(n,C_4)\) (see [14]), and so \(G\cong H_3, H_5\) or \(H_6\), as desired. So assume that \(n\geq 7\). Note that we are done if \(G\in\mathcal{H}_n\). So assume also that \(G\not\in\mathcal{H}_n\) in the following.

By Claim 1, let \(xx'y'y\) be a \(3\)-thread of \(G\). Let \(G'=G-\{x',y'\}\). Then \(n(G')=n-2\) and \(e(G')=e(G)-3\geq f(n)-3\).

By Fact 6, \(e(G')=e(G)-3\geq f(n)-3\geq f(n-2)\) if \(n\neq 12\). By Claim 2, \(e(G')\leq f(n-2)\). It follows that \(n\notin\{7,10,12,13,16\}\), \(G'\in\mathcal{H}_{n-2}\) and \(G\) is a \(2\)-extension of \(G'\). That is, \(G\in\mathcal{H}_n\). Now we consider the exceptional case \(n=12\).

For \(n=12\), we have that \(n(G')=10\), \(e(G')\geq 13\). By Claim 2, \(G'\) is 2-connected without \((1\bmod 3)\)-cycles. By Claim 3, \(G'\in\mathcal{H}'_{10}\), and \(G\) is a 2-extension of \(G'\). That is, \(G\in\mathcal{H}_{12}\). This completes the proof.

4.2 Proof of Lemma 3↩︎

A simple subdivision of a graph \(H\) is obtained from \(H\) by subdividing each edge of \(H\) at most once. Suppose \(G\) is a simple subdivision of \(H\). In what follows, when no confusion arises, we simply say that an edge is subdivided to mean that an edge of \(H\) is subdivided in \(G\). For a subgraph \(H'\) of \(H\), we use \(\tau(H')\) to denote the number of edges in \(H'\) that are subdivided. If \(G'\) is the subgraph of \(G\) obtained by subdividing each edge of \(H'\) at most once, then we say that \(H'\) converts to \(G'\).

We notice that if \(C\) is a triangle in \(H\) and \(G\) is a simple subdivision of \(H\) without \((1\bmod 3)\)-cycles, then \(\tau(C)\neq 1\); and if \(C\) is a 4-cycle, then \(\tau(C)\neq 0\) or 3. We first prove the following fact.

Now let \(G\) be an essentially \(3\)-connected graph without \((1\bmod 3)\)-cycles such that \(G\) does not contain two vertex-disjoint cycles. Let \(H\) be the graph obtained from \(G\) by contracting one of the two edges incident to each vertex in \(N_2(G)\). Then \(H\) is 3-connected without two vertex-disjoint cycles, and \(G\) is a simple subdivision of \(H\). By Theorem 13, \(H\) is isomorphic to \(K_5^-\), \(K_5\), \(W_{p}\) or \(K^{(i)}_{3,p}\), where \(p\geq 3\) and \(0\leq i\leq 3\).

Set \(V(H)=\{v_1,\ldots,v_5\}\), and let \(v_1v_2\notin E(H)\). Let \(\tau=\tau(v_3v_4v_5v_3)\) (see Figure 8). Note that \(\tau\neq 1\) and that \(H-v_1\cong H-v_2\cong K_4\). By Fact 14, both \(H-v_1\) and \(H-v_2\) convert to an \(H_7\), \(H_8\) or \(K_4^*\).

Suppose first that \(\tau=0\). Then both \(H-v_1\) and \(H-v_2\) convert to an \(H_7\), implying that all edges between \(\{v_1,v_2\}\) and \(\{v_3,v_4,v_5\}\) are subdivided. That is, \(G\cong H_{11}\), as desired.

Suppose second that \(\tau=2\). Then both \(H-v_1\) and \(H-v_2\) convert to an \(H_7\) or \(H_8\). In each case \(\tau(v_3v_1v_4)=\tau(v_4v_2v_5)=1\). Now \(v_3v_1v_4v_2v_5v_3\) converts to a 7-cycle, a contradiction.

Suppose third that \(\tau=3\). Then both \(H-v_1\) and \(H-v_2\) converts to a \(K_4^*\). This implies that all edges of \(H\) are subdivided. Now \(v_3v_1v_4v_2v_5v_1\) converts to a 10-cycle, a contradiction.

For each edge \(e\) in \(H\), \(H-e\) is a \(K_5^-\). By the analysis of Case 1, we see that \(H-e\) converts to an \(H_{11}\) for each \(e\in E(H)\). Thus there are two edges \(e_1,e_2\in E(H)\) such that \(e_1\) is subdivided and \(e_2\) is not. Now \(H-e_1\) and \(H-e_2\) converts to two graphs with different edge numbers, one of which is not isomorphic to \(H_{11}\), a contradiction.

If \(p=3\), then \(H\cong K_4\). By Fact 14, \(G\in\{H_7, H_8, K_4^*\}\). Now we assume that \(p\geq 4\). Let \(u\) be the center of \(H\) and \(v_1v_2\ldots v_pv_1\) be the \(p\)-cycle of \(H\). Let \(C\) be a triangle in \(H\) with \(\tau:=\tau(C)\) as small as possible, say \(C=uv_1v_pu\) (see Figure 9). Note that \(\tau\neq 1\).

Suppose first that \(\tau=0\). If \(\tau(uv_2v_1)=0\), then \(uv_pv_1v_2u\) converts to a 4-cycle; if \(\tau(uv_2v_1)=1\), then \(uv_1v_2u\) converts to a 4-cycle, both contradictions. So we conclude that \(\tau(uv_2v_1)=2\), and similarly, \(\tau(uv_{p-1}v_p)=2\). That is, all four edges \(uv_2,v_1v_2,uv_{p-1},v_{p-1}v_p\) are subdivided. Now \(v_{p-1}uv_2\), \(v_{p-1}v_pv_1v_2\), \(v_{p-1}v_puv_1v_2\) convert to three \((v_{p-1},v_2)\)-paths of length 4, 5, 6, respectively. All the three paths are internally vertex-disjoint with the path that \(v_2v_3\ldots v_{p-1}\) converts to. Thus \(G\) contains a \((1\bmod 3)\)-cycle, a contradiction.

Suppose second that \(\tau=2\). If \(\tau(v_1v_p)=0\), then \(uv_1,uv_p\) are subdivided. In this case \(\tau(uv_2v_1)\neq 2\); for otherwise \(uv_pv_1v_2u\) converts a 7-cycle. It follows that \(\tau(uv_2v_1)=1\), and similarly \(\tau(uv_{p-1}v_p)=1\). Now \(uv_{p-1}v_pv_1v_2u\) converts a 7-cycle, a contradiction. So we conclude that \(\tau(v_1v_p)=1\) (i.e., \(v_1v_p\) is subdivided), and assume without loss of generality that \(uv_p\) is subdivided. If \(\tau(uv_{p-1}v_p)=2\), then \(uv_{p-1}v_pv_1u\) converts a 7-cycle, a contradiction. Thus we conclude that \(\tau(uv_{p-1}v_p)=1\). If \(uv_{p-1}\) is subdivided, then we can get a contradiction by the analysis above. So we conclude that \(v_{p-1}v_p\) is subdivided. By the choice of \(C\), \(uv_{p-2}\), \(v_{p-2}v_{p-1}\), \(v_1v_2\) and \(uv_2\) are subdivided. If \(p=4\), then \(v_{p-2}=v_2\) and \(G\cong\hat{W}_4\), as desired. Now assume that \(p\geq 5\). It follows that \(v_{p-2}uv_2\), \(v_{p-2}v_{p-1}uv_1v_2\), \(v_{p-2}v_{p-1}v_pv_1v_2\) convert to three \((v_{p-2},v_2)\)-paths of lengths 4, 6 and 8, respectively. All the three paths are internally vertex-disjoint with the path that \(v_2v_3\ldots v_{p-2}\) converts to. Thus \(G\) contains a \((1\bmod 3)\)-cycle, a contradiction.

Suppose third that \(\tau=3\). By the choice of \(C\), each edge of \(H\) is subdivided, and \(uv_1v_2v_3v_4u\) converts a 10-cycle, a contradiction.

We let \(X=\{x_1,x_2,x_3\}\) and \(Y=\{y_1,y_2,\ldots,y_p\}\) be the partition sets of \(H\), where \(e(H[X])=i\).

If \(i=0\), then \(H\cong K_{3,3}\). By Fact 14, \(G\in\{H_9, K'_{3,3},K_{3,3}^*\}\). Now assume that \(i\geq 1\). Let \(H'=H-E(H[X])\) and \(G'\) be the subgraph of \(G\) that \(H'\) converts to. By Fact 14, \(G'\in\{H_9, K'_{3,3},K_{3,3}^*\}\). If \(G'\cong H_9\), then each two vertices in \(X\) are connected by a 2-path and a 3-path in \(G'\). If \(G'\cong K'_{3,3}\), then each two vertices in \(X\) are connected by a 2-path and a 3- or 6-path in \(G'\). Since there is an edge \(e\in E(H[X])\), no matter \(e\) is subdivided or not, \(G\) has a \((1\bmod 3)\)-cycle, a contradiction. So we conclude that \(G'\cong K_{3,3}^*\), implying that all edges between \(X\) and \(Y\) are subdivided. Now each two vertices in \(X\) are connected by a 8-path in \(G\). If some edge in \(E(H[X])\) is subdivided, then \(G\) contains a 10-cycle, a contradiction. So we conclude that every edge in \(E(H[X])\) is not subdivided, and \(G\cong\hat{K}_{3,3}^{(i)}\).

For simplicity we denote by \(H_{ijk}\), \(1\leq i<j<k\leq p\), the subgraph of \(H\) induced by the edges between \(X\) and \(\{y_i,y_j,y_k\}\), and let \(G_{ijk}\) be the subgraph of \(G\) that \(H_{ijk}\) converts to. By Fact 14, we have \(G_{ijk}\in\{H_9,K'_{3,3}, K_{3,3}^*\}\). Let \(K\) be a claw of \(H\) with center in \(Y\) with \(\tau:=\tau(K)\) as small as possible, say \(y_1\) is the center of \(K\).

Suppose first that \(\tau=0\). Then \(G_{1jk}\cong K'_{3,3}\) for \(2\leq j<k\leq p\). It follows that each vertex in \(Y\backslash\{y_1\}\) is incident to exactly two subdivided edges. Now \(G_{234}\) is not isomorphic to \(H_9\), \(K'_{3,3}\) and \(K_{3,3}^*\), a contradiction.

Suppose second that \(\tau=1\). Then \(G_{1jk}\cong H_9\) for \(2\leq j<k\leq p\). It follows that each vertex in \(Y\backslash\{y_1\}\) is incident to exactly one subdivided edge. Thus two subdivided edges between \(X\) and \(Y\) are adjacent, say \(x_1y_2,x_1y_3\). Now \(G_{234}\) is not isomorphic to \(H_9\), \(K'_{3,3}\) and \(K_{3,3}^*\), a contradiction.

Suppose third that \(\tau=2\). Then \(G_{1jk}\cong K'_{3,3}\) for \(2\leq j<k\leq p\). It follows that some vertex in \(Y\) is not incident to any subdivided edge, contradicting the choice of \(K\).

Suppose fourth that \(\tau=3\). By the choice of \(K\), all edges between \(X\) and \(Y\) are subdivided. Note that each two vertices in \(X\) are connected by a 8-path in \(G\). This implies that all edges in \(E(H[X])\) is not subdivided. Thus \(G\cong\hat{K}_{3,p}^{(i)}\), as desired.

5 Concluding remarks↩︎

We conclude with some remarks on graphs without \((2\bmod 4)\)-cycles. Gao et al. [8] showed that if \(G\) contains no \((2\bmod 4)\)-cycle, then \(e(G)\leq \frac{5}{2} (n-1)\) and, for \(4\mid (n-1)\), the equality holds if and only if each block of \(G\) is isomorphic to \(K_5\). We consider the 2-connected setting and determine the corresponding maximum number of edges. For \(k\geq 0\), we let \(F_k=K_2\vee(K_2\cup kK_1)\) (see Figure 10). Note that \(F_0=K_4\). The following results are needed in our proof.

Finally, we propose the following conjecture for the general cases.

Acknowledgement↩︎

The research of Yandong Bai and Binlong Li was supported by the National Key Research and Development Program of China (No. 2026YFE0151700), National Natural Science Foundation of China (Nos. 12542043, 12242111, 12131013), and Guangdong Basic and Applied Basic Research Foundation (No. 2023A1515030208). Hojin Chu was supported by a KIAS Individual Grant (CG101801) at Korea Institute for Advanced Study. Boram Park was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (No. RS-2025-00523206), and supported by the New Faculty Startup Fund from Seoul National University.