Vertex-disjoint multiquadrilaterals in multigraphs

Abstract

A cycle of length 4 is called a quadrilateral and a multigraph is called standard if every edge in it has multiplicity at most 2. A quadrilateral with four multiedges is called heavy-quadrilateral. It is proved that if the minimum degree of M is at least 6k-2, then M contains k vertex-disjoint quadrilaterals, such that k-1 of them are heavy-quadrilaterals and the remaining one is a quadrilateral with three multiedges, with only three exceptions.

Keywords

Multiquadrilateral / standard multigraph / minimum degree

1 Introduction

The directed graphs considered in this paper are simple, finite directed graphs without cycles or multiple edges. Definitions and terminology not explicitly provided in the text can be found in reference [1]. An arc \left(x,y\right)\in A\left(D\right) of a directed graph D refers to a directed edge starting from x and ending at y. For \mathrm{\forall }x\in V\left(D\right), the in-degree and out-degree are defined as follows: {d_D}^{-}\left(x\right):=\left|\{z\in V\left(D\right)\right|\left(z,x\right)\in A\left(D\right)\left\}\right| and {d_D}^{+}\left(x\right):=\left|\{x\in V\left(D\right)\right|\left(x,z\right)\in A\left(D\right)\left\}\right|. The degree of x in D is given by d_D\left(x\right)={d_D}^{-}\left(x\right)+{d_D}^{+}\left(x\right). The minimum degree of D is defined as \delta \left(D\right):=\mathrm{m}\mathrm{i}\mathrm{n}\left\{d_D\left(x\right)\right|x\in V\left(D\right)\}. Let K_n^{\ast } be an n-vertex directed graph, such that for any \{u,v\}\subseteq V\left(K_n^{\ast }\right) there is \{\left(u,v\right),\left(v,u\right)\}\subseteq A\left(K_n^{\ast }\right). A special graph D* is defined as [6]: D^{\ast }=D\left[V\right(D_1\cup D_2\left)\right], where D_1\cong D_2\cong K_{2k}^{\ast }, k is an odd integer and \mathrm{V}\left(D_1\right)\cap V\left(D_2\right)=\varnothing ,\left(u,v\right)\in A\left(D\right). Additionally, for any u\in V\left(D_1\right) and v\in V\left(D_2\right), \left(u,v\right)\in A\left(D\right) and \left(v,u\right)\notin A\left(D\right).

Let M=\left(V\left(M\right),E\right) be a multigraph. For any x,y\in V\left(M\right), let {\mu }_M\left(x,y\right) be the number of edges connecting x and y in M. If xy\notin E, then {\mu }_M\left(x,y\right)=0. Define \mu \left(M\right):={\mathrm{m}\mathrm{a}\mathrm{x}}_{x,y\in V\left(M\right)}{\mu }_M\left(x,y\right). The degree of x in M is defined as d_M\left(x\right)={\mathrm{\Sigma }}_{y\in V\left(M\right)}{\mu }_M\left(x,y\right) and the minimum degree of M is \delta \left(M\right):=\mathrm{m}\mathrm{i}\mathrm{n}\left\{d_M\right(x\left)\right|x\in V\left(M\right)\}. A 4-vertex multigraph Q_7^4 contains a quadrilateral xyzwx and {\mu }_M\left(x,y\right)={\mu }_M\left(y,z\right)={\mu }_M\left(z,w\right)=2, This structure is called a 7-quadrilateral. A 4-vertex multigraph Q_8^4 contains a quadrilateral xyzwx and {\mu }_M\left(x,y\right)={\mu }_M\left(y,z\right)={\mu }_M\left(z,w\right)={\mu }_M\left(w,x\right)=2. t{Q}_7^4 is used to describe a set containing t pairwise disjoint Q_7^4 subgraphs. The notation M\supseteq t{Q}_7^4 indicates that M contains t pairwise disjoint 7-quadrilaterals.

Removing the direction of all arcs in a simple directed graph D results in a multigraph M. Specifically, if \left(x,y\right)\in A\left(D\right) and \left(y,x\right)\in A\left(D\right), then {\mu }_M\left(x,y\right)=2, and there is \delta \left(D\right)=\delta \left(M\right). If M\supseteq Q_7^4, then D contains a directed quadrilateral with the same vertex set. A multigraph M:=\left(V\left(M\right),E\right) is called standard if \mu \left(M\right)\le 2. For a given standard multigraph M, the two types of simple graphs [2] are defined as follows: G:=G_M:=\left(V\right(M),E_G) and H:=H_M:=\left(V\left(M\right),E_H\right), where E_G:=\{xy:{\mu }_M\left(x,y\right)\ge 1\} and E_H:=\{xy:{\mu }_M\left(x,y\right)=2\}. An edge xy\in E_H is called a double edge, while an edge xy\in E_G\mathrm{\setminus }{E}_H is called a single edge. A subgraph M^{\prime } of M is said to be double-edged if all of its edges are double edges. In this paper, {\mathbb{D}}^{\mathbb{\ast }} is used to denote the graph obtained by removing the direction of all arcs in D*.

Let M=\left(V\right(M),E) be a multigraph, where \left|M\right|:=\left|V\right(M\left)\right| and \Vert M\Vert :=\left|E\right|. For a subset U\subseteq V\left(M\right), denote \Vert U\Vert :=\Vert M\left[U\right]\Vert. For any v\in V\left(M\right), define \Vert \left\{v\right\},U\Vert :=\sum _{x\in U} {\mu }_M(v,u). For any subsets U,U^{\prime }\in V\left(M\right), define \Vert U,U^{\prime }\Vert :=\sum _{v\in U} \Vert \left\{v\right\},U^{\prime }\Vert. The set of edges with one endpoint in U and the other in ,U^{\prime } is denoted by E(U,U^{\prime }). Hence, there is \Vert U,U^{\prime }\Vert =\left|E\left(U,U^{\prime }\right)\right|+\Vert U\cap U^{\prime }\Vert.

Before presenting the main results of this paper, two special multigraphs are first introduced. {\mathbb{F}}^{\mathbb{\ast }} is a multigraph of order 4k: Let F_1\cong K_{2k+1},\left|V\left(F_2\right)\right|=2k-1, with V\left(F_1\right)\cap V\left(F_2\right)=\varnothing. Each vertex in V(F₁) is connected to each vertex in V(F₂) with double edges. The resulting graph is denoted as {\mathbb{F}}^{\mathbb{\ast }}. Let {\mathbb{B}}^{\mathbb{\ast }} be a multigraph of order 4k, where V\left(B_1\right)\cap V\left(B_2\right)=\varnothing. The subgraph B₁ consists of k + 1 disjoint copies of K_2^{\ast }, and any two such K_2^{\ast } subgraphs have their four vertices connected by four single edges. Additionally, \left|V\left(B_2\right)\right|=2k-2, \delta \left(B_2\right)\ge 2k-6. Each vertex in B₁ is connected to each vertex in B₂ with double edges, forming the graph {\mathbb{B}}^{\mathbb{\ast }}. It is known that {\mathbb{F}}^{\mathbb{\ast }}⊉(k-1)Q_8^4\cup Q_7^4, {\mathbb{B}}^{\mathbb{\ast }}⊉(k-1)Q_8^4\cup Q_7^4, but {\mathbb{B}}^{\mathbb{\ast }}\supseteq k{Q}_7^4.

Czygrinow et al. [2] were the first to study pairwise disjoint triangles in standard multigraphs. Subsequently, Gao et al. [4] investigated the existence of pairwise disjoint Q_7^4 subgraphs in standard multigraphs and proved the following results.

Theorem 1.1 [4]　 Let M be a standard multigraph of order 4k, where k is a positive integer. If \delta \left(M\right)\ge 6k-2, then M\supseteq k{Q}_7^4, unless M\in \{{\mathbb{D}}^{\mathbb{\ast }},{\mathbb{F}}^{\mathbb{\ast }}\}.

In this paper, Theorem 1.1 is strengthened according to the proof techniques of Gao[4].

Theorem 1.2　 Let M be a standard multigraph of order 4k, where k is a positive integer. If \delta \left(M\right)\ge 6k-2, then M\supseteq \left(k-1\right)Q_8^4\cup Q_7^4, then M\in \{{\mathbb{D}}^{\mathbb{\ast }},{\mathbb{F}}^{\mathbb{\ast }},{\mathbb{B}}^{\mathbb{\ast }}\}.

Let D^{\ast },F^{\ast },B^{\ast } be the corresponding simple graphs of {\mathbb{D}}^{\mathbb{\ast }},{\mathbb{E}}^{\mathbb{\ast }},{\mathbb{B}}^{\mathbb{\ast }}, respectively. By Theorem 1.2, the following theorem is evident, providing an improvement on the main results obtained by Zhang and Wang [7]: A simple graph of order 4k and minimum degree at least 2k-1 contains k-1 pairwise disjoint 4-cycles.

Theorem 1.3　 Let G be a simple graph of order 4k, where k is a positive integer. If \delta \left(G\right)\ge 2k-1, then G contains k-1 pairwise disjoint 4-cycles and a path of order 4, unless G\cong \{D^{\ast },F^{\ast },B^{\ast }\}.

Furthermore, if the minimum degree bound in Theorem 1.3 is increased by 1, the main result established by Randerath et al. can be obtained [5].

Theorem 1.4 [5]　 Let G be a simple graph of order 4k, where k is a positive integer. If \delta \left(G\right)\ge 2k, then G contains k−1 pairwise disjoint 4-cycles and a path of order 4.

Theorem 1.5 [7]　 Let D be a directed graph of order 4k, where k is a positive integer. If \delta \left(D\right)\ge 2k-1, then D contains k pairwise disjoint directed quadrilaterals, except when \mathrm{D}\cong D^{\ast }.

Proof　Let M be the standard multigraph corresponding to D, and there is \delta \left(M\right)\ge 6k-2. If M\supseteq k{Q}_7^4, then D contains k pairwise disjoint directed quadrilaterals. Thus, it may be assumed that \mathrm{M}⊉k{Q}_7^4. Theorem 1.2 implies that M\in \{{\mathbb{D}}^{\mathbb{\ast }},{\mathbb{F}}^{\mathbb{\ast }}\}. If M\cong {\mathbb{D}}^{\mathbb{\ast }}, then D\cong D^{\ast }. Otherwise, if M\cong {\mathbb{F}}^{\mathbb{\ast }}, then D\supseteq \left(k-1\right)Q_7^4 and contains a subset M^{\prime }=\{x_1,x_2,x_3,x_4\}, such that M^{\prime } is vertex-disjoint from the previously mentioned subgraphs. Additionally, the edges x_1{x}_2,x_1{x}_3, and x_1{x}_4 are double edges, while x_2{x}_3,x_2{x}_4, and x_3{x}_4 are single edges. Since D\left[x_2,x_3,x_4\right] must contain a directed path of order 3, it follows that D\left[x_1,x_2,x_3,x_4\right] contains a directed quadrilateral. Consequently, D contains k pairwise disjoint directed quadrilaterals, leading to a contradiction.

Finally, recall the conjecture proposed by Erdös and Faudree [3]: A simple graph of order 4k and minimum degree at least 2k contains k pairwise disjoint 4-cycles. This conjecture was a highly challenging problem and not proven until 2010 by Wang [6], an internationally recognized expert in subgraph research. Therefore, a related question is proposed as the conclusion of this section:

Conjecture 1.1　 Let M be a standard multigraph of order 4k, where k is a positive integer. If \delta \left(M\right)\ge 6k-2, then M\supseteq k{Q}_8^4, unless M is isomorphic to certain special graphs.

If Conjecture 1.1 can be proven true, the Erdös-Faudree conjecture [4] will be correct.

2 Preliminaries

In the following lemmas, let M be a standard multigraph and G^{\prime } be an arbitrary simple graph. For simplicity, consider G^{\prime } as a multigraph.

Lemma 2.1 [6]　 Let G^{\prime } be a simple graph of order 4k where k is a positive integer. If \delta \left(G^{\prime }\right)\ge 2k-1, then G^{\prime } contains k-1 pairwise disjoint quadrilaterals.

Lemma 2.2 [5]　 Let C be a quadrilateral and let x and y be two distinct vertices in G^{\prime } that are not on C. If \Vert \{x,y\},V\left(C\right)\Vert \ge 5, then G^{\prime }\left[V\left(C\right)\cup \{x,y\}\right] contains a quadrilateral C^{\prime } and an edge e such that C^{\prime } and e are vertex-disjoint, and e is incident to exactly one of {x,y}.

Lemma 2.3　 Let C contain Q_8^4 as an induced subgraph, and x and y be two distinct vertices in M that are not on C. If \Vert x,V\left(C\right)\Vert =\Vert y,V\left(C\right)\Vert =6 and \Vert x,V\left(C\right){\Vert }_H=\Vert y,V\left(C\right){\Vert }_H=2, then M\left[V\right(C)\cup \{x,y\left\}\right] contains C^{\prime }\supseteq Q_8^4 and a double edge e such that C^{\prime } and e are vertex-disjoint, except in the following three cases. Let \mathrm{C}=x_1{x}_2{x}_3{x}_4{x}_1:

(1) xx₁, xx₂, yx₃, yx₄ are all double edges.

(2) xx₁, xx₂, yx₂, yx₃ are all double edges.

(3) \Vert x,V\left(C\right){\Vert }_H=\Vert y,V\left(C\right){\Vert }_H=2 and x and y share the same two double-edge neighbors in V(C), specifically: xx₁, xx₃, yx₁, and yx₃ are all double edges, or xx₂, xx₄, yx₂, and yx₄ are all double edges.

Lemma 2.4　 Let \overline{U}=\{x,y,z,w\}\subseteq V\left(M\right). Suppose \Vert \overline{U}\Vert \ge 9 and M\left[\overline{U}\right]⊉Q_7^4. Then, if \Vert \overline{U}\Vert =9, one of the following two cases must hold:

(1) M\left[\overline{U}\right] contains a triangle with a double edge, denoted as xyzx, such that wx, wz, and wy are single edges.

(2) M\left[\overline{U}\right] contains a star graph centered at x, where xy, xz, and xw are double edges, while wz, yz, and yw are single edges.

Lemma 2.5　 Let \overline{U} and F be two vertex-disjoint 4-vertex subgraphs of M, where F\supseteq Q_8^4, and \overline{U} contains two vertex-disjoint independent double edges. If \Vert V\left(F\right),V\left(\overline{U}\right)\Vert \ge 25, then M\left[V\left(F\right)\cup \overline{U}\right]\supseteq Q_7^4\cup Q_8^4.

Proof　It is proceeded by contradiction. Assume that M\left[V\left(F\right)\cup \overline{U}\right]⊉Q_7^4\cup Q_8^4. Let F=u_1{u}_2{u}_3{u}_4{u}_1 and V\left(\overline{U}\right)=\{x_1,x_2,x_3,x_4\}, where x₁x₂ and x₃x₄ are double edges. Since \Vert V\left(F\right),V\left(\overline{U}\right)\Vert \ge 25, it follows that \Vert V\left(F\right),V\left(\overline{U}\right){\Vert }_H\ge 9. By symmetry, it may be assumed that \Vert \{x_1,x_2\},V\left(F\right){\Vert }_H\ge 5.

(a) \Vert \{x_1,x_2\},V\left(F\right){\Vert }_H=8, \Vert \{x_3,x_4\},V\left(F\right){\Vert }_H\ge 1. Since x_1{x}_2{u}_1{u}_2{x}_1\supseteq Q_8^4, x_1{x}_2{u}_3{u}_4{x}_1\supseteq Q_8^4, it follows that M\left[\right\{x_3,x_4,u_3,u_4\left\}\right]⊉Q_7^4, M\left[\right\{x_3,x_4,u_1,u_2\left\}\right]⊉Q_7^4. Thus \Vert \{x_3,x_4\},\{u_3,u_4\}\Vert \le 4, \Vert \{x_3,x_4\},\{u_1,u_2\}\Vert \le 4. This implies \Vert \{x_3,x_4\},V\left(F\right)\Vert \le 8, leading to \Vert V\left(F\right),V\left(\overline{U}\right)\Vert \le 16+8=24, which contradicts the given assumption.

(b) \Vert \{x_1,x_2\},V\left(F\right){\Vert }_H=7, \Vert \{x_3,x_4\},V\left(F\right){\Vert }_H\ge 2. Assume that \Vert \left\{x_1\right\},V\left(F\right){\Vert }_H=4, and x₂u₁, x₂u₂, x₂u₃ are double edges. Then, x_1{x}_2{u}_1{u}_2{x}_1\supseteq Q_8^4, x_1{x}_2{u}_3{u}_4{x}_1\supseteq Q_8^4.It is concluded that M\left[\right\{x_3,x_4,u_3,u_4\left\}\right]⊉Q_7^4, M\left[\right\{x_3,x_4,u_1,u_2\left\}\right]⊉Q_7^4. Thus, \Vert \{x_3,x_4\},\{u_3,u_4\}\Vert \le 4, \Vert \{x_3,x_4\},\{u_1,u_2\}\Vert \le 4. This implies \Vert \{x_3,x_4\},V\left(F\right)\Vert \le 8, leading to \Vert V\left(F\right),V\left(\overline{U}\right)\Vert \le 16+8=24, which contradicts the given assumption.

(c) \Vert \{x_1,x_2\},V\left(F\right){\Vert }_H=6, \Vert \{x_3,x_4\},V\left(F\right){\Vert }_H\ge 3. Assume that \Vert \left\{x_1\right\},V\left(F\right){\Vert }_H\ge 3.

(i) \Vert \left\{x_1\right\},V\left(F\right){\Vert }_H=4, \Vert \left\{x_2\right\},V\left(F\right){\Vert }_H=2. Without losing generality, assume that x₂u₁ and x₂u₂ are double edges. Then, x_1{x}_2{u}_1{u}_4{x}_1\supseteq Q_8^4, x_1{x}_2{u}_2{u}_3{x}_1\supseteq Q_8^4. This implies that M\left[\right\{x_3,x_4,u_2,u_3\left\}\right]⊉Q_7^4, M\left[\left\{x_3,x_4,u_1,u_4\right\}\right]⊉Q_7^4. Thus, \Vert \{x_3,x_4\},V\left(F\right)\Vert \le 8, \Vert V\left(F\right),V\left(\overline{U}\right)\Vert \le 16+8=24, which contradicts the given assumption.

(ii) \Vert \left\{x_1\right\},V\left(F\right){\Vert }_H=3, \Vert \left\{x_2\right\},V\left(F\right){\Vert }_H=3. Then x₁ and x₂ must be double-edge connected to the same three vertices. Otherwise, the argument would reduce to case (i), leading to a contradiction. Assume that x₁u₁, x₁u₂, x₁u₃, x₂u₁, x₂u₂, x₂u₃ are double edges. Then, x_1{x}_2{u}_1{u}_2{x}_1\supseteq Q_8^4, x_1{x}_2{u}_2{u}_3{x}_1\supseteq Q_8^4. This implies that M\left[\right\{x_3,x_4,u_2,u_3\left\}\right]⊉Q_7^4, M\left[\right\{x_3,x_4,u_1,u_4\left\}\right]⊉Q_7^4. Thus, \Vert \{x_3,x_4\},\{u_3,u_4\}\Vert \le 4, \Vert \{x_3,x_4\},\{u_1,u_4\}\Vert \le 4. Since x_1{u}_1{u}_4{u}_3{x}_1\supseteq Q_8^4, it follows that x₄u₂ cannot be a double edge. Otherwise, x_2{x}_3{x}_4{u}_2{x}_2\supseteq Q_7^4. Similarly, since x_2{u}_1{u}_4{u}_3{x}_2\supseteq Q_8^4, it follows that x₃u₂ cannot be a double edge. Otherwise, x_1{x}_4{x}_3{u}_2{x}_1\supseteq Q_7^4. Thus, there is \Vert \{x_3,x_4\},\left\{u_2\right\}\Vert \le 2. However, the given assumption states that 25\le \Vert V\left(F\right),V\left(\overline{U}\right)\Vert \le 3\times 2+3\times 2+2+4+4+2=24, which is a contradiction.

(d) \Vert \{x_1,x_2\},V\left(F\right){\Vert }_H=5,\Vert \{x_3,x_4\},V\left(F\right){\Vert }_H\ge 4.

(i) \Vert \left\{x_1\right\},V\left(F\right){\Vert }_H=3, \Vert \left\{x_2\right\},V\left(F\right){\Vert }_H=2. Assume that x₁u₁, x₁u₂, x₁u₃ are double edges, then one of the following must hold: \Vert \left\{x_2\right\},\{u_1,u_2\}{\Vert }_H=2, \Vert \left\{x_2\right\},\{u_1,u_3\}{\Vert }_H=2, \Vert \left\{x_2\right\},\{u_1,u_4\}{\Vert }_H=2 or \Vert \left\{x_2\right\},\{u_2,u_4\}{\Vert }_H=2. When \Vert \left\{x_2\right\},\{u_1,u_2\}{\Vert }_H=2, there are x_1{x}_2{u}_1{u}_2{x}_1\supseteq Q_8^4andx_1{x}_2{u}_2{u}_3{x}_1\supseteq Q_8^4. It follows that M\left[\right\{x_3,x_4,u_3,u_4\left\}\right]⊉Q_7^4, M\left[\right\{x_3,x_4,u_1,u_4\left\}\right]⊉Q_7^4. Thus, \Vert \{x_3,x_4\},\{u_3,u_4\}\Vert \le 4, \Vert \{x_3,x_4\},\{u_1,u_4\}\Vert \le 4. Since x_1{u}_1{u}_4{u}_3{x}_1\supseteq Q_8^4, it follows that x₄u₂ cannot be a double edge. Otherwise, x_2{x}_3{x}_4{u}_2{x}_2\supseteq Q_7^4. Hence, \Vert \{x_3,x_4\},\left\{u_2\right\}\Vert \le 3. However, the assumption states that 25\le \Vert V\left(F\right),V\left(\overline{U}\right)\Vert \le 5\times 2+3\times 1+4+4+3=24, which is a contradiction.\Vert \left\{x_2\right\},\{u_1,u_3\}{\Vert }_H=2 and \Vert \left\{x_2\right\},\{u_1,u_4\}{\Vert }_H=2 follow a similar argument, leading to a contradiction. When \Vert \left\{x_2\right\},\{u_2,u_4\}{\Vert }_H=2, there is x_1{x}_2{u}_4{u}_1{x}_1\supseteq Q_8^4, x_1{x}_2{u}_2{u}_3{x}_1\supseteq Q_8^4. Then, M\left[\right\{x_3,x_4,u_3,u_2\left\}\right]⊉Q_7^4, M\left[\right\{x_3,x_4,u_1,u_4\left\}\right]⊉Q_7^4. This implies that \Vert \{x_3,x_4\},\{u_3,u_2\}\Vert \le 4, \Vert \{x_3,x_4\},\{u_1,u_4\}\Vert \le 4. Hence, \Vert \{x_3,x_4\},V\left(F\right)\Vert \le 8. This leads to 25\le \Vert V\left(F\right),V\left(\overline{U}\right)\Vert \le 16+8=24, which is a contradiction.

(ii) \Vert \left\{x_1\right\},V\left(F\right){\Vert }_H=4, \Vert \left\{x_2\right\},V\left(F\right){\Vert }_H=1. Assume that x₂u₁ is a double edge. Then, x_1{x}_2{u}_1{u}_2{x}_1\supseteq Q_8^4, x_1{x}_2{u}_1{u}_4{x}_1\supseteq Q_8^4. This implies that M\left[\right\{x_3,x_4,u_3,u_4\left\}\right]⊉Q_7^4, M\left[\right\{x_3,x_4,u_2,u_3\left\}\right]⊉Q_7^4. Thus, \Vert \{x_3,x_4\},\{u_3,u_4\}\Vert \le 4, \Vert \{x_3,x_4\},\{u_2,u_3\}\Vert \le 4. Since x_1{u}_2{u}_3{u}_4{x}_1\supseteq Q_8^4, it follows that x₄u₁ cannot be a double edge. Otherwise, x_2{u}_1{x}_4{x}_3{x}_2\supseteq Q_7^4. Thus, \Vert \{x_3,x_4\},\left\{u_1\right\}\Vert \le 3. However, the assumption states that 25\le \Vert V\left(F\right),V\left(\overline{U}\right)\Vert \le 5\times 2+3\times 1+4+4+3=24, which is a contradiction. Thus, the lemma is proven. □

3 Proof of Theorem 1.2

It is proceeded by contradiction. Suppose M is a standard multigraph of order 4k with \delta \left(M\right)\ge 6k-2. Assume that M⊉\left(k-1\right)Q_8^4\cup Q_7^4. It requires to prove that M\in \left\{{\mathbb{D}}^{\mathbb{\ast }},{\mathbb{F}}^{\mathbb{\ast }},{\mathbb{B}}^{\mathbb{\ast }}\right\}. \mathrm{\forall }x\in V\left(M\right), and there is

(1)d_H\left(x\right)\ge d_M\left(x\right)-\left(4k-1\right)\ge \delta \left(M\right)-\left(4k-1\right)\ge 6k-2-\left(4k-1\right)=2k-1.

By Lemma 2.1, it follows that M\supseteq \left(k-1\right)Q_8^4, denoted as U_1,U_2,\dots ,U_{k-1}. Define U=\bigcup _{i=1}^{k-1} U_i and \overline{U}=V\left(M\right)\mathrm{\setminus }V\left(U\right). For each j\in \{1,2,\dots ,k-1\}, since U_j\supseteq Q_8^4, choose U_1,U_2,\dots ,U_{k-1} such that

(2)\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{n}\mathrm{u}\mathrm{m}\mathrm{b}\mathrm{e}\mathrm{r}\mathrm{o}\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{p}\mathrm{e}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{d}\mathrm{o}\mathrm{u}\mathrm{b}\mathrm{l}\mathrm{e}\mathrm{e}\mathrm{d}\mathrm{g}\mathrm{e}\mathrm{s}\mathrm{i}\mathrm{n}M\left[\overline{U}\right]\mathrm{i}\mathrm{s}\mathrm{m}\mathrm{a}\mathrm{x}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{z}\mathrm{e}\mathrm{d}.

Given (2), choose U_1,U_2,\dots ,U_{k-1}, and \overline{U} so that

(3)\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{l}\mathrm{o}\mathrm{n}\mathrm{g}\mathrm{e}\mathrm{s}\mathrm{t}\mathrm{d}\mathrm{o}\mathrm{u}\mathrm{b}\mathrm{l}\mathrm{e}-\mathrm{e}\mathrm{d}\mathrm{g}\mathrm{e}\mathrm{p}\mathrm{a}\mathrm{t}\mathrm{h}\mathrm{i}\mathrm{n}M\left[\overline{U}\right]\mathrm{i}\mathrm{s}\mathrm{m}\mathrm{a}\mathrm{x}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{z}\mathrm{e}\mathrm{d}.

Given (2) and (3), choose U_1,U_2,\dots ,U_{k-1}to maximize

(4){\sum }_{j=1}^{k-1}\Vert U_j\Vert .

Assertion 3.1　 M\left[\overline{U}\right] contains at least two independent double edges.

Proof　It first requires to prove that \Vert \overline{U}{\Vert }_H\ge 1. Otherwise, if M\left[\overline{U}\right] contains no double edges in H_M, then for \mathrm{\forall }x,y\in \overline{U} there is \Vert \{x,y\},\overline{U}\Vert \le 6. Thus,

\Vert \{x,y\},U\Vert \ge 2\left(6k-2\right)-6=12\left(k-1\right)+2.

This implies that there exists some j\in \{1,2,\dots ,k-1\} such that \Vert \{x,y\},U_j\Vert \ge 13. Hence, \Vert \{x,y\},U_j{\Vert }_H\ge 5. Applying Lemma 2.2 to H_M and U_j, it is concluded that H_M\left[\{x,y\}\cup V\left(U_j\right)\right] contains some U_j^{\prime }\supseteq Q_8^4 and a double edge e, where U_j^{\prime } and e are vertex-disjoint, and e is incident to exactly one vertex in {x, y}. By the choice criterion in (2), we obtain \Vert \overline{U}{\Vert }_H\ge 1. Let \overline{U}=\{x_1,x_2,x_3,x_4\}, where x₁x₂ is a double edge.

Now, it requires to prove that H\left[\overline{U}\right] contains at least two independent double edges. Assume instead that H\left[\overline{U}\right] contains only one independent double edge. For \mathrm{\forall }j\in \{1,2,\dots ,k-1\}, there is \Vert \{x_3,x_4\},U_j\Vert \le 12. Thus, \Vert \{x_3,x_4\},U\Vert \le 12(k-1), which leads to

(5)\Vert \{x_3,x_4\},\overline{U}\Vert \ge 2\left(6k-2\right)-12\left(k-1\right)=8.

This implies that \Vert \{x_3,x_4\},\{x_1,x_2\}{\Vert }_H\ge 2. By symmetry, assume that x₁x₃ is a double edge. If x₄x₂ is also a double edge, then x_3{x}_4\notin E. Otherwise M\left[\overline{U}\right]\supseteq Q_7^4, which contradicts the assumption that M\supseteq \left(k-1\right)Q_8^4\cup Q_7^4. By equation (5), it is known that x₄x₁, x₄x₂, and x₃x₂ are all double edges, which implies \mathrm{M}\left[\overline{U}\right]\supseteq Q_8^4, contradicting the assumption. Thus, x₄x₂ is not a double edge, and x_3{x}_4\in E. The two cases are considered as follows:

Case 1: x₂x₃ is not a double edge.

By Lemma 2.4, it is known that x₁x₄ is a double edge, while x₂x₃, x₃x₄, and x₂x₄ are single edges. k ≥ 2, otherwise M would be a 4-vertex graph and M\cong {\mathbb{F}}^{\mathbb{\ast }}, which completes the proof. Thus, \Vert \{x_2,x_3\},\overline{U}\Vert =8 and

(6)\Vert \{x_2,x_3\},U\Vert \ge 2\left(6k-2\right)-8=12\left(k-1\right).

If there exists some j\in \{1,2,\dots ,k-1\} such that \Vert \{x_2,x_3\},U_j\Vert \ge 13, then \Vert \{x_2,x_3\},U_j{\Vert }_H\ge 5. Applying Lemma 1.2 to H_M and U_j, it is concluded that H_M\left[\{x_2,x_3\}\cup V\left(U_j\right)\right] contains some U_j^{\prime }\supseteq Q_8^4 and a double edge e, where U_j^{\prime } and e are vertex-disjoint, and e is incident to exactly one vertex in {x₂ ,x₃}. Replacing U_j^{\prime } with U_j yields two independent double edges, contradicting (2). Thus, for every j\in \{1,2,\dots ,k-1\}, there must be \Vert \{x_2,x_3\},U_j\Vert =12 and \Vert \{x_2,x_3\},U_j{\Vert }_H=4. By the symmetry of x₂, x₃, x₄, it is known that for every \mathrm{j}\in \{1,2,\dots ,k-1\}, there are \Vert \{x_3,x_4\},U_j\Vert =12 and \Vert \{x_3,x_4\},U_j{\Vert }_H=4,\Vert \{x_2,x_4\},U_j\Vert =12, and \Vert \{x_2,x_4\},U_j{\Vert }_H=4. Thus, for every j\in \{1,2,\dots ,k-1\}, there are \Vert \{x_2,x_3,x_4\},U_j\Vert =18 and \Vert \{x_2,x_3,x_4\},U_j{\Vert }_H=6. So, for every j\in \left\{1,2,\dots ,k-1\right\}, and i\in \{2,3,4\}, there are \Vert \left\{x_i\right\}\},U_j\Vert =6 and \Vert \left\{x_i\right\},U_j{\Vert }_H=2. Choose an arbitrary U_j=u_1{u}_2{u}_3{u}_4{u}_1. Assume that for each \mathrm{i}=\left\{2,3,4\right\},\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{e}\mathrm{d}\mathrm{g}\mathrm{e}\mathrm{s}{u}_1{x}_i\mathrm{a}\mathrm{n}\mathrm{d}{u}_3{x}_i are double edges. If this assumption does not hold, then without losing generality, assume that the double-edge neighbors of x₃, x₄ are not the same. Applying Lemma 1.3 to x₃, x₄, the two cases are analyzed.

(a) If x₃u₁, x₃u₂, x₄u₃, and x₄u₄ are double edges, then since \Vert \left\{x_2\right\},U_j{\Vert }_H=2, by the symmetry of x₃ and x₄, assume x₂u₁ is a double edge. Thus, M\left[\{x_1,x_3,u_1,x_2\}\right]\supseteq Q_8^4, and u₂u₃ and x₄u₄ form two independent double edges, contradicting condition (2).

(b) If x₃u₁, x₃u₂, x₄u₂, and x₄u₃ are double edges, then by condition (2), choose x₂u₃ and x₂u₄ as double edges. Thus, M\left[\right\{x_1,x_4,u_3,x_2\left\}\right]\supseteq Q_8^4, and u₁u₄ and x₃u₂ form two independent double edges, contradicting condition (2).

If \Vert \left\{u_4\right\},\overline{U}-x_1\Vert \ge 4, then, by symmetry, assume u₄x₂ is a double edge. Thus, M\left[\{x_4,u_1,u_2,u_3\}\right]\supseteq Q_8^4, and u₄x₂ and x₁x₃ form two independent double edges, contradicting condition (2). Therefore, \Vert \left\{u_4\right\},\overline{U}-x_1\Vert \le 3, which implies \Vert \left\{u_4\right\},\overline{U}\Vert \le 5. Further, for each U_i\in U\mathrm{\setminus }{U}_j, let U_i=w_1{w}_2{w}_3{w}_4{w}_1. Assume that for each i=\{2,3,4\},w_1{x}_i{\mathrm{a}\mathrm{n}\mathrm{d}w}_3{x}_i are double edges. If u₄w₄ is a double edge, then M\left[\right\{x_2,u_1,u_2,u_3\left\}\right]\supseteq Q_8^4, and M\left[\right\{x_4,w_1,w_2,w_3\left\}\right]\supseteq Q_8^4. Here, x₃x₁ and u₄w₄ form two independent double edges, leading to a contradiction. Thus, u₄w₄ is not a double edge, and by symmetry, u₄w₂ is also not a double edge. Therefore, \Vert \left\{u_4\right\},U_l\Vert \le 6 and \Vert \left\{u_4\right\},V\left(U\right)-U_j\Vert \le 6\left(k-2\right). Thus,

\begin{array}{rl}6k-2\le d_M\left(u_4\right)& \le \Vert \left\{u_4\right\},U_j\Vert +\Vert \left\{u_4\right\},\overline{U}\Vert +\Vert \left\{u_4\right\},V\left(U\right)-U_j\Vert \\ & \le 5+5+6\left(k-2\right)\\ & =6k-2.\end{array}

Since the equality holds, for each U_l\in U\mathrm{\setminus }{U}_j, there are \Vert \{u_4\},U_j\Vert =5, \Vert \left\{u_4\right\},\overline{U}\Vert =5, and \Vert \left\{u_4\right\},U_l\Vert =6. Thus, x₁u₄ and x₁u₂ are double edges, and M\left[\{x_2,x_3,x_4,u_2,u_4\}\right]\cong K_5. For each U_l\in U\mathrm{\setminus }{U}_j, there exists a labeling U_l=z_1^l{z}_2^l{z}_3^l{z}_4^l{z}_1^l such that

(i) M\left[\{x_2,x_3,x_4,u_2,u_4,z_2^l,z_4^l\}\right]\cong K_7.

(ii) x_i{z}_1^l,x_i{z}_3^l are double edges for i\in \{2,3,4\}, l\in \{1,2,\dots ,k-1\}\setminus \left\{j\right\}.

(iii) u_2{z}_1^l,u_2{z}_3^l,u_4{z}_1^l,u_4{z}_3^l are all double edges for l\in \{1,2,\dots ,k-1\}\mathrm{\setminus }\left\{j\right\}.

Define the sets:

V\left(F_1\right)=\left\{x_2,x_3,x_4,u_2,u_4\right\}\cup \left({\bigcup }_{i=1,i\ne j}^{k-1} \left\{z_2^i,z_4^i\right\}\right),

and

V\left(F_2\right)=V\left(M\right)\mathrm{\setminus }V\left(F_1\right).

Then for \mathrm{\forall }x\in V\left(F_1\right)\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{\forall }y\in V\left(F_2\right), xy is a double edge in M. Thus, F_1\cong K_{2k+1}, which implies M\cong {\mathbb{F}}^{\mathbb{\ast }}.

Case 2: x₂x₃ is a double edge.

By Lemma 2.4, it is known that x₁x₄, x₂x₄, and x₃x₄ are single edges. Thus, \Vert \{x_2,x_4\},\overline{U}\Vert =8, and

\Vert \{x_2,x_4\},U\Vert \ge 2\left(6k-2\right)-8=12\left(k-1\right).

If there exists some j\in \{1,2,\dots ,k-1\} such that \Vert \{x_2,x_4\},U_j\Vert \ge 13. Then \Vert \{x_2,x_4\},U_j{\Vert }_H\ge 5. Applying Lemma 2.2 to Hm and U_j, it is concluded that H_M\left[\{x_2,x_4\}\cup V\left(U_j\right)\right]contains some U_j^{\prime }\supseteq Q_8^4 and a double edge e, where U_j^{\prime } and e are vertex-disjoint, and e is incident to exactly one vertex in {x₂, x₄}. Replacing U_j^{\prime } with U_j results in two independent double edges, which contradicts condition (2). Thus, for every j\in \{1,2,\dots ,k-1\}, there must be \Vert \left\{x_2,x_4\right\},U_j\Vert =12 and \Vert \{x_2,x_4\},U_j{\Vert }_H=4. By the symmetry of x₂, x₃, x₁, it is known that for every j\in \{1,2,\dots ,k-1\}, there are \Vert \{x_1,x_4\},U_j\Vert =12 and \Vert \{x_1,x_4\},U_j{\Vert }_H=4, \Vert \{x_3,x_4\},U_j\Vert =12 and \Vert \{x_3,x_4\},U_j{\Vert }_H=4. Let any double-edge quadrilateral in U be: U_j=u_1{u}_2{u}_3{u}_4{u}_1. \Vert x_i,u_j\Vert >0, i\in \{1,2,3\},j\in \{1,2,3,4\}.

(a) Assume that \Vert \left\{x_4\right\},U_j{\Vert }_H=1. Then \Vert \left\{x_i\right\},U_j{\Vert }_H=3, for i\in \{1,2,3\}. Without losing generality, assume that x₃u₁, x₃u₂, and x₃u₃ are double edges. If x₄u₁ is a double edge andi\in \{2,4\}, and let i = 2, then M\left[\right\{x_3,u_1,u_4,u_3\left\}\right]\supseteq Q_8^4, and x₁x₂ and x₄u₂ form two independent double edges, leading to a contradiction. Therefore, x₄u_i must be a single edge for i\in \{2,4\}. Now, assume that x₄u₁ is a double edge. Both {x₁, x₂} must be double-edge connected to {u₁, u₂, u₃}. Otherwise, at least one of {x₁, x₂} must be double-edge connected to u₄, which leads to one of the following contradictions: M\left[\right\{x_1,x_2,u_3,u_4\left\}\right]\supseteq Q_8^4, and x₄u₁ and x₃u₂ form two independent double edges, contradicting condition (2). Or, M\left[\{x_2,x_3,u_3,u_4\}\right]\supseteq Q_8^4 and x₄u₁ and x₁u₂ form two independent double edges, contradicting condition (2). Furthermore, x_1{x}_2{u}_2{x}_3{x}_1\supseteq Q_8^4, and x₄u₁ and u₃u₄ are double edges, which leads to another contradiction. If x₄u₃ is a double edge, then by a symmetric argument, there exists another contradiction.

(b) Assume that \Vert \left\{x_4\right\},U_j{\Vert }_H=2. Then, \Vert \left\{x_i\right\},U_j{\Vert }_H=2 for i\in \{1,2,3\}. Assume that x₄u₁ and x₄u₂ are double edges. If x₃u₁ and x₃u₂ are double edges, then x_3{u}_1{x}_4{u}_2{x}_3\supseteq Q_8^4, and x₁x₂ and u₃u₄ form two independent double edges, contradicting condition (2). If x₃u₁ and x₃u₃ are double edges, then x_3{u}_1{u}_4{u}_3{x}_3\supseteq Q_8^4, and x₄u₂ and x₁x₂ form two independent double edges, contradicting condition (2). Thus, it is assumed that x₄u₁ and x₄u₃ are double edges. If x₃u₁ and x₃u₂ are double edges, then x_4{u}_1{u}_4{u}_3{x}_4\supseteq Q_8^4, and x₃u₂ and x₁x₂ form two independent double edges, contradicting condition (2). Thus, it is assumed that x₃u₁ and x₃u₃ are double edges. By the symmetry of x₁,x₂,x₃, it is concluded that x_iu₁, x_iu₃ are double edges for i\in \{1,2\}. Otherwise, a subgraph containing Q_8^4 and two independent double edges would be formed, contradicting condition (2). Since M\left[\{x_1,x_2,x_3,u_1\}\right]\supseteq Q_8^4, by condition (2) it follows that u₂u₄ is a double edge. Thus, x_4{u}_1{x}_3{u}_3{x}_4\supseteq Q_8^4, and x₁x₂ and u₂u₄ form two independent double edges, leading to a contradiction.

(c) Assume that \Vert \left\{x_4\right\},U_j{\Vert }_H=3. Then, \Vert \left\{x_i\right\},U_j{\Vert }_H=1, for i\in \{1,2,3\}. Assume that x₄u₁, x₄u₂, and x₄u₃ are double edges. Thus, \Vert \{x_1,x_2,x_3\},\{u_2,u_4\}{\Vert }_H=0. Otherwise, a subgraph containing Q_8^4 and two independent double edges would be formed, contradicting the given conditions. Now, it requires to consider several cases where x₃u₁ is a double edge. If x₁u₁ is a double edge, then x_1{u}_1{x}_3{x}_2{x}_1\supseteq Q_8^4 and x₄u₂ and u₃u₄ form two independent double edges, contradicting the assumption. If x₁u₃ is a double edge, there are two subcases. If x₂u₁ is a double edge, then x_1{x}_2{u}_1{x}_3{x}_1\supseteq Q_8^4, and x₄u₂ and u₃u₄ form two independent double edges, leading to a contradiction. If x₂u₃ is a double edge, then u_3{x}_2{x}_3{x}_1{u}_3\supseteq Q_8^4 and x₄u₂ and u₁u₄ form two independent double edges, leading to a contradiction. If x₃u₃ is a double edge, then a similar argument leads to a contradiction. This implies that \Vert \left\{x_1\right\},U_j{\Vert }_H=0, which contradicts the assumption.

(d) Thus, for all U_j\in U, it is concluded that either \Vert \left\{x_4\right\},U_j{\Vert }_H=4 or \Vert \left\{x_4\right\},U_j{\Vert }_H=0. For every j\in \{1,2,\dots ,s\}, there is\Vert \left\{x_4\right\},U_j{\Vert }_H=4, and for every j\in \{s+1,\dots ,s+t\}, there is \Vert \left\{x_4\right\},U_j{\Vert }_H=0, where s+t=k-1. If s < t, then

d_M\left(x_4\right)=3+8s+4t=3+4\left(k-1\right)+4s\le 6k-3,

which contradicts the assumption that \delta \left(M\right)\ge 6k-2. Thus, s >t, which implies that 2t\le k-2, d_M(x_3)=5+4s+8t=5+4(k-1)+4t\le 5+4(k-1)+2(k-2)=6k-3, which leads to a contradiction. Thus, the proof is complete. □

Assertion 3.2　 \Vert \overline{U}\Vert =8.

Proof　It is proceeded by contradiction. Suppose that \Vert \overline{U}\Vert \ne 8. If \Vert \overline{U}\Vert \ge 9, by Assertion 3.1, it is known that M\left[\overline{U}\right] contains two independent double edges. Applying Lemma 1.4, we obtain M\left[\overline{U}\right]\supseteq Q_7^4. Since U contains \left(k-1\right)Q_8^4, it follows that M\supseteq \left(k-1\right)Q_8^4\cup Q_7^4, which contradicts the assumption. Therefore, for \Vert \overline{U}\Vert \le 7, there is

\Vert \overline{U},U\Vert \ge 4\left(6k-2\right)-14>24\left(k-1\right).

This implies that there exists some j\in \{1,2,\dots ,k-1\} such that \Vert \overline{U},U_j\Vert \ge 25. By Lemma 2.5, it follows that M\left[V\left(U_j\right)\cup \overline{U}\right]\supseteq Q_8^4\cup Q_7^4, which implies that M\supseteq \left(k-1\right)Q_8^4\cup Q_7^4and contradicts the assumption. Thus, the proof is complete. □

Let \overline{U}=\{x_1,x_2,y_1,y_2\}. By Assertion 3.1, it is assumed that x₁x₂ and y₁y₂ are double edges.

Assertion 3.3　 If M\left[\overline{U}\right] does not contain a double-edge path of order 4, then \Vert \left\{x_i\right\},U_l\Vert +\Vert \left\{y_j\right\},U_i\Vert \le 12, where i\in \left\{1,2\right\}, j\in \left\{1,2\right\}, and U_l\in U.

Proof　Since M\left[\overline{U}\right] does not contain a double-edge path of order 4, and by Assertion 3.2, it is known that x_iy_i is a single edge. Additionally, \left|\right\{x_i\},\overline{U}\Vert +\Vert \{y_j\},\overline{U}\Vert =8, for i\in \{1,2\}, j\in \{1,2\}. Thus,

\Vert \overline{U},U\Vert \ge 4\left(6k-2\right)-16=24\left(k-1\right).

By Lemma 2.5, for each U_l\in U, there is \Vert \overline{U},U_l\Vert \le 24. That is, for each U_l\in U, \Vert \overline{U},U_l\Vert =24.

Now, suppose that there exist i\in \{1,2\}, j\in \{1,2\} and U_l\in U such that \Vert \left\{x_i\right\},U_l\Vert +\Vert \left\{y_j\right\},U_l\Vert \ge 13. By symmetry, assume that i = j = 1 and let U_l=v_1{v}_2{v}_3{v}_4{v}_1, where v₁v₂, v₂v₃, v₃v₄, v₄v₁ are double edges. Now the three cases are considered as follows:

Case 1: \Vert \left\{x_1\right\},U_l\Vert +\Vert \left\{y_1\right\},U_l\Vert \ge 15.

By symmetry, assume that \Vert \left\{y_1\right\},U_l\Vert =8, \Vert \left\{x_1\right\},U_l\Vert \ge 7, and x₁v₁, x₁v₂, and x₁v₃ are double edges. If x₂v₄ is a double edge, then \mathrm{M}\left[\{x_1,v_1,v_2,v_3\}\right]\supseteq Q_8^4, and y₂y₁v₄x₂ forms a double-edge path of order 4, contradicting condition (2). Thus, x₂v₄ is not a double edge. By a similar argument, it is known that x₂v_i and y₂v_i are not double edges for i\in \{1,2,3,4\}. This implies that \Vert \{x_2,y_2\},U_l\Vert \le 8. Since \Vert \overline{U},U_l\Vert =24, it is concluded that \Vert \{x_2,y_2\},U_l\Vert =8 and \Vert \{x_1,y_1\},U_l\Vert =16. That is, \Vert \{x_2,y_2\},U_l{\Vert }_H=0 and \Vert \{x_1,y_1\},U_l{\Vert }_H=8. For k = 2, , which leads to a contradiction. For k ≥ 3, if \mathrm{\forall }{U}_j\in U\setminus U_l, \Vert \{x_2,y_2\},U_j\Vert \le 12, then

2\left(6k-2\right)=12k-4\le d_M\left(x_2\right)+d_M\left(y_2\right)\le 12\left(k-2\right)+8+8=12k-8,

leading to a contradiction. Thus, there exists U_j\in U\mathrm{\setminus }{U}_l such that \Vert \{x_2,y_2\},U_j\Vert \ge 13. This implies that either \Vert x_2,U_j\Vert \ge 7 or \Vert y_2,U_j\Vert \ge 7. Assume the former, i.e., \Vert x_2,U_j{\Vert }_H\ge 3, \Vert y_2,U_j{\Vert }_H\ge 1. Let U_j=s_1{s}_2{s}_3{s}_4{s}_1.

(a) If \Vert x_2,U_j\Vert =8, then \Vert y_2,U_j{\Vert }_H\ge 1. Without losing generality, assume that y₂s₄ is a double edge. Then, x_1{v}_1{v}_2{v}_3{x}_1\supseteq Q_8^4, x_2{s}_1{s}_2{s}_3{x}_2\supseteq Q_8^4, and s₄y₂y₁v₄ forms a double-edge path of order 4, leading to a contradiction.

(b) If \Vert x_2,U_j\Vert =7, then \Vert y_2,U_j{\Vert }_H\ge 2. Assume that x_2{s}_1,x_2{s}_2{\mathrm{a}\mathrm{n}\mathrm{d}x}_2{s}_3 are double edges. Then, y₂s_i is not a double edge for i\in \{2,4\}. Otherwise, x_1{v}_1{v}_2{v}_3{x}_1\supseteq Q_8^4, x_2{s}_1{s}_2{s}_3{x}_2\supseteq Q_8^4, and s₄y₂y₁v₄ forms a double-edge path of order 4, leading to a contradiction. Thus, y₂s₁ and y₂s₃ are double edges. Then, y_2{s}_1{s}_4{s}_3{y}_2\supseteq Q_8^4, y_1{v}_1{v}_2{v}_3{y}_1\supseteq Q_8^4, and s₂x₂x₁v₄ forms a double-edge path of order 4, leading to a contradiction.

Case 2: \Vert \left\{x_1\right\},U_l\Vert +\Vert \left\{y_1\right\},U_l\Vert =13.

By symmetry, assume that \Vert \left\{x_1\right\},U_l\Vert \ge \Vert \left\{y_1\right\},U_l\Vert. Thus, \Vert \left\{x_1\right\},U_l\Vert \ge 7, \Vert \left\{y_1\right\},U_l\Vert \ge 5.

(a) \Vert \left\{x_1\right\},U_l\Vert =8, \Vert \left\{y_1\right\},U_l\Vert =5. By symmetry, assume that y₁v₁ is a double edge. From the given assumption, it is known that x₂v_i is not a double edge for i\in \{2,3,4\} and y₂v₂, y₂v₄ are also not double edges. Since \Vert \left\{x_2\right\},U_l\Vert +\Vert \left\{y_2\right\},U_l\Vert =11, it follows that y₂v₁, y₂v₃, and x₂v₁ must be double edges. Thus, M\left[\{x_2,x_1,v_2,v_1\}\right]\supseteq Q_8^4 and y₁y₂v₃v₄ forms a double-edge path of order 4, leading to a contradiction.

(b) \Vert \left\{x_1\right\},U_l\Vert =7, \Vert \left\{y_1\right\},U_l\Vert =6. By symmetry, assume that x₁v₁, x₁v₂, and x₁v₃ are double edges. Since \Vert \left\{y_1\right\},U_l{\Vert }_H\ge 2, there are four possible cases by symmetry: If y₁v₁, y₁v₃ are double edges, then y₂v₂, y₂v₄ and x₂v_i must not be a double edge for i\in \{1,2,3,4\}. This contradicts \Vert \left\{x_2\right\},U_l\Vert +\Vert \left\{y_2\right\},U_l\Vert =11. If y₁v₁, y₁v₂ are double edges, then x₂v₂, x₂v₃, y₂v_i must not be a double edge for i\in \{1,2,3,4\}. This also contradicts \Vert \left\{x_2\right\},U_l\Vert +\Vert \left\{y_2\right\},U_l\Vert =11. If y₁v₂, y₁v₄ are double edges, then y₂v₃, y₂v₁, x₂v₁, x₂v₂, x₂v₃ must not be double edges. Thus, y₂v₂, y₂v₄, x₂v₄ must be double edges. Then, M\left[\{x_2,x_1,v_1,v_4\}\right]\supseteq Q_8^4 and y₁y₂v₂v₃ forms a double-edge path of order 4, leading to a contradiction. If y₁v₃, y₁v₄ are double edges, then, y₂v₂, y₂v₁, x₂v_i for i\in \{1,2,3,4\} must not be double edges. This contradicts \Vert \left\{x_2\right\},U_l\Vert +\Vert \left\{y_2\right\},U_l\Vert =11.

Case 3: \Vert \left\{x_1\right\},U_l\Vert +\Vert \left\{y_1\right\},U_l\Vert =14.

Then, \Vert \left\{x_2\right\},U_l\Vert +\Vert \left\{y_2\right\},U_l\Vert =10. By symmetry, assume that \Vert \left\{x_1\right\},U_l\Vert \ge \Vert \left\{y_1\right\},U_l\Vert. Thus, \Vert \left\{x_1\right\},U_l\Vert \ge 7, \Vert \left\{y_1\right\},U_l\Vert \ge 6. Let \Vert \left\{y_1\right\},U_l{\Vert }_H\ge 2.

(a) \Vert \left\{x_1\right\},U_l\Vert =7, \Vert \left\{y_1\right\},U_l\Vert =7. Assume that x₁v₁, x₁v₂, x₁v₃ are double edges. If y₁v₁, y₁v₂ are double edges, then x₂v₂, x₂v₄, x₂v₃ and y₂v₁, y₂v₂, y₂v₃, y₂v₄ are not double edges. Thus,\Vert \left\{x_2\right\},U_l\Vert +\Vert \left\{y_2\right\},U_l\Vert \le 9, which leads to a contradiction. This implies that either y₁v₁, y₁v₃, y₁v₄ or y₁v₂, y₁v₃, y₁v₄ are double edges. Assuming the former case holds, y₂v₃, y₂v₄, y₂v₂, x₂v₂, x₂v₄, x₂v₃ are not double edges, and y₂v₁, x₂v₁ are double edges. This leads to y_2{v}_1{v}_4{y}_1{y}_2\supseteq Q_8^4, and x₂x₁v₂v₃ forms a double-edge path with 4 vertices, leading to a contradiction. Similarly, if the latter case holds, same contradiction occurs.

(b) \Vert \left\{x_1\right\},U_l\Vert =8, \Vert \left\{y_1\right\},U_l\Vert =6. (i) If y₁v₁, y₁v₂ are double edges, then y₂v₁, y₂v₂, y₂v₃, y₂v₄, x₂v₁, x₂v₃, x₂v₄ are not double edges, which contradicts \Vert \left\{x_2\right\},U_l\Vert +\Vert \left\{y_2\right\},U_l\Vert =10. (ii) If y₁v₁, y₁v₃ are double edges, then, by the assumption, y₂v₂, y₂v₄ and x₂v₁, x₂v₂, x₂v₃, x₂v₄ are not double edges. Since \Vert \left\{x_2\right\},U_l\Vert +\Vert \left\{y_2\right\},U_l\Vert =10, both y₂v₁ and y₂v₃ must be double edges. By symmetry, assume for \mathrm{\forall }j\in \{1,2,\dots ,s\}, \Vert \left\{x_2\right\},U_j\Vert =4, and \mathrm{\forall }j\in \{s+1,s+2,\dots ,s+t\}, there are \Vert \left\{y_2\right\},U_j\Vert =4, s+t=k-1. If s ≤ t, then

d_M\left(y_2\right)=4+4t+6s=4+4\left(k-1\right)+2s\le 5k-1,

which contradicts \delta \left(M\right)\ge 6k-2. Therefore, s > t, and , leading to a contradiction. Thus, the proof is complete. □

Assertion 3.4　 If M\left[\overline{U}\right] does not contain a double-edge path of order 4, then one of the following must hold: \Vert \left\{x_i\right\},U_l{\Vert }_H=4 or \Vert \left\{x_i\right\},U_i{\Vert }_H=0, for i\in \{1,2\}.

Proof　Since M\left[\overline{U}\right] does not contain a double-edge path of order 4, by Assertion 3.2, it is known that x_iy_i is a single edge and \Vert \left\{x_i\right\},\overline{U}\Vert +\Vert \left\{y_j\right\},\overline{U}\Vert =8, for i\in \{1,2\}, j\in \{1,2\}. Thus, \Vert \left\{x_i\right\},U\Vert +\Vert \left\{y_j\right\},U\Vert \ge 2\left(6k-2\right)-8=12\left(k-1\right). By the assumptions and Assertion 3.3, \Vert \left\{x_i\right\},U\Vert +\Vert \left\{y_j\right\},U\Vert \le 12\left(k-1\right). Thus, for every U_l\in U, \Vert \left\{x_i\right\},U_l\Vert +\Vert \left\{y_j\right\},U_l\Vert =12.

Proof by contradiction. \Vert \left\{x_i\right\},U_l\Vert +\Vert \left\{y_j\right\},U_i\Vert =12. Without losing generality, let i = j = 1 and assume that such a U_l\in U exists such that \Vert \left\{x_1\right\},U_l{\Vert }_H\ge 1 and \Vert \left\{y_1\right\},U_l{\Vert }_H\ge 1. Let U_l=v_1{v}_2{v}_3{v}_4{v}_1 and assume x₁v₁ is a double edge. By assumption, there are \Vert \left\{x_1\right\},U_l\Vert \le 7 and \Vert \left\{y_1\right\},U_l\Vert \le 7.

Case 1: Assume \Vert \left\{x_1\right\},U_l\Vert =7. Since \Vert \left\{x_1\right\},U_l\Vert +\Vert \left\{y_1\right\},U_l\Vert =12, it follows that \Vert \left\{x_1\right\},U_l\Vert =\Vert \left\{x_2\right\},U_l\Vert =7 and \Vert \left\{y_1\right\},U_l\Vert =\Vert \left\{y_2\right\},U_l\Vert =5. Without losing generality, assume x₁v₁, x₁v₂, x₁v₃ are double edges, then x₂v₁, x₂v₂, x₂v₃ must also be double edges. Otherwise, \Vert \{y_1,y_2\},U_l{\Vert }_H=0, which leads to a contradiction. Since M\left[\right\{x_1,x_2,v_1,v_2\left\}\right]\supseteq Q_8^4 and M\left[\right\{x_1,x_2,v_2,v_3\left\}\right]\supseteq Q_8^4, it follows that \Vert \{y_1,y_2\},\{v_3,v_4\}{\Vert }_H=0, and \Vert \{y_1,y_2\},\left\{v_1\right\}{\Vert }_H=0. Thus, y₁v₂, y₂v₂ are double edges, which implies that M\left[\right\{x_2,v_1,v_4,v_3\left\}\right]\supseteq Q_8^4, x₁v₂y₁y₂ forms a double-edge path of order 4 with 4 vertices, leading to a contradiction.

Case 2: From Case 1, it is known that \Vert \left\{x_1\right\},U_l\Vert \le 6 and \Vert \left\{y_1\right\},U_l\Vert \le 6, which implies \Vert \left\{x_1\right\},U_l\Vert =\Vert \left\{y_1\right\},U_l\Vert =6 and \Vert \left\{x_2\right\},U_l\Vert =\Vert \left\{y_2\right\},U_l\Vert =6. Thus, \Vert \left\{x_i\right\},U_l{\Vert }_H=2 and \Vert \left\{y_i\right\},U_l{\Vert }_H=2,i\in \{1,2\}. Otherwise, M\left[U_l\cup \overline{U}\right] would contain Q_8^4 and a double-edge path of order 4. Since\Vert \left\{x_1\right\},U_i\Vert =\Vert \left\{y_1\right\},U_l\Vert =6 and \Vert \left\{x_1\right\},U_l{\Vert }_H=\Vert \left\{y_1\right\},U_l{\Vert }_H=2, the following cases are considered:

(a) If x₁v₁, x₁v₂, y₁v₃, y₁v₄ or x₁v₁, x₁v₃, y₁v₂, y₁v₄ are double edges, without losing generality, assume the first case holds. According to the assumption, y₂v₂, y₂v₁, x₂v₃, x₂v₂ are not double edges. Then y₂v₃, y₂v₄, x₂v₁, x₂v₄ are double edges, and there is x_1{x}_2{v}_4{v}_1{x}_1\supseteq Q_8^4. y₂y₁v₃v₂ forms a double-edge path of order 4, which leads to a contradiction.

(b) If x₁v₁, x₁v₂, y₁v₂, y₁v₃ or x₁v₁, x₁v₂, y₁v₁, y₁v₃ or xιv₁, x₁v₃, y₁v₃, y₁v₄ are double edges, assume the first case holds. According to the assumption, x₂v₄, x₂v₂, y₂v₂, y₂v₄ are not double edges. Then, x₂v₁, x₂v₃, y₂v₁, y₂v₃ are double edges, and there is x_1{x}_2{v}_3{v}_2{x}_1\supseteq Q_8^4. y₁y₂v₁v₄ forms a double-edge path with 4 vertices, leading to a contradiction.

(c) x₁v₁, x₁v₃, y₁v₁, y₁v₃ or x₁v₁, x₁v₂, y₁v₁, y₁v₂ are double edges, assume the first case holds. According to the assumption, x₂v₄, x₂v₂, y₂v₄, y₂v₂ are not double edges, indicating that x₂v₁, x₂v₃, y₂v₁, y₂v₃ are double edges. That is, \Vert \overline{U},\{v_1,v_3\}{\Vert }_H=8 and {v₂, v₄}is connected to \overline{U} by single edges. This connection structure is called Structure 1. If the second case holds, according to the assumption, x₂v₃, x₂v₄, y₂v₃, y₂v₄ are not double edges, then x₂v₁,x₂v₂,y₂v₁,y₂v₂ are double edges. That is, \Vert \overline{U},\{v_1,v_2\}{\Vert }_H=8 and {v₃, v₄} is connected to \overline{U} by single edges. This connection structure is called Structure 2.

(i) \mathrm{\forall }{U}_l\in U, where l\in \{1,2,\dots ,k-1\}, the connection between \overline{U} and U follows Structure 1. When k = 2,

6\times 2-2\le d_M\left(v_4\right)=d_M\left(v_2\right)\le \Vert \left\{v_4\right\},\overline{U}\Vert +\Vert \left\{v_4\right\},U_l\Vert \le 4+\Vert \left\{v_4\right\},U_l\Vert ,

which leads to \Vert \left\{v_2\right\},U_l\Vert =\Vert \left\{v_4\right\},U_l\Vert \ge 6and implies that v₄v₂ is a double edge. Therefore, x₁x₂, y₁y₂, v₂v₄ are three K_2^{\ast } (complete bipartite graphs), and the four vertices between any two double edges are single-edge connected. Thus, M\left[\left\{x_1,x_2,y_1,y_2,v_2,v_4\right\}\right]\cong B_1, V\left(B_2\right)=\left\{v_1,v_3\right\}, and each vertex in B₁ is double-edge connected to each vertex in B₂. In this case, \delta \left(B_2\right)>0>2k-6, so M\cong {\mathbb{B}}^{\mathbb{\ast }}.

When k ≥ 3, there exists U_j\in U, where U_j=v_1{v}_2{v}_3{v}_4{v}_1, such that \overline{U} and U_j are double-edge connected at two diagonally opposite vertices. Without losing generality, assume these vertices are {v₁, v₃}. Then,

6k-2\le d_M\left(v_2\right)=d_M\left(v_4\right)\le 4+\Vert \left\{v_2\right\},U\Vert ,

which leads to \Vert \left\{v_2\right\},U\Vert \ge 6k-6=6\left(k-1\right). Now assume there exists U_i\in U, i\in \{1,2,\dots ,k-1\}, such that 4\le \Vert \left\{v_2\right\},U_i\Vert \le 5. Assume U_i=U_j.

1) If \Vert \left\{v_2\right\},U_j\Vert =4, from \Vert \left\{v_2\right\},U\Vert \ge 6\left(k-1\right), it is known there exists U_w\in U, where w\in \{1,2,\dots ,k-1\}\setminus \left\{j\right\}, such that \Vert \left\{v_2\right\},U_w\Vert \ge 8, i.e., \Vert \left\{v_2\right\},U_w{\Vert }_H=4. Let U_w=w_1{w}_2{w}_3{w}_4{w}_1 and \Vert \overline{U},\{w_1,w_3\}{\Vert }_H=8. Then, x_1{v}_1{v}_4{v}_3{x}_1\supseteq Q_8^4, v_2{w}_2{w}_1{w}_4{v}_2\supseteq Q_8^4, x_2{y}_1{y}_2{w}_3{x}_2\supseteq Q_7^4, which leads to a contradiction.

2) \Vert \left\{v_2\right\},U_j\Vert =5. There exists U_w\in U, where w\in \{1,2,\dots ,k-1\}\setminus \left\{j\right\} and U_w=w_1{w}_2{w}_3{w}_4{w}_1. Assume \Vert \overline{U},\{w_1,w_3\}{\Vert }_H=8. From 1), it is known that w₂w₄ is either a single-edge or a double-edge. Based on \Vert \left\{v_2\right\},U\Vert \ge 6\left(k-1\right), it is shown that there must exist U_i\in U, where i\in \{1,2,\dots ,k-1\}, such that w₂w₄ is a double-edge. Assume that U_w is one such case. Since \Vert \left\{v_2\right\},U_j\Vert =5, there is \Vert \left\{v_2\right\},U_w\Vert \ge 7, implying that v₂ is double-edge connected to at least three vertices in U_w. Let these vertices be w₁,w₂,w₃. Then, x_1{v}_1{v}_4{v}_3{x}_1\supseteq Q_8^4, v_2{w}_2{w}_4{w}_3{v}_2\supseteq Q_8^4, x_2{y}_1{y}_2{w}_1{x}_2\supseteq Q_7^4, which leads to a contradiction.

In summary, for \mathrm{\forall }{U}_i\in U, where i\in \{1,2,\dots ,k-1\}, there is \Vert \left\{v_2\right\},U_i\Vert \ge 6. That is, v₂v₄ is a double-edge. Similarly, w₂w₄ is also a double-edge. Since x_1{v}_1{x}_2{v}_3{x}_1\supseteq Q_8^4, y_1{w}_1{y}_2{w}_3{y}_1\supseteq Q_8^4, it follows that \Vert \{v_2,v_4\},\{w_2,w_4\}{\Vert }_H=0. Otherwise, v₂v₄w₂w₄ would form a double-edge path with 4 vertices. Since \Vert \left\{v_2\right\},U_i\Vert \ge 6, v₂w₁, v₂w₃, v₄w₁, v₄w₃ are double-edges, and v₂w₂, v₂w₄, v₄w₂, v₄w₄ are single-edges. Similarly, w₂v₁, w₂v₃, w₄v₁, w₄v₃ are double-edges, and w₂v₂, w₂v₄, w₄v₁, w₄v₃ are single-edges. Thus, for each U_l\in U, define U_l=q_1^l{q}_2^l{q}_3^l{q}_4^l{q}_1^l, and there are:

(1) {x_{1}x}_2,y_1{y}_2,q_2^l{q}_4^l form k+1 K_2^{\ast } graphs, and the four vertices of any two K_2^{\ast } graphs are single-edge connected, where l\in \{1,2,\dots ,k-1\};

(2) \Vert \overline{U},\{q_1^l,q_3^l\}{\Vert }_H=8, where l\in \{1,2,\dots ,k-1\};

(3) \Vert \left\{q_2^l\right\},\{q_1^l,q_3^l\}{\Vert }_H=\Vert \left\{q_4^l\right\},\{q_1^l,q_3^l\}{\Vert }_H=2, and q_2^i{q}_2^l,q_2^l{q}_4^l,q_4^l{q}_2^l,q_4^i{q}_4^l are single-edges, where l\in \{1,2,\dots ,k-1\}, i\in \{1,2,\dots ,k-1\}, i\ne l.

Define the set

V\left(B_1\right)=\{x_1,x_2,y_1,y_2\}\cup \left(\underset{i=1}{\bigcup ^{k-1}}\{q_2^i,q_4^i\}\right),

and

V\left(B_2\right)=\underset{i=1}{\bigcup ^{k-1}}\{q_1^i,q_3^i\}.

For each x\in V\left(B_1\right) and y\in V\left(B_2\right), xy is a double-edge in M, and \delta \left(B_2\right)=d_M\left(q_1^l\right)\ge 8+4(k-1)=4k+4>2k-6. Therefore, M\cong {\mathbb{B}}^{\mathbb{\ast }}.

(ii) For \mathrm{\forall }{U}_l\in U, where l\in \{1,2,\dots ,k-1\}, the connection between \overline{U} and U is of structure 2. When k = 2,

6\times 2-2\le d_M\left(v_4\right)=d_M\left(v_3\right)\le \Vert \left\{v_3\right\},\overline{U}\Vert +\Vert \left\{v_3\right\},U_l\Vert \le 4+\Vert \left\{v_3\right\},U_l\Vert .

We obtain \Vert \left\{v_4\right\},U_l\Vert =\Vert \left\{v_3\right\},U_l\Vert \ge 6, implying that v₃v₁, and v₄v₂ are double-edges. Then, x₁x₂, y₁y₂, v₃v₄ are three K_2^{\ast } graphs, and the four vertices of any two double-edges are single-edge connected. Thus, M\left[\right\{x_1,x_2,y_1,y_2,v_3,v_4\left\}\right]\cong B_1, V\left(B_2\right)=\{v_1,v_2\}, and every vertex in B₁ is double-edge connected to every vertex in B₂. Therefore, \delta \left(B_2\right)>0>2k-6, implying M\cong {\mathbb{B}}^{\mathbb{\ast }}.

When k ≥ 3, there exists U_j\in U, where U_j=v_1{v}_2{v}_3{v}_4{v}_1, such that \overline{U} and the two diagonal vertices in U_j are associated with a multiple edge. Assume these two vertices are {v₁, v₂}, then

6k-2\le d_M\left(v_3\right)=d_M\left(v_4\right)\le 4+\Vert \left\{v_3\right\},U\Vert .

This implies: \Vert \left\{v_3\right\},U\Vert \ge 6k-6=6\left(k-1\right). Assume there exists U_i\in U, i\in \{1,2,\dots ,k-1\}, such that 4\le \Vert \left\{v_3\right\},U_i\Vert \le 5. Assume U_i=U_j.

1. \Vert \left\{v_3\right\},U_j\Vert =4. Then there exists U_w\in U, w\in \{1,2,\dots ,k-1\}\setminus \left\{j\right\}, such that \Vert \left\{v_3\right\},U_w{\Vert }_H=4. Let U_w=w_1{w}_2{w}_3{w}_4{w}_1 and \Vert \overline{U},\{w_1,w_2\}{\Vert }_H=8. Then, x_1{x}_2{v}_1{v}_2{x}_1\supseteq Q_8^4, y_1{y}_2{w}_1{w}_2{y}_1\supseteq Q_8^4, and the path v₄v₃w₄w₃ is a multiple edge path of order 4, leading to a contradiction.

2. \Vert \left\{v_3\right\},U_j\Vert =5. It is seen that there exists U_w\in U, where w\in \{1,2,\dots ,k-1\}\setminus \left\{j\right\}, U_w=w_1{w}_2{w}_3{w}_4{w}_1, such that \Vert \overline{U},\{w_1,w_2\}{\Vert }_H=8. Since \Vert \left\{v_3\right\},U_j\Vert =5, there is \Vert \left\{v_3\right\},U_w\Vert \ge 7. That is, v₃ is associated with at least three multiple edges in U_w, which we can assume to be w₁, w₂, w₃. Then, x_1{x}_2{v}_1{v}_2{x}_1\supseteq Q_8^4, y_1{y}_2{w}_1{w}_2{y}_1\supseteq Q_8^4, and the path v₄v₃w₃w₄ is a multiple edge path of order 4, leading to a contradiction.

In summary, for \mathrm{\forall }{U}_i\in U, where i\in \{1,2,\dots ,k-1\}, and there is \Vert \left\{v_3\right\},U_i\Vert =\Vert \left\{v_4\right\},U_i\Vert \ge 6. That is, v₃v₁, v₂v₄ are multiple edges. Similarly, w₁w₃, w₂w₄ are multiple edges. Since x_1{x}_2{v}_1{v}_2{x}_1\supseteq Q_8^4, y_1{y}_2{w}_1{w}_2{y}_1\supseteq Q_8^4, there is \Vert \{v_3,v_4\},\{w_3,w_4\}{\Vert }_H=0. Otherwise v₃v₄w₃w₄ would form a multiple edge path of 4 vertices. Since \Vert \left\{v_3\right\},U_i\Vert \ge 6, it follows that v₃w₁, v₃w₂, v₄w₁, v₄w₂ are multiple edges, while v₃w₃, v₃w₄, v₄w₃, v₄w₄ are single edges. Similarly, w₃v₁, w₃v₂, w₄v₁, w₄v₂ are multiple edges, and w₃v₃, w₃v₄, w₄v₃, w₄v₄ are single edges. In summary, for each U_l\in U, define U_l=q_1^l{q}_2^l{q}_3^l{q}_4^l{q}_1^l, and the following shows the details:

(1) x_1{x}_2,y_1{y}_2,q_3^l{q}_4^l form k+1 K_2^{\ast }'s, and any two K_2^{\ast }'s have four vertices that are associated by single edges, \mathrm{l}\in \left\{1,2,\dots ,k-1\right\};

(2) \Vert \overline{U},\{q_1^l,q_2^l\}{\Vert }_H=8,l\in \left\{1,2,\dots ,k-1\right\};

(3) \Vert \left\{q_3^l\right\},\{q_1^l,q_2^l\}{\Vert }_H=\Vert \left\{q_4^l\right\},\{q_1^l,q_2^l\}{\Vert }_H=2, and q_3^i{q}_3^l,q_3^l{q}_4^l,q_4^l{q}_3^l,q_4^i{q}_4^l are single edges, l\in \left\{1,2,\dots ,k-1\right\}, i\in \left\{1,2,\dots ,k-1\right\}, i\ne l.

Let the set be

V\left(B_1\right)=\{x_1,x_2,y_1,y_2\}\cup \left(\bigcup _{i=1}^{k-1} \{q_3^i,q_4^i\}\right),

and

V\left(B_2\right)=\underset{i=1}{\bigcup ^{k-1}}\{q_1^i,q_2^i\}.

Then, for each x\in V\left(B_1\right) and y\in V\left(B_2\right), xy is a multiple edge in M and \delta \left(B_2\right)=d_M\left(q_1^l\right)\ge 8+6+4(k-2)=4k+6>2k-6, which implies M\cong {\mathbb{B}}^{\mathbb{\ast }}.

(iii) Let \mathrm{\forall }{U}_j\in U, where j\in \{1,2,\dots ,s\}, the connection between \overline{U} and U is Structure 1. Let \mathrm{\forall }{U}_i\in U, where i\in \{s+1,s+2,\dots ,k-1\}, the connection between \overline{U} and U is Structure 2. From (i) and (ii), it is known that when k = 2, M\cong B^{\ast }. When k ≥ 3, let U_j=v_1{v}_2{v}_3{v}_4{v}_1, where j\in \{1,2,\dots ,s\}, and U_i=w_1{w}_2{w}_3{w}_4{w}_1, where i\in \{s+1,s+2,\dots ,k-1\}. Then, v₂v₄,w₁w₃,w₂w₄ are multiple edges. Since x_1{v}_1{x}_2{v}_3{x}_1\supseteq Q_8^4, y_1{y}_2{w}_1{w}_2{y}_1\supseteq Q_8^4, it is concluded that \Vert \{v_2,v_4\},\{w_3,w_4\}{\Vert }_H=0. Otherwise, v₂v₄w₃w₄ would form a multiple edge path of order 4. Therefore, v₂w₁,v₂w₂,v₄w₁, v₄w₂ and w₃v₁,w₃v₃, w₄v₁,w₄v₃ are multiple edges, while v₂w₃, v₂w₄, v₄w₃, v₄w₄, and w₃v₂, w₃v₄, w₄v₂,w₄v₄ are single edges.

Let \mathrm{\forall }{U}_j\in U, where j\in \{1,2,\dots ,s\}, U_j=p_1^j{p}_2^j{p}_3^j{p}_4^j{p}_1^j and \mathrm{\forall }{U}_i\in U, where i\in \{s+1,s+2,\dots ,k-1\}, U_i=q_1^i{q}_2^i{q}_3^i{q}_4^i{q}_1^i. Then

(1) x_1{x}_2,y_1{y}_2,p_2^j{p}_4^j,q_3^i{q}_4^i form k + 1 K_2^{\ast }'s, and the four vertices of any two K_2^{\ast }'s are connected by single edges, where j\in \{1,2,\dots ,s\}, i\in \{s+1,s+2,\dots ,k-1\}；

(2) \Vert \overline{U},\{p_1^j,p_3^j\}{\Vert }_H=8, \Vert \overline{U},\{q_1^i,q_2^j\}{\Vert }_H=8, where j\in \{1,2,\dots ,s\} and i\in \{s+1,s+2,\dots ,k-1\}；

(3) \Vert \{p_2^j\},\{q_1^i,q_2^i\}{\Vert }_H=\Vert \{p_4^j\},\{q_1^i,q_2^i\}{\Vert }_H=\Vert \{p_2^j\},\{p_1^i,p_3^i\}{\Vert }_H=\Vert \{p_4^j\},\{p_1^j,p_3^j\}{\Vert }_H=2, \Vert \{q_3^i\},\{q_1^i,q_2^i\}{\Vert }_H=\Vert \{q_4^i\},\{q_1^i,q_2^i\}{\Vert }_H=\Vert \{q_3^i\},\{p_1^i,p_3^i\}{\Vert }_H=\Vert \{q_4^i\},\{p_1^j,p_3^j\}{\Vert }_H=2, and p_2^j{q}_3^i,p_2^j{q}_4^i,p_4^j{q}_3^i,p_4^j{q}_4^i,p_2^j{p}_1^j,p_2^j{p}_3^j,p_4^j{p}_1^j,p_4^j{p}_3^j and q_3^i{p}_2^j,q_3^i{p}_4^j,q_4^i{p}_2^j,q_4^i{p}_4^j,q_3^i{q}_1^i,q_3^i{q}_2^i,q_4^i{q}_1^i,q_4^i{q}_2^i are single edges, where j\in \{1,2,\dots ,s\} and i\in \{s+1,s+2,\dots ,k-1\}.

Thus, there are

V\left(B_1\right)=\{x_1,x_2,y_1,y_2\}\cup \left(\bigcup _{j=1}^s \{p_2^j,p_4^j\}\right)\cup \left(\bigcup _{i=s+1}^{k-1} \{q_3^i,q_4^i\}\right),

and

184V\left(B_2\right)=\left(\bigcup _{j=1}^s \{p_1^j,p_3^j\}\right)\cup \left(\bigcup _{i=s+1}^{k-1} \{q_1^i,q_2^i\}\right).

Then, for each x\in V\left(B_1\right) and y\in V\left(B_2\right), xy is a multiple edge in M, and when s = k − 1, it corresponds to case (i), and when s =0, it corresponds to case (ii). Therefore, there is \delta \left(B_2\right)>2k-6, which implies M\cong {\mathbb{B}}^{\mathbb{\ast }}. □

Assertion 3.5　 M\left[\overline{U}\right] contains a multiple edge path of order 4.

Proof　It is proceeded by contradiction. Assume that M\left[\overline{U}\right] does not contain a multiple edge path of order 4. From Assertion 3.4, there is either \Vert \left\{x_i\right\},U_l{\Vert }_H=4 or \Vert \left\{x_i\right\},U_l{\Vert }_H=0, where i\in \{1,2\},U_l\in U. According to Assertions 3.2 and 3.3, x_iy_j is a single edge, and \Vert \left\{x_i\right\},U_l\Vert +\Vert \left\{y_j\right\},U_l\Vert =12,U_l\in U. Suppose there exist some U_l\in U such that \Vert \left\{x_i\right\},U_l{\Vert }_H=0, then x_iz is a single edge for any z\in V\left(U_l\right). Assume \Vert \left\{x_1\right\},U_j{\Vert }_H=0,j\in \{1,2,\dots ,s\} and \Vert \left\{x_1\right\},U_j{\Vert }_H=4, j\in \{s+1,s+2,\dots ,k-1\}. For each U_j\in U, there are \Vert \left\{x_2\right\},U_l{\Vert }_H=\Vert \left\{x_1\right\},U_l{\Vert }_H and \Vert \left\{y_2\right\},U_l{\Vert }_H=\Vert \left\{y_1\right\},U_l{\Vert }_H. Thus,

6k-2\le d_M\left(x_1\right)=4+4s+8\left(k-s-1\right)=8k-4s-4,

6k-2\le d_M\left(y_1\right)=4+8s+4(k-s-1)=4k+4s.

Solving for s, we obtain s=\frac{k-1}{2}, which implies that k is odd. Define H_1={\cup }_{i=1}^s{U}_i and H_2={\cup }_{i=s+1}^{k-1}{U}_i. For each U_l\in H_1, there are\Vert \left\{y_2\right\},U_l{\Vert }_H=\Vert \left\{y_1\right\},U_l{\Vert }_H=4. For every U_l\in H_2, there are \Vert \left\{y_2\right\},U_l{\Vert }_H=\Vert \left\{y_1\right\},U_l{\Vert }_H=0. Choose any U_i\in H_1 and U_j\in H_2, where U_i=u_1{u}_2{u}_3{u}_4{u}_1 and U_j=v_1{v}_2{v}_3{v}_4{v}_1. Assume \Vert U_i,U_j{\Vert }_H>0. Without losing generality, suppose u₄v₄ is a multiple edge. Then the following contradictions are obtained: M\left[\right\{x_1,u_1,u_4,v_4\left\}\right]\supseteq Q_7^4, M\left[\right\{y_1,y_2,u_2,u_3\left\}\right]\supseteq Q_8^4, M\left[\right\{x_2,v_1,v_2,v_3\left\}\right]\supseteq Q_8^4. Thus, for \mathrm{\forall }{U}_i\in H_1, U_j\in H_2, there is \Vert U_i,U_j{\Vert }_H=0. For \mathrm{\forall }z\in V\left(H_1\right), since 2s = k – 1, there is

(8)\begin{array}{rl}\Vert \left\{z\right\},H_2\Vert & \ge d_M\left(z\right)-\Vert \left\{z\right\},\overline{U}\Vert -\Vert \left\{z\right\},H_1\Vert \\ & \ge 6k-2-6-\left(8s-2\right)\\ & =2\left(k-1\right)\\ & =4\left(k-1-s\right).\end{array}

Since \mathrm{\forall }{U}_i\in H_1, U_j\in H_2, there is \Vert U_i,U_j{\Vert }_H=0, it follows that \Vert \left\{z\right\},H_2\Vert \le 4\left(k-1-s\right). Thus, equality always holds in equation (8). Define: H_1^{\prime }=H_1\cup \{y_1,y_2\} and H_2^{\prime }=H_2\cup \left\{x_1,x_2\right\}. Then, M\left[V\right(H_1^{\prime }\left)\right]\cong K_{2k}^{\ast }, M\left[V\right(H_2^{\prime }\left)\right]\cong K_{2k}^{\ast }. Thus, it is concluded: M\cong {\mathbb{D}}^{\mathbb{\ast }}. □

According to Assertion 3.5, it is assumed that P=x_1{x}_2{y}_1{y}_2 is a multiple edge path of order 4 in M\left[\overline{U}\right]. Since M⊉(k-1)Q_8^4\cup Q_7^4, it follows that x_1{y}_2\notin E. Based on this assumption and Lemma 2.5, for \mathrm{\forall }{U}_j\in U, \Vert V\left(P\right),U_j\Vert \le 24. Meanwhile,

\Vert V\left(P\right),U\Vert \ge 4\left(6k-2\right)-16=24\left(k-1\right).

Thus, for \mathrm{\forall }{U}_j\in U, \Vert V\left(P\right),U_j\Vert =24 and \Vert V\left(P\right),U_j{\Vert }_H\ge 24-16=8.

Assertion 3.6　 For \mathrm{\forall }{U}_l\in U, we have \Vert V\left(P\right),U_l{\Vert }_H\ge 9.

Proof　It is proceeded by contradiction. Suppose there exists U_j\in U such that \Vert V\left(P\right),U_j{\Vert }_H=8. Let U_j=u_1{u}_2{u}_3{u}_4{u}_1. Since \Vert V\left(P\right),U_j\Vert =24, there is either \Vert \{x_1,x_2\},U_j\Vert \ge 12 or \Vert \{y_1,y_2\},U_j\Vert \ge 12. Without losing generality, it is assumed the former holds. Moreover, it is assumed \Vert \{x_1,x_2\},\{u_3,u_4\}\Vert \ge 6.

Case 1: \Vert \{x_1,x_2\},\{u_3,u_4\}\Vert \ge 7. Then, x_1{x}_2{u}_3{u}_4{x}_1\supseteq Q_8^4, which implies \Vert \{y_1,y_2\},\{u_1,u_2\}\Vert \le 4. Since \Vert \overline{U},U_j{\Vert }_H=8 and \Vert \overline{U},U_j\Vert =24, it follows that every vertex in \overline{U} is adjacent to every vertex in U_j. Hence, \Vert \{y_1,y_2\},\{u_1,u_2\}{\Vert }_H=0.

(a) If M\left[\{x_1,x_2,u_1,u_2\}\right]\supseteq Q_8^4, then \Vert \{y_1,y_2\},\{u_3,u_4\}\Vert \le 4. This leads to \Vert \{y_1,y_2\},U_j\Vert \le 8, and consequently \Vert \{x_1,x_2\},U_j\Vert \ge 16. It follows that \Vert \{y_1,y_2\},\{u_1,u_2\}\Vert =\Vert \{y_1,y_2\},\{u_3,u_4\}\Vert =4, and \Vert \{x_1,x_2\},U_j{\Vert }_H=8. As a result, we obtain x_1{u}_1{u}_2{u}_3{x}_1\supseteq Q_8^4 and x_2{y}_1{y}_2{u}_4{x}_2\supseteq Q_7^4, leading to a contradiction.

(b) If M\left[\{x_1,x_2,u_1,u_2\}\right]⊉Q_8^4, then \Vert \{x_1,x_2\},\{u_1,u_2\}{\Vert }_H\le 2. The two cases are analyzed as follows:

(i) When \Vert \{x_1,x_2\},\{u_3,u_4\}\Vert =8, there is \Vert \{x_1,x_2\},\{u_3,u_4\}{\Vert }_H=4. Since \Vert \overline{U},U_j{\Vert }_H=8,\Vert \{y_1,y_2\}\{u_1,u_2\}{\Vert }_H=0, it follows that \Vert \{y_1,y_2\},\{u_3,u_4\}{\Vert }_H\ge 2. Thus, y₂u₄ is not a multiple edge. Otherwise, there would be x_2{y}_1{y}_2{u}_4{x}_2\supseteq Q_8^4 and x_1{u}_3{u}_2{u}_1{x}_1\supseteq Q_7^4, leading to a contradiction. Similarly, y₂u₃ is not a multiple edge. Consequently, \Vert \{y_1,y_2\},\{u_3,u_4\}{\Vert }_H=2, and \Vert \{x_1,x_2\},\{u_1,u_2\}{\Vert }_H=2, implying that y₁u₃, y₁u₄ are multiple edges. If x₁u₁ is a multiple edge, then there are x_1{u}_1{u}_4{x}_2{x}_1\supseteq Q_8^4, y_2{y}_1{u}_3{u}_2{y}_2\supseteq Q_7^4, leading to a contradiction. Similarly, it is deduced that x₂u₁ is not a multiple edge. This implies that x₁u₂, x₂u₂ are multiple edges, which results in x_1{x}_2{u}_2{u}_3{x}_1\supseteq Q_8^4 and y_2{y}_1{u}_4{u}_1{y}_2\supseteq Q_7^4, leading to a contradiction.

(ii) When \Vert \{x_1,x_2\},\{u_3,u_4\}\Vert =7, there is \Vert \{x_1,x_2\},\{u_3,u_4\}{\Vert }_H=3,\Vert \{y_1,y_2\},\{u_3,u_4\}{\Vert }_H\ge 3.

(1) If x₁u₃, x₁u₄, x₂u₃ are multiple edges, then y₂u₃ is not a multiple edge. Otherwise, there would be x_2{y}_1{y}_2{u}_3{x}_2\supseteq Q_8^4 and x_1{u}_4{u}_1{u}_2{x}_1\supseteq Q_7^4, leading to a contradiction. Thus, it is concluded that \Vert \{y_1,y_2\},\{u_3,u_4\}{\Vert }_H=3, and \Vert \{x_1,x_2\},\{u_1,u_2\}{\Vert }_H=2. If x₂u₁ is a multiple edge, then there are x_1{x}_2{u}_1{u}_4{x}_1\supseteq Q_8^4 and y_2{y}_1{u}_3{u}_2{y}_2\supseteq Q_7^4, which leads to a contradiction. If x₁u₂ is a multiple edge, then x_1{x}_2{u}_3{u}_2{x}_1\supseteq Q_8^4 and y_1{y}_2{u}_4{u}_1{y}_1\supseteq Q_7^4, leading to a contradiction. Thus, it follows that x₂u₂, x₁u₁ are multiple edges, which implies x_1{x}_2{u}_2{u}_1{x}_1\supseteq Q_8^4and contradicts the assumption that M\left[\right\{x_1,x_2,u_1,u_2\left\}\right]⊉Q_8^4.

(2) If x₁u₃, x₂u₃, x₂u₄ are multiple edges, then y₂u₄ is not a multiple edge. Otherwise, there would be x_2{y}_1{y}_2{u}_4{x}_2\supseteq Q_8^4 and x_1{u}_3{u}_2{u}_1{x}_1\supseteq Q_7^4, leading to a contradiction. Thus, there are \Vert \{y_1,y_2\},\{u_3,u_4\}{\Vert }_H=3, and \Vert \{x_1,x_2\},\{u_1,u_2\}{\Vert }_H=2, so y₁u₃, y₁u₄, y₂u₃ are multiple edges. If x₁u₁ is a multiple edge, then x_1{x}_2{u}_4{u}_1{x}_1\supseteq Q_8^4 and y_1{y}_2{u}_3{u}_2{y}_1\supseteq Q_7^4, which leads to a contradiction. If x₁u₂ is a multiple edge, then x_1{x}_2{u}_2{u}_3{x}_1\supseteq Q_8^4 and y_1{y}_2{u}_3{u}_4{y}_1\supseteq Q_7^4, leading to a contradiction. Thus, it is concluded that x₂u₂, x₂u₁ are multiple edges. However, this results in x_1{x}_2{u}_3{u}_2{x}_1\supseteq Q_8^4 and y_2{y}_1{u}_4{u}_1{y}_2\supseteq Q_7^4, leading to a contradiction.

Case 2: When \Vert \{x_1,x_2\},\{u_3,u_4\}\Vert =6, there is \Vert \{x_1,x_2\},\{u_1,u_2\}\Vert \ge 6, which implies \Vert \{x_1,x_2\},\{u_3,u_4\}{\Vert }_H=2.

If \Vert \{x_1,x_2\},\{u_1,u_2\}\Vert \ge 7, then as in Case 1, there is a contradiction. This confirms that \Vert \{x_1,x_2\},\{u_1,u_2\}\Vert =6, there is \Vert \{x_1,x_2\},\{u_1,u_2\}{\Vert }_H=2. Since \Vert \overline{U},U_j{\Vert }_H=8 and \Vert \{x_1,x_2\},\{u_3,u_4\}{\Vert }_H=2, it follows that \Vert \{y_1,y_2\},\{u_1,u_2\}{\Vert }_H=4. This leads to the containment relationships: x_1{x}_2{u}_3{u}_4{x}_1\supseteq Q_7^4, y_2{y}_1{u}_2{u}_1{y}_2\supseteq Q_8^4, which results in a contradiction. This completes the proof. □

Assertion 3.7　 For each U_l\in U, one of the following conditions holds: \Vert \left\{x_1\right\},U_j\Vert =\Vert \left\{x_2\right\},U_j\Vert =\Vert \left\{y_1\right\},U_j\Vert =8,\Vert \left\{y_2\right\},U_j\Vert =0; or \Vert \left\{y_1\right\},U_j\Vert =\Vert \left\{y_2\right\},U_j\Vert =\Vert \left\{x_2\right\},U_j\Vert =8,\Vert \left\{x_1\right\},U_j\Vert =0.

Proof　From Assertion 3.6, there are \mathrm{\forall }{U}_l\in U, \Vert V\left(P\right),U_l{\Vert }_{|H}\ge 9. Let U_j=u_1{u}_2{u}_3{u}_4{u}_1. By symmetry, there is\Vert \{x_1,x_2\},U_j{\Vert }_H\ge 5. Furthermore, it is assumed \Vert \{x_1,x_2\},\{u_1,u_2\}{\Vert }_H\ge 3, which implies M\left[\{x_1,x_2,u_1,u_2\}\right]\supseteq Q_8^4. Thus, there is \Vert \{y_1,y_2\},\{u_3,u_4\}\Vert \le 4.

Now, suppose that M\left[\{x_1,x_2,u_3,u_4\}\right]\supseteq Q_8^4. Then, \Vert \{y_1,y_2\},\{u_1,u_2\}\Vert \le 4, which leads to \Vert \{y_1,y_2\},U_j\Vert \le 8,\Vert \{x_1,x_2\},U_j\Vert \ge 16. Thus, there are \Vert \left\{x_1\right\},U_j\Vert =\Vert \left\{x_2\right\},U_j\Vert =8, \Vert \{y_1,y_2\},\{u_1,u_2\}\Vert =4, and \Vert \{y_1,y_2\},\{u_3,u_4\}\Vert =4. Since M\left[\{x_1,u_1,u_2,u_3\}\right]\supseteq Q_8^4 and u₄x₂y₁y₂ forms a multiple-edge path of four vertices, from equation (4) it is known that u₂u₄ is a multiple edge. If u_4{y}_2\in E, then M\left[\right\{x_1,u_1,u_2,u_3\left\}\right]\supseteq Q_8^4, M\left[\right\{u_4,x_2,y_1,y_2\left\}\right]\supseteq Q_7^4, which leads to a contradiction. Therefore, u_4{y}_2\notin E. Similarly, it is known that u_3{y}_2\notin E. Consequently, y₁u₃,y₁u₄ are multiple edges. Similarly, y₁u₁, y₁u₂ are multiple edges, leading to \Vert \{y_2,U_j\}\Vert =0.

Now, suppose that M\left[\{x_1,x_2,u_3,u_4\}\right]⊉Q_8^4. Then, \Vert \{x_1,x_2\},\{u_3,u_4\}\Vert \le 6. The two cases are considered as follows.

Case 1: When 5\le \Vert \{x_1,x_2\},\{u_3,u_4\}\Vert \le 6, it is concluded that \mathrm{M}\left[\{x_1,x_2,u_3,u_4\}\right]⊉Q_8^4 and M\left[\right\{x_1,x_2,u_3,u_4\left\}\right]\supseteq Q_7^4. Thus, M\left[\{y_1,y_2,u_1,u_2\}\right]⊉Q_8^4. Since \Vert \{y_1,y_2\},\{u_3,u_4\}\Vert \le 4 and \Vert \{x_1,x_2\},\{u_3,u_4\}\Vert \le 6, it follows that \Vert \overline{U},\{u_1,u_2\}\Vert \ge 24-10=14. Thus, it is known that \Vert \overline{U},\{u_1,u_2\}{\Vert }_H\ge 6. Since M\left[\{y_1,y_2,u_1,u_2\}\right]⊉Q_8^4, there is \Vert \{y_1,y_2\},\{u_1,u_2\}{\Vert }_H\le 2. This implies \Vert \{x_1,x_2\},\{u_1,u_2\}{\Vert }_H\ge 4, so it is concluded that \Vert \{x_1,x_2\},\{u_1,u_2\}{\Vert }_H=4 and \Vert \{y_1,y_2\},\{u_1,u_2\}{\Vert }_H=2. Without losing generality, assume that y₁u₁ is a multiple edge. Since M\left[\{y_1,y_2,u_1,u_2\}\right]⊉Q_8^4, it follows that y₂u₂ is not a multiple edge. The two cases are considered as follows:

(a) y₂u₁ is a multiple edge. Since \Vert \overline{U},\{u_1,u_2\}\Vert \ge 14, and , it follows that y₂u_2, y₁u₂ are single edges. If x₁u₃ is a multiple edge, then x_1{u}_1{u}_4{u}_3{x}_1\supseteq Q_8^4, x_2{y}_1{y}_2{u}_2{x}_2\supseteq Q_7^4, which is a contradiction. Hence, x₁u₃ is not a multiple edge. Since x_1{x}_2{u}_3{u}_4{x}_1⊉Q_8^4, it is known that x₂u₄ is a multiple edge. If x₁u₄ is a multiple edge, then x_1{u}_4{u}_3{u}_2{x}_1\supseteq Q_8^4, and y₂y₁x₂u₁ forms a multiple-edge path of order 4. By equation (4), it is concluded that u₁u₃, u₂u₄ are multiple edges. This leads to u_1{x}_1{u}_4{u}_3{u}_1\supseteq Q_8^4, x_2{y}_1{y}_2{u}_2{x}_2\supseteq Q_7^4, which is a contradiction. Hence, x₁u₄ is not a multiple edge, so x₂u₃ must be a multiple edge. Since x_1{x}_2{u}_3{u}_2{x}_1\supseteq Q_8^4, and y₂y₁u₁u₄ forms a multiple-edge path of order 4, by equation (4), it is concluded that u₁u₃, u₂u₄ are multiple edges. If x₁y₁ has an edge, then x_2{u}_4{u}_3{u}_2{x}_2\supseteq Q_8^4, x_1{u}_1{y}_2{y}_1{x}_1\supseteq Q_7^4, which is a contradiction. Thus, x_1{y}_1\notin E, and x₂y₂ is a multiple edge. If \Vert \{y_1,y_2\},\left\{u_4\right\}\Vert \ge 1, then x_1{u}_1{u}_3{u}_2{x}_1\supseteq Q_8^4, M\left[\{x_2,u_4,y_2,y_1\}\right]\supseteq Q_7^4, which is a contradiction. Therefore, \Vert \{y_1,y_2\},\left\{u_4\right\}\Vert =0. Hence, \Vert \{y_1,y_2\},\left\{u_3\right\}\Vert >0. Since \Vert \overline{U},\{u_1,u_2\}\Vert =14,\Vert \{x_1,x_2\},\{u_3,u_4\}\Vert \le 6, it is concluded that \Vert \{y_1,y_2\},\{u_3,u_4\}\Vert \ge 4. However, since there has been \Vert \{y_1,y_2\},\{u_3,u_4\}\Vert \le 4, it follows that \Vert \{y_1,y_2\},\{u_3,u_4\}\Vert =4. This implies \Vert \{y_1,y_2\},\left\{u_3\right\}\Vert =4, meaning that y₁u₃, y₂u₃ are multiple edges. Consequently, x_1{x}_2{y}_2{u}_1{x}_1\supseteq Q_8^4, y_1{u}_2{u}_4{u}_3{y}_1\supseteq Q_7^4, which leads to a contradiction.

(b) Assume that y₁u₂ is a multiple edge. Since \Vert \overline{U},\{u_1,u_2\}\Vert \ge 14 and , it follows that y₂u₂, y₂u₁ are single edges. If x₁u₃ is a multiple edge, then x_1{x}_2{u}_2{u}_3{x}_1\supseteq Q_8^4 and y₂y1u₁u₄ forms a multiple-edge path of order 4. By equation (4), it is concluded that u₁u₃, u₂u₄ are multiple edges. This leads to x_1{u}_1{u}_4{u}_3{x}_1\supseteq Q_8^4, x_2{y}_1{y}_2{u}_2{x}_2\supseteq Q_7^4, which is a contradiction. Thus, x₁u₃ is not a multiple edge, so x₂u₄ must be a multiple edge. Since x_1{u}_1{u}_4{x}_2{x}_1\supseteq Q_8^4, and y₂y₁u₂u₃ forms a multiple-edge path of order 4, by equation (4) it is concluded that u₁u₃, u₂u₄ are multiple edges. If x₁u₄ is also a multiple edge, then u_1{x}_1{u}_4{u}_3{u}_1\supseteq Q_8^4, x_2{y}_1{y}_2{u}_2{x}_2\supseteq Q_7^4, which is a contradiction. If x₂u₃ is a multiple edge, then y_2{u}_4\notin E. Otherwise, there would be x_1{x}_2{u}_3{u}_2{x}_1\supseteq Q_8^4, u_4{u}_1{y}_1{y}_2{u}_4\supseteq Q_7^4, which is a contradiction. Similarly, y_2{u}_3\notin E. Since \Vert \overline{U},\left\{u_1,u_2\right\}\Vert =10, \Vert \{x_1,x_2\},\{u_3,u_4\}\Vert \le 6, it is concluded that \Vert \{y_1,y_2\},\{u_3,u_4\}\Vert \ge 4. However, since there has been \Vert \{y_1,y_2\},\{u_3,u_4\}\Vert \le 4, it follows that \Vert \{y_1,y_2\},\{u_3,u_4\}\Vert =4. This implies that y₁u₃, y₁u₄ are multiple edges. Consequently, y_2{y}_1{u}_4{u}_2{y}_2\supseteq Q_7^4, x_1{u}_1{u}_3{x}_2{x}_1\supseteq Q_8^4, which leads to a contradiction.

When y₂u₂ is a multiple edge, the situation is similar, leading to a contradiction. The details are omitted here.

Case 2: If \Vert \{x_1,x_2\},\{u_3,u_4\}\Vert \le 4, then \Vert V\left(P\right),\{u_1,u_2\}\Vert \ge 24-8=16. That is, \Vert \left\{u_1\right\},V\left(P\right)\Vert =\Vert \left\{u_2\right\},V\left(P\right)\Vert =8, \Vert \{u_3,u_4\},\{x_1,x_2\}\Vert =4, and \Vert \{u_3,u_4\},\{y_1,y_2\}\Vert =4. Since \Vert \{x_1,x_2\},U_j{\Vert }_H\ge 5, there is \Vert \{x_1,x_2\},\{u_3,u_4\}{\Vert }_H\ge 1. Since M\left[\{u_1,u_2,y_1,y_2\}\right]\supseteq Q_8^4 and x₁x₂u₃u₄ forms a multiple-edge path of order 4, by equation (4), it is concluded that u₁u₃, u₂u₄ are multiple edges.

(a) \Vert \left\{x_1\right\},\{u_3,u_4\}{\Vert }_H\ge 1.

By the symmetry of u₃ and u₄, it is assumed that x₁u₃ is a multiple edge. This implies \Vert x_2,u_4\Vert =0 and \Vert x_1,u_4\Vert =0. Otherwise, there would be M\left[\right\{y_1,y_2,u_1,u_2\left\}\right]\supseteq Q_8^4, M\left[\right\{x_1,x_2,u_3,u_4\left\}\right]\supseteq Q_7^4, which leads to a contradiction. Thus, u₃x₂ is a multiple edge. Similarly, it is known that u₃y₁, u₃y₂ are multiple edges, implying \Vert \left\{u_4\right\},V\left(P\right)\Vert =0. Since \Vert V\left(P\right)\Vert =8, assume x_1{y}_1\in E. Then there are M\left[\right\{u_3,x_1,y_1,y_2\left\}\right]\supseteq Q_7^4, M\left[\right\{x_2,u_2,u_4,u_1\left\}\right]\supseteq Q_8^4, which leads to a contradiction. Therefore, x_1{y}_1\notin E, and x₂y₂ is a multiple edge. This results in M\left[\{u_3,x_1,x_2,y_2\}\right]\supseteq Q_7^4, M\left[\{y_1,u_2,u_4,u_1\}\right]\supseteq Q_8^4, which leads to a contradiction.

(b) \Vert \left\{x_2\right\},\{u_3,u_4\}{\Vert }_H\ge 1.

Without losing generality, it is assumed that x₂u₃ is a multiple edge. Then \Vert x_1,u_3\Vert =0, and \Vert x_1,u_4\Vert =0. Otherwise, there would be M\left[\right\{x_1,u_3,u_4,u_1\left\}\right]\supseteq Q_7^4, M\left[\right\{x_2,y_1,y_2,u_2\left\}\right]\supseteq Q_8^4, which leads to a contradiction. Since \Vert \left\{x_1\right\},\{u_3,u_4\}\Vert =0, \Vert \{x_1,x_2\},\{u_3,u_4\}\Vert =4, it follows that \Vert \left\{x_2\right\},\{u_3,u_4\}\Vert =4, which means x₂u₃, x₂u₄ are multiple edges. Since M\left[\{x_1,u_1,u_3,u_2\}\right]\supseteq Q_8^4, \Vert y_2,u_4\Vert =0. Similarly, it is known \Vert y_2,u_3\Vert =0. Thus, y₁u₃, y₁u₄ must be multiple edges. Since \Vert V\left(P\right)\Vert =8, assume that x_1{y}_1\in E. Then, there are M\left[\right\{u_3,x_2,u_1,u_4\left\}\right]\supseteq Q_8^4, M\left[\right\{x_1,u_2,y_2,y_1\left\}\right]\supseteq Q_7^4, which leads to a contradiction. Thus, x_1{y}_1\notin E. This implies that x₂y₂ is a multiple edge. Consequently, there are M\left[\right\{u_1,x_1,x_2,y_2\left\}\right]\supseteq Q_7^4, M\left[\right\{y_1,u_2,u_4,u_3\left\}\right]\supseteq Q_8^4, which leads to a contradiction. This completes the proof.

Let U_1=u_1{u}_2{u}_3{u}_4{u}_1. From Assertion 3.7, it is known that there exist three vertices in V(P), namely x₁,x₂,y₁, such that \Vert \left\{x_1\right\},U_1\Vert =\Vert \left\{x_2\right\},U_1\Vert =\Vert \left\{y_1\right\},U_1\Vert =8, \Vert \left\{y_2\right\},U_j\Vert =0. If \Vert y_2,x_2\Vert >0, then M\left[\right\{x_2,y_2,y_1,u_4\left\}\right]\supseteq Q_7^4, M\left[\right\{x_1,u_1,u_2,u_3\left\}\right]\supseteq Q_8^4, which leads to a contradiction. Therefore, \Vert y_2,x_2\Vert =0. This implies that x₁y₁ is a multiple edge. Let U^{\prime }=U\mathrm{\setminus }{U}_1. Then,

\Vert \left\{y_2\right\},U^{\prime }\Vert \ge 6k-2-2>6\left(k-2\right).

So, there exists some U_l\in U^{\prime } such that \Vert y_2,U_l\Vert \ge 7. Thus, \Vert \left\{y_1\right\},U_l\Vert =\Vert \left\{y_2\right\},U_l\Vert =\Vert \left\{x_2\right\},U_l\Vert =8, \Vert \left\{x_1\right\},U_l\Vert =0. Let U_l=v_1{v}_2{v}_3{v}_4{v}_1. Then, there are M\left[\right\{x_1,u_1,u_2,u_3\left\}\right]\supseteq Q_8^4, M\left[\right\{y_2,v_1,v_2,v_3\left\}\right]\supseteq Q_8^4, M\left[\right\{x_2,u_4,y_1,v_4\left\}\right]\supseteq Q_7^4. This implies that M\supseteq \left(k-1\right)Q_8^4\cup Q_7^4, which leads to a contradiction. This completes the proof of Theorem 1.2.

References

[1] Bang-JensenJ.GutinG.Z., Digraphs: Theory, Algorithms and Applications, London: Springer-Verlag, 2008

[2] Czygrinow A., Kierstead, H.A. , Molla, T. . On directed versions of the Corrádi-Hajnal corollary. European J. Combin. 2014; 42: 1–14

[3] ErdösP., Some recent combinatorial problems, Technical Report, Bielefeld: University of Bielefeld, 1990.

[4] Gao Y.S., Zou, Q.S. , Ma, L.Y. . Vertex-disjoint quadrilaterals in multigraphs. Graphs Combin. 2017; 33(4): 901–912

[5] Randerath B., Schiermeyer, I. , Wang, H. . On quadriaterals in a graph. Discrete Math. 1999; 203(1/2/3): 229–237

[6] Wang H. . Proof of the Erdös-Faudree conjecture on quadrilaterals. Graphs Combin. 2010; 26(6): 833–877

[7] Zhang D.H. , Wang, H. . Disjoint directed quadrilaterals in a directed graph. J. Graph Theory 2005; 50(2): 91–104

RIGHTS & PERMISSIONS

Higher Education Press 2025