The k-Ramsey number of two five cycles

Abstract

Given any two graphs F and H, the Ramsey number R(F, H) is defined as the smallest positive integer n such that every red-blue coloring of the edges of the complete graph K_n of order n, there will be a subgraph of K_n isomorphic to F whose edges are all colored red (a red F) or a subgraph of K_n isomorphic to H whose edges are all colored blue (a blue H). If F and H are bipartite graphs, then the k-Ramsey number $R_k(F,H)$ is defined as the smallest positive integer n such that for any red-blue coloring of the edges of the complete k-partite graph of order n in which each partite set is of order $\lfloor \frac{n}{k}\rfloor$ or $\lceil \frac{n}{k}\rceil$ there will be a subgraph isomorphic to F whose edges are all colored red (a red F) or a subgraph isomorphic to H whose edges are all colored blue (a blue H). Andrews, Chartrand, Lumduanhom and Zhang found the k-Ramsey number $R_k(F,H)$ for $F=H=C_4$, and for $F=K_{1,t}$ and $H=K_{1,s}$ where $s,t\ge 2$. We continue their work by investigating the case where the graphs F and H are both C₅.

Keywords:

• Bipartite
• Ramsey
• k-Ramsey number
• odd cycle

1 Introduction

The graphs we consider in this paper are undirected and simple. Given a graph $G=(V,E)$ with $v\in V$, the open neighborhood of v, denoted N(v), is defined as the set of all vertices adjacent to v. The edges uv and vx are adjacent in G, while the edges vx and wy are nonadjacent. The number of vertices in a graph G is the order of G and the number of edges is the size of G. We will use n and m for the order and size, respectively, of a graph. For notations not defined here, we refer the reader to [2].

In a red-blue coloring of (the edges of) a graph G, every edge of G is colored red or blue. For two graphs F and H, the Ramsey number R(F, H) of F and H is the smallest positive integer n such that for every red-blue coloring of the complete graph K_n of order n, there is either a subgraph isomorphic to F all of whose edges are colored red (a red F) or a subgraph isomorphic to H all of whose edges are colored blue (a blue H). The Ramsey number R(F, H) is known to exist for each pair F, H of graphs.

In the case where F and H are bipartite, the bipartite Ramsey number BR(F, H) is defined as the smallest positive integer r such that every red-blue coloring of the r-regular complete bipartite graph $K_{r,r}$ results in a red F or a blue H. The bipartite Ramsey number BR(F, H) is also known to exist for each pair F, H of bipartite graphs (see [4]).

For an integer $k\ge 2$, a balanced complete k-partite graph G of order $n\ge k$ is the complete k-partite graph in which every partite set has either $\lceil \frac{n}{k}\rceil$ or $\lfloor \frac{n}{k}\rfloor$ vertices. Suppose $n=kq+r$ where $0\le r\le k-1$. Then $\lfloor \frac{n}{k}\rfloor =q$ and $\lceil \frac{n}{k}\rceil =q+1$. Let $\mathcal{l}$ be the number of partite sets in G of order $\lfloor \frac{n}{k}\rfloor =q$. Then the number of partite sets of order $\lceil \frac{n}{k}\rceil =q+1$ equals $k-\mathcal{l}$. Hence, $n=\mathcal{l}q+(k-\mathcal{l})(q+1)=kq+k-\mathcal{l}$, and $kq+r=kq+k-\mathcal{l}$, whence $\mathcal{l}=k-r$. Thus, we have k – r partite sets of order $\lfloor \frac{n}{k}\rfloor$ and r partite sets of order $\lceil \frac{n}{k}\rceil$, and so G is isomorphic to $K_{\underset{r}{\underbrace{\lceil \frac{n}{k}\rceil ,\dots ,\lceil \frac{n}{k}\rceil }},\underset{k-r}{\underbrace{\lfloor \frac{n}{k}\rfloor ,\dots ,\lfloor \frac{n}{k}\rfloor }}}=K_{\underset{r}{\underbrace{q+1,\dots ,q+1}},\underset{k-r}{\underbrace{q,\dots ,q}}}$. If r = 0, then G is a $(k-1)q$-regular graph, which we denote by $K_{k(q)}$. If $1\le r\le k-1$, then we denote G by $K_{r(q+1),(k-r)q}$. For bipartite graphs F and H and an integer k with $2\le k\le R(F,H)$, the k-Ramsey number $R_k(F,H)$ is defined in [1] as the smallest positive integer n such that every red-blue coloring of a balanced complete k-partite graph of order n produces either a red F or a blue H.

For two sets X and Y of vertices of a graph G, the set of edges in G joining a vertex in X and a vertex in Y is denoted by $[X,Y]$. The subgraph induced by $[X,Y]$ is denoted by $G〈[X,Y]〉$ or just $〈[X,Y]〉$ if the context is clear. The subgraph induced by X is denoted by $G〈X〉$ or just $〈X〉$ if the context is clear.

Let $BR(F,H)=p$ and consider the complete k-partite graph $K_{k(p)}$. Let $V_1,\dots ,V_{kp}$ denote the partite sets of G. Then $G\prime =〈[V_1,V_2]〉\cong K_{p,p}$. Let (R, B) be any two-coloring of G. Then, as we have a 2-coloring of the edges of $G\prime$ and $BR(F,H)=p$, either a blue F or a red H is produced in $G\prime$ and therefore in G. Thus, $R_k(F,H)\le kp=\mathit{kBR}(F,H)$ and so $R_k(F,H)$ exists. In [1], a formula for $R_k(K_{1,s},K_{1,t})$ is presented for each pair $K_{1,s},K_{1,t}$ of stars of sizes $s\ge 2$ and $t\ge 2$, respectively, and each integer k with $2\le k\le n$ where $R(K_{1,s},K_{1,t})=n$. The authors also determine $R_k(C_4,C_4)$ where $2\le k\le 5$.

For a red-blue coloring (R, B) of a graph G, let G_R and G_B denote the red and blue subgraphs of G, respectively.

It is not necessarily the case that $R_k(F,H)$ exists when F and H are not bipartite, which was pointed out by Johnston in his Ph.D. dissertation [5]. To see this, let G be any balanced complete 2-bipartite graph. No matter how we color the edges of G, there is no subgraph isomorphic to F all of whose edges are colored red nor is there a subgraph isomorphic to H all of whose edges are colored blue. Next, consider the case when k = 3. Let G be any balanced complete 3-partite graph with partite sets V₁, V₂ and V₃. Assigning the color red to every edge of $[V_1,V_2]$ and blue to all other edges of G results in G_R and G_B both being bipartite. Thus, $R_3(F,H)$ does not exist if both F and H are not bipartite. For k = 4, let G be a balanced complete 4-partite graph with partite sets $V_1,V_2,V_3$ and V₄ and color each edge of $[V_1,V_2],[V_2,V_3]$ and $[V_3,V_4]$ red and assign blue to all other edges of G. Then both G_R and G_B are bipartite. Thus, $R_4(F,H)$ does not exist if both F and H are not bipartite.

We note next that $R_5(C_3,C_3)$ does not exist. To see this, let G be a balanced complete 5-partite graph with partite sets V_i for $1\le i\le 5$. If the edges in $[V_1,V_2],[V_2,V_3]$, $[V_3,V_4],[V_4,V_5],[V_5,V_1]$ are colored red and all other edges are colored blue, then G does not contain a monochromatic K₃. Consequently, $R_k(C_3,C_3)$ only exists when $k=R(C_3,C_3)=6$, since then $R_6(C_3,C_3)=R(C_3,C_3)$.

The Ramsey number $R(C_n,C_m)$ for two cycles was independently obtained by Faudree and Schelp [3] and Rosta [7].

Theorem 1.

$$\begin{array}{c}R(C_n,C_m)\\ =\mathrm{}\{\begin{array}{cc}2n-1& \text{for}3\le m\le n,\mathrm{m}\text{is odd},(n,m)\ne (3,3),\\ n-1+\frac{m}{2}& \text{for}4\le m\le n,m\text{and}n\text{even},\\ & (n,m)\ne (4,4),\\ \max \{n-1+\frac{m}{2},2m-1\}& \text{for}4\le m<n,m\text{even and}n\text{odd}.\end{array}\end{array}$$

The following result is due to Johnston.

Theorem 2.

[5] Let $p_1=BR(K_{k,k},K_{k,k})$, and let $p_{i+1}=BR(K_{p_i},K_{p_i})$ for $i=1,\dots ,5$. For integers $k\ge \mathcal{l}\ge 2$, the Ramsey number $R_5(C_{2\mathcal{l}+1},C_{2k+1})\le 5p_5$.

Recall that $R_k(C_5,C_5)$ does not exist for $2\le k\le 4$, and note that $R(C_5,C_5)=9$ by Theorem 1. Our goal in this paper is to show that $R_k(C_5,C_5)=9$ for $5\le k\le 8=R(C_5,C_5)-1$.

2 Preliminary remarks

We begin this section by stating results that will be used in the remainder of the paper.

Let n be a positive integer and G a graph. We define $\text{ex}(n,G)$ to be the largest number of edges possible in a graph on n vertices that does not contain G as a subgraph. Reiman determined the following upper bound on $\text{ex}(n,C_4)$.

Theorem 3.

[6] Let n be a positive integer. Then $\text{ex}(n,C_4)\le \frac{n}{4}(1+\sqrt{4n-3})$.

Lemma 4.

Let H be a graph of order five. If $m(H)\ge 8$, then H has a 5-cycle.

Proof.

The result is obviously true for m(H) = 9 or m(H) = 10.

Next consider the case when m(H) = 8. Let $V(H)=\{v_1,v_2,v_3,v_4,v_5\}$. If two adjacent edges, say $v_1{v}_3$ and $v_1{v}_4$, are omitted, then $v_1,v_2,v_3,v_4,v_5,v_1$ is one 5-cycle of H. If two nonadjacent edges, say $v_1{v}_2$ and $v_3{v}_5$ are omitted, then $v_1,v_3,v_2,v_5,v_4,v_1$ is a 5-cycle of H. □

Lemma 5.

Let H be a graph of order five obtained from K₅ by deleting exactly one edge. Delete two nonadjacent edges from H to form the graph $H\prime$. Then $H\prime$ has a 5-cycle.

Proof.

Let $V(H)=\{v_1,v_2,v_3,v_4,v_5\}$ and suppose $v_1{v}_2$ is the deleted edge. Consider any two nonadjacent edges e and f of G. Suppose first that e and f are both incident with v₁ and v₂, say $e=v_2{v}_3$ and $f=v_1{v}_5$. Then $v_1,v_3,v_5,v_2,v_4,v_1$ is a 5-cycle of $H\prime$. Next suppose that exactly one of e or f is incident with a vertex in $\{v_1,v_2\}$, say $e=v_2{v}_3$. But then $f=v_4{v}_5$, and $v_1,v_3,v_5,v_2,v_4,v_1$ is a 5-cycle of $H\prime$. □

Next we show that determining $R_k(C_5,C_5)=9$ for $5\le k\le 8$ reduces to showing that $R_5(C_5,C_5)\le 9$. Consider the following complete multipartite graphs G_k for $5\le k\le 8$: $$\begin{array}{cc}{G}_5=K_{4(2),1}\hfill & \text{ if }k=5,\hfill \\ G_6=K_{3(2),3(1)}\hfill & \text{ if }k=6,\hfill \\ G_7=K_{2(2),5(1)}\hfill & \text{ if }k=7,\hfill \\ G_8=K_{2,7(1)}\hfill & \text{ if }k=8.\hfill \end{array}$$

Note that $G_k\subseteq G_{k+1}$ for $5\le k\le 8$.

Observation 6. If $R_k(C_5,C_5)\le 9$, then $R_{k+1}(C_5,C_5)\le 9$ for $5\le k\le 8$.

Proof.

Let $5\le k\le 8$ and consider any 2-coloring $C=(R,B)$ of the edges of $G_{k+1}$. Then, as $G_k\subseteq G_{k+1}$, the coloring C induces a 2-coloring on the edges of G_k. Moreover, as $G_k(C_5,C_5)\le 9$, either the red subgraph of this induced coloring contains a C₅ or the blue subgraph of this induced coloring contains a C₅. As $G_k\subseteq G_{k+1}$, it now follows that the red subgraph associated with C contains a C₅ or the blue subgraph associated with C contains a C₅, whence $R_{k+1}(C_5,C_5)\le 9$. □

Consider the following complete multipartite graphs H_k for $5\le k\le 8$: $$\begin{array}{cc}{H}_5=K_{3(2),2(1)}\hfill & \text{ if }k=5,\hfill \\ H_6=K_{2(2),4(1)}\hfill & \text{ if }k=6,\hfill \\ H_7=K_{2,6(1}\hfill & \text{ if }k=7,\hfill \\ H_8=K_{8(1)}\hfill & \text{ if }k=8.\hfill \end{array}$$

As $R(C_5,C_5)=8$, there exists a 2-coloring C of the edges of K₈ such that neither the red graph nor the blue graph has a 5-cycle. Note that $H_k\subseteq K_8$, and that the coloring C induces a coloring on the edges of H_k containing no monochromatic 5-cycle for $5\le k\le 8$, whence $R_k(C_5,C_5)\ge 9$ for $5\le k\le 8$. Thus, if we can show that $R_5(C_5,C_5)\le 9$, then, by Observation 6 and the latter remark, it follows that $R_k(C_5,C_5)=9$ for $5\le k\le 8$.

3 Main result

We now show that $R_5(C_5,C_5)\le 9$.

Theorem 7.

$R_5(C_5,C_5)\le 9$.

Proof.

Let $G=K_{4(2),1}$ and assume to the contrary that there exists a red-blue coloring of the edges of G that contains neither a red C₅ nor a blue C₅. Note that $m:=m(G)=(\begin{array}{c}9\\ 2\end{array})-4=32$. Further, let G_R and G_B denote the subgraphs of G induced by the red edges and the blue edges of G respectively. Lastly, let m_R and m_B denote the size of G_R and G_B respectively. Then $$m=m_R+m_B=32.$$

Without loss of generality, suppose $m_R\ge 16$. The graph G_R is not a forest as $m_R>8=9-1$. By Theorem 3, we have $$\text{ex}(|V(G_R)|,C_4)\le \frac{9}{4}(1+\sqrt{4(9)-3})\approx 15.2,$$which implies that G_R has a 4-cycle, as $m_R\ge 16$. Let $\mathcal{l}$ denote the length of a longest cycle of G_R. Then, as G_R does not contain a 5-cycle, we have $\mathcal{l}\in \{4,6,7,8,9\}$. We now consider each of these possibilities for $\mathcal{l}$. Let $C:=v_1,v_2,\dots ,v_{\mathcal{l}},v_1$ be a longest cycle in G_R and let $V(G_R)-V(C)=\{v_{\mathcal{l}+1},\dots ,v_9\}$. Let G₁ (G₂, respectively) be the subgraph induced by V(C) ($V(G_R)-V(C)$, respectively) in G_R, and let G₃ be the subgraph of G_R induced by the edges $E(G_R)-E(G_1)-E(G_2)$. Lastly, let m_i denote the size of the graph G_i for i = 1, 2, 3. Note that $m_R=m_1+m_2+m_3$. □

Case 1.

$\mathcal{l}=4$.

As $C_4\subseteq G_1$, we see that $4\le m_1\le 6$.

We first establish a few useful facts.

Fact 1. If $v\prime \in V(G_R)$, then G₂ does not contain a 4-cycle $C\prime$ such that $|N(C\prime )\cap \{v\prime \left\}\right|\ge 3$.

Proof.

Suppose G₂ contains a 4-cycle $C\prime :=u{\prime }_1,u{\prime }_2,$ $u{\prime }_3,u{\prime }_4,u{\prime }_1$ such that $|N(C\prime )\cap \{v\prime \left\}\right|\ge 3$. As $|N(C\prime )\cap \{v\prime \left\}\right|\ge 3$, we have two consecutive vertices on $C\prime$ which are adjacent to $v\prime$. Without loss of generality, assume $\{u{\prime }_1,u{\prime }_2\}\subseteq N(v\prime )$. Then $v\prime ,u{\prime }_1,u{\prime }_4,u{\prime }_3,u{\prime }_2,v\prime$ is a 5-cycle in G_R, which is a contradiction. The result now follows.

Fact 2. Suppose $u\in V(G_2)$. Then $|N(u)\cap V(C)|\le 2$. Moreover, if $|N(u)\cap V(C)|=2$, then u is adjacent to two nonconsecutive vertices of C, and $m_1\le 5$.

Proof.

By Fact 1, we have $|N(u)\cap V(C)|\le 2$. If $N(u)=\{v_1,v_3\}$, say, then v₂ is not adjacent to v₄, since otherwise $u,v_1,v_2,v_4,v_3,u$ is a 5-cycle of G_R, which is a contradiction. Thus, if $N(u)=\{v_1,v_3\}$, then $m_1\le 5$. □

Fact 3. Let G₂₁ be a nontrivial component of G₂ and let $u\in V(G_{21})$. If $|N(u)\cap V(C)|=2$, then $N(v)\cap V(C)=\varnothing$ for all $v\in V(G_{21})-\left\{u\right\}$.

Proof.

Let $u\in V(G_{21})$ and suppose $|N(u)\cap V(C)|=2$. Without loss of generality, assume $N(u)\cap V(C)=\{v_1,v_3\}$. Let $v\in V(G_{21})-\left\{u\right\}$. As G₂₁ is connected, there is a nontrivial path P joining u and v. If v is adjacent to v₂, then P followed by the vertices $v_2,v_3,v_4,v_1,u$ is a t-cycle of G_R where $t\ge 6$, which is a contradiction. Thus, v is not adjacent to v₂, and, by symmetry, neither is v adjacent to v₄. If v is adjacent to v₃, then P followed by the vertices $v_3,v_4,v_1,u$ is a t-cycle of G_R, where $t\ge 5$, which is a contradiction. If v is adjacent to v₁, then P followed by the vertices $v_1,v_2,v_3,u$ is a t-cycle of G_R, where $t\ge 5$, which is a contradiction. Thus, $N(v)\cap V(C)=\varnothing$. □

Fact 4. Let G₂₁ be a nontrivial component of G₂. Then $|N(V(G_{21}))\cap V(C)|\le |V(G_{21})|$. Moreover, if $|N(u)\cap V(C)|=2$ for some $u\in G_{21}$, then $|N(V(G_{21}))\cap V(C)|=2$.

Proof.

If $|N(u)\cap V(C)|=2$ for some $u\in V(G_{21})$, then, by Fact 3, we have $N(v)\cap V(C)=\varnothing$ for all $V(G_{21})-\left\{u\right\}$, and so $|N(V(G_{21}))\cap V(C)|=2\le |V(G_{21})|$. Thus, $|N(u)\cap V(C)|\le 1$ for all $u\in V(G_{21})$, and so $|N(V(G_{21}))\cap V(C)|\le |V(G_{21})|$. □

Fact 5. Let G₂₁ be a non-trivial component of G₂. If $|N(u)\cap V(C)|=1$ for some $u\in V(G_{21})$, then $N(V(G_{21}))\cap V(C)=N(u)\cap V(C)$.

Proof.

Let G₂₁ be a nontrivial component of G₂ and suppose $|N(u)\cap V(C)|=1$ for some $u\in V(G_{21})$. Without loss of generality, assume $N(u)\cap V(C)=\left\{v_1\right\}$. Note that $N(u)\cap V(C)\subseteq N(V(G_{21}))\cap V(C)$.

We show that $N(V(G_{21}))\cap V(C)\subseteq N(u)\cap V(C)$: Let $v\in N(V(G_{21}))\cap V(C)$. If v = v₁, then $v\in N(u)\cap V(C)$. Thus, $v\ne v_1$. Let $u\prime \in V(G_{21})$ be adjacent to v. If $u=u\prime$, then $N(u)\cap V(C)=\{v_1,v\}$, which is a contradiction. Hence, $u\ne u\prime$. As G₂₁ is connected, there exists a path P joining u and $u\prime$. If $v\in \{v_2,v_4\}$, say v = v₂, then P followed by $v,v_3,v_4,v_1,u$ is a t-cycle of G_R for $t\ge 6$, which is a contradiction. If v = v₃, then P followed by $v,v_2,v_1,u$ is a t-cycle of G_R for $t\ge 5$, which is a contradiction.

Thus, $N(V(G_{21}))\cap V(C)=N(u)\cap V(C)$. □

Fact 6. Let $G_{2i}$ be the nontrivial components of G₂ for $i=1,\dots ,s$, let $n_i=|V(G_{2i})|$ for $i=1,\dots ,s$ and let $c={\sum }_{i=1}^s{n}_i$. Then $m_R\le \max \{m_2+(15-c),m_2+11\}$.

Proof.

For simplicity, let $V(G_2)=\{u_1,\dots ,u_5\}$. Without loss of generality, assume u_i for $i=c+1,\dots ,5$ are isolated in G₂. Then, by Facts 2 and 4, $m_3={\sum }_{i=1}^c|N(u_i)\cap V(C)|+{\sum }_{i=c+1}^5|N(u_i)\cap V(C)|\le {\sum }_{i=1}^s{n}_i+2(5-c)=c+10-2c=10-c$. Thus, $m_R\le m_1+m_2+10-c$. If $|N(u_i)\cap V(C)|=2$ for some $i\in \{c+1,\dots ,5\}$, then, by Fact 2, we have $m_1=5$, and so $m_R\le m_1+m_2+10-c=15+m_2-c$. Otherwise, $|N(u_i)\cap V(C)|\le 1$ for $i=c+1,\dots ,5$, and so $m_3={\sum }_{i=1}^c|N(v_i)\cap V(C)|+{\sum }_{i=c+1}^5|N(u_i)\cap V(C)|\le {\sum }_{i=1}^s{n}_i+5-c=c+5-c=5$, whence $m_R\le 6+m_2+5=m_2+11$. It now follows that $m_R\le \max \{m_2+(15-c),m_2+11\}$. □

Note that $m_2\le 7$, since otherwise G_R has a 5-cycle (cf. Lemma 4).

Subcase (i): $m_2\le 4$.

As $m_2+11\le 15$ and $m_R\ge 16$, we have $16\le m_R\le \max \{m_2+(15-c),m_2+11\}=m_2+(15-c)$, and so $c\le m_2-1$. First consider the case when $m_2\le 3$. As $c\ge 2$, we have that $m_2\ge 3$, and so $m_2=3$. Then c = 2 and so $G_2\cong K_2\cup 3P_1$, whence $m_2=1$, which is a contradiction. Next consider the case when $m_2=4$. In this case, $2\le c\le 3$. If c = 2, then $G_2\cong K_2\cup 3P_1$, whence $m_2=1$, which is a contradiction. If c = 3, then $G_2\cong P_3\cup 2P_1$ or $G_2\cong K_3\cup 2P_1$, whence $m_2\le 3$, which is a contradiction.

Subcase (ii): $m_2=5$.

Note that G₂ has at most two nontrivial components, since otherwise $|V(G_2)|\ge 6$. If G₂ has two nontrivial components, then $G_2\cong 2K_2\cup K_1,G_2\cong K_2\cup P_3$ or $G_2\cong K_3\cup K_2$, whence $m_2\le 4$, which is a contradiction. Thus, G₂ has one nontrivial component. Let D denote the graph obtained from K₄ by deleting an edge. Then $G_2\cong K_2+3K_1$ (having size 1), $G_2\cong P_3\cup 2K_1$ (having size 2), $G_2\cong K_3+2K_1$ (having size 3), $G_2\cong H\cup K_1$ where H is a connected subgraph of order four or G₂ is connected. As $m_2=5$, we must have that $G_2\cong D\cup K_1$ or G₂ is connected.

First consider the case when $G_2\cong D\cup K_1$. Let v₅ be the isolated vertex of G₂ and let $V(D)=\{v_6,v_7,v_8,v_9\}$. If $|N(v_5)\cap V(C)|=2$, then, by Fact 2, we have $m_1\le 5$, and so $m(〈\{v_1,v_2,v_3,v_4,v_5\}〉)\le 7$. If $|N(v_5)\cap V(C)|\le 1$, then, as $m_1\le 6$, we have $m(〈\{v_1,v_2,v_3,v_4,v_5\}〉)\le 7$. As $N(V(D))\cap V(C)=m_R-m_2-m(〈\{v_1,v_2,v_3,v_4,v_5\}〉)$, we see that $|N(V(D))\cap V(C)|\ge 16-5-7=4$. If $|N(u)\cap V(C)|=2$ for some $u\in V(D)$, then, by Fact 4, we have $|N(V(D))\cap V(C)|=2$, which is a contradiction. Thus, every vertex of D is adjacent to at most one vertex of C. As $|N(V(D))\cap V(C)|\ge 4$ and D has order four, we see that every vertex of D is adjacent to exactly one vertex of C. By Fact 5, every vertex of D is adjacent to the same vertex of C, say v₁. But then D contains a 4-cycle $C\prime$ such that $|N(C\prime )\cap \{v_1\left\}\right|\ge 3$, which contradicts Fact 1.

Next, consider the case when G₂ is connected. If $|N(v_i)\cap V(C)|=2$ for some $i\in \{5,\dots ,9\}$, then $|N(V(G_2))\cap V(C)|=2$ (cf. Fact 4), and it follows that $m_R=m_1+m_2+m_3\le 6+5+2=13$, which is a contradiction. Thus, $|N(v_i)\cap V(C)|\le 1$ for $i=5,\dots ,9$. If $N(v_i)\cap V(C)=\varnothing$ for some $i\in \{5,\dots ,9\}$, then $m_R=m_1+m_2+m_3\le 6+5+4=15$, which is a contradiction. Thus, every vertex of G₂ is adjacent to exactly one vertex of C. By Fact 5, every vertex of G₂ is adjacent to the same vertex of C, say v₁.

Before proceeding further, we prove the following useful result.

Lemma 8.

G₂ contains P₄ as a subgraph.

Proof.

If $\Delta (G_2)=1$, then $m_2\le \frac{5}{2}$, and so $m_2\le 2$, which is a contradiction.

For simplicity, assume $V(G_2)=\{u_1,\dots ,u_5\}$. Assume, without loss of generality, that u₁ is the vertex of maximum degree in G₂ and that $N_{G_2}(u_1)=\{u_2,u_3,\dots ,u_{\Delta (G_2)\mathrm{ }+\mathrm{ }1}\}$.

First consider the case when $\Delta (G_2)=2$. Then ${\mathrm{deg}}_{G_2}(u_2)={\mathrm{deg}}_{G_2}(u_3)=2$, since otherwise $m_2\le 4$, which is a contradiction. Note that u₂ and u₃ are nonadjacent in G₂, since otherwise $〈\{u_1,u_2,u_3\}〉$ is a component of G₂, which is a contradiction. Thus, u₂ is adjacent to u₄ (say), and $u_4,u_2,u_1,u_3$ is a path of order four in G₂.

Next consider the case when $\Delta (G_2)=3$. As G₂ is connected, u₅ must be adjacent to u_i in G₂ for some $i\in \{2,\dots ,4\}$, say u₂. But then $u_5,u_2,u_1,u_3$ is path of order four in G₂

Lastly, consider the case when $\Delta (G_2)=4$. Then, as $m_2=5$, two vertices of $\{u_2,\dots ,u_5\}$ must be adjacent in G₂, say u₂ and u₃. But then $u_3,u_2,u_1,u_4$ is a path of order four in G₂. □

Let P be a path of order 4 of G₂. As v₁ is adjacent to every vertex of G₂, v₁ is adjacent to the endpoints of P which forms a 5-cycle in G_R, which is a contradiction.

Subcase (iii): $m_2=6$.

Reasoning as previously, we see that $G_2\cong K_4\cup K_1$ or G₂ is connected.

First consider the case when $G_2\cong K_4\cup K_1$. Let v₅ be the isolated vertex of G₂ and let $V(K_4)=\{v_6,v_7,v_8,v_9\}$. If $|N(v_5)\cap V(C)|=2$, then, by Fact 2, we have $m_1\le 5$, and so $m(〈\{v_1,v_2,v_3,v_4,v_5\}〉)\le 7$. If $|N(v_5)\cap V(C)|\le 1$, then, as $m_1\le 6$, we have $m(〈\{v_1,v_2,v_3,v_4,v_5\}〉)\le 7$. As $N(V(K_4))\cap V(C)=m_R-m_2-m(〈\{v_1,v_2,v_3,v_4,v_5\}〉)$, we see that $|N(V(K_4))\cap V(C)|\ge 16-6-7=3$. If $|N(u)\cap V(C)|=2$ for some $u\in V(K_4)$, then, by Fact 4, we have $|N(V(K_4))\cap V(C)|=2$, which is a contradiction. Thus, every vertex of K₄ is adjacent to at most one vertex of C. As $|N(V(K_4))\cap V(C)|\ge 3$ and $|V(K_4)|=4$, we see that at least three vertices of K₄ are adjacent to exactly one vertex of C. By Fact 5, at least three vertices of K₄ are adjacent to the same vertex of C, say v₁. As $C_4\subseteq K_4$, the graph G₂ contains a 4-cycle $C\prime$ such that $|N(C\prime )\cap \{v_1\left\}\right|\ge 3$, which contradicts Fact 1.

Next, consider the case when G₂ is connected. If $|N(v_i)\cap V(C)|=2$ for some $i\in \{5,\dots ,9\}$, then $|N(V(G_2))\cap V(C)|=2$, and so $m_R=m_1+m_2+m_3\le 6+6+2=14$, which is a contradiction. Thus, $|N(v_i)\cap V(C)|\le 1$ for $i=5,\dots ,9$. As $m_R\ge 16,m_1\le 6$ and $m_2=6$, we see that $m_3\ge 4$. Thus, we see that at least four vertices of G₂ are adjacent to exactly one vertex of C. By Fact 5, at least four vertices of G₂ are adjacent to the same vertex of C, say v₁.

Lemma 9.

G₂ contains a P₄ with both its endpoints adjacent to v₁.

Proof.

For simplicity, let $V(G_2)=\{u_1,\dots ,u_5\}$. If $\Delta (G_2)\le 2$, then $m_2\le 5$, which is a contradiction. Thus, $\Delta (G_2)\ge 3$.

First consider the case when $\Delta (G_2)=3$. Suppose u₁ is a vertex of maximum degree in G₂, and suppose, without loss of generality, that $N_{G_2}(u_1)=\{u_2,u_3,u_4\}$. If $|N(v_5)\cap N(u_1)|\ge 2$, then we have a 4-cycle $C\prime$ in G₂ such that $|N(C\prime )\cap \{v_1\left\}\right|\ge 3$, which contradicts Fact 1. Thus, v₅ is adjacent to exactly one vertex of $N(u_1)$ and nonadjacent to u₁. As $m_2=6$, the graph $〈\{v_1,v_2,v_3,v_4\}〉\cong K_4-e$. As $C_4\subseteq K_4-e$, the graph G₂ contains a 4-cycle $C\prime$ such that $|N(C\prime )\cap \{v_1\left\}\right|\ge 3$, which contradicts Fact 1.

Next consider the case when $\Delta (G_2)=4$. Suppose u₁ is a vertex of maximum degree in G₂, and suppose, without loss of generality, that $N_{G_2}(u_1)=\{u_2,u_3,u_4,u_5\}$. As $m_2=6$, the graph $〈N(u_1)〉$ contains exactly two edges.

First consider the case when these two edges are adjacent, i.e. suppose u_i is adjacent to u_j and u_k where i, j and k are distinct integers in the set $\{2,3,4,5\}$. Then $C\prime :=u_1,u_j,u_i,u_k,u_1$ is a 4-cycle in G₂ such that $|N(C\prime )\cap \{v_1\left\}\right|\ge 3$, which contradicts Fact 1.

Next consider the case when these two edges are nonadjacent, i.e. suppose $u_i{u}_j$ and $u_k{u}_{\mathcal{l}}$ are edges with $\{i,j,k,\mathcal{l}\}=\{2,3,4,5\}$. If u_i is not adjacent to v₁, then $u_j,u_1,u_k,u_{\mathcal{l}}$ is a P₄ with both endpoints adjacent to v₁. If u_j is not adjacent to v₁, then $u_i,u_1,u_k,u_{\mathcal{l}}$ is a P₄ with both endpoints adjacent to v₁. If u_k is not adjacent to v₁, then $u_i,u_j,u_1,u_{\mathcal{l}}$ is a P₄ with both endpoints adjacent to v₁. If $u_{\mathcal{l}}$ is not adjacent to v₁, then $u_i,u_j,u_1,u_k$ is a P₄ with both endpoints adjacent to v₁. Lastly, if u₁ is not adjacent to v₁, then $u_i,u_j,u_1,u_k$ is a P₄ with both endpoints adjacent to v₁. □

As G₂ contains a P₄ with both its endpoints adjacent to v₁, we see that v₁ followed by the path of order four followed by v₁ is a 5-cycle of G_R, which is a contradiction.

Subcase (iv): $m_2=7$

Reasoning as before, we see that G₂ is connected. If $|N(v_i)\cap V(C)|=2$ for some $i\in \{5,\dots ,9\}$, then $|N(V(G_2))\cap V(C)|=2$, and so $m_R=m_1+m_2+m_3\le 6+7+2=15$, which is a contradiction. Thus, $|N(v_i)\cap V(C)|\le 1$ for $i=5,\dots ,9$. As $m_R\ge 16,m_1\le 6$ and $m_2=7$, we see that $m_3\ge 3$. Thus, we see that at least three vertices of G₂ are adjacent to exactly one vertex of C. By Fact 5, at least three vertices of G₂ are adjacent to the same vertex of C, say v₁.

If G₂ is C₄-free, then, by Theorem 3, $$\text{ex}(|V(G_2)|,C_4)\le \frac{5}{4}(1+\sqrt{4(5)-3})\approx \mathrm{6.4.}$$

As $m_2\ge 7$, we may assume G₂ has a 4-cycle. For simplicity, assume $V(G_2)=\{u_1,u_2,u_3,$ $u_4,u_5\}$ where $u_1,u_2,u_3,u_4,u_1$ (say) forms a 4-cycle $C\prime$.

As G₂ is connected, vertex u₅ is adjacent to some vertex of $C\prime$, say u₃. To avoid a 5-cycle, u₅ is not adjacent to u₂ or u₄. So, possibly u₅ is adjacent to u₁.

First consider the case when u₅ is adjacent to only u₃. Then, as $m_2=7$, we see that $〈\{u_1,\dots ,u_4\}〉\cong K_4$. Moreover, as $m_3\ge 3$, vertex v₁ is adjacent to at least two vertices of the clique of order 4, resulting in a 5-cycle of G_R, which is a contradiction.

Next consider the case when u₅ is adjacent to both u₁ and u₃. To avoid the 5-cycle $u_5,u_1,u_4,u_2,u_3,u_5$, we see that u₂ is not adjacent to u₄. As $m_2=7$, it then follows that u₁ is adjacent to u₃.

If u₅ is not adjacent to v₁, then $|N(C\prime )\cap \{v_1\left\}\right|\ge 3$, which contradicts Fact 1. Thus, v₁ is adjacent to u₅. If v₁ is not adjacent to u₂, then the 4-cycle $C″=u_1,u_4,u_3,u_5,u_1$ has $|N(C″)\cap \{v_1\left\}\right|\ge 3$, which contradicts Fact 1. Thus, v₁ is adjacent to u₂. But then $v_1,u_2,u_1,u_3,u_5,v_1$ is a 5-cycle of G_R, which is a contradiction.

Case 2.

$\mathcal{l}=6$.

As G_R does not contain any 5-cycles, the pairs of vertices $v_1{v}_3,v_1{v}_5,v_2{v}_4,v_2{v}_6,v_3{v}_5,v_4{v}_6$ are not in G_R, and so $m(G_1)\le 9$.

If $|N(v_i)\cap V(C)|\le 1$ for all i = 7, 8, 9, then $m_R\le 9+3+3=15$, which is a contradiction. Assume, without loss of generality, that $|N(v_7)\cap V(C)|\ge 2$ and that v₇ is adjacent to v₁. Note that v₇ cannot be adjacent to either v₂ or v₆, since otherwise we obtain a cycle of length 7. In order to avoid the 5-cycle $v_7,v_1,v_6,v_5,v_4,v_7$, we see that v₇ is not adjacent to v₄. Thus, $N(v_7)\cap \{v_2,v_4,v_6\}=\varnothing$, and so $N(v_7)\cap V(C)\subseteq \{v_1,v_3,v_5\}$.

If $N(v_i)\cap V(C)=\varnothing$ for j = 8, 9, then $m_R\le 9+3+3=15$, which is a contradiction. Thus $N(v_i)\cap C\ne \varnothing$ for some $i\in \{8,9\}$.

Subcase (i): $N(v_i)\cap \{v_1,v_3,v_5\}\ne \varnothing$ for some $i\in \{8,9\}$. As before, $N(v_i)\cap \{v_2,v_4,v_6\}=\varnothing$. But then $H=〈\{v_2,v_4,v_6,v_7,v_i\}〉-\{v_7,v_i\}$ is a 5-clique with an edge removed in ${\overline{G}}_R$. At most two nonadjacent edges of H are not in G_B. Thus, by Lemma 5, the subgraph induced by $\{v_2,v_4,v_6,v_7,v_i\}$ in G_B contains a 5-cycle, which is a contradiction.

Subcase (ii): $N(v_i)\cap \{v_1,v_3,v_5\}=\varnothing$ for i = 8, 9. In this case, $H=〈\{v_1,v_3,v_5,v_8,v_9\}〉-\{v_8,v_9\}$ is a 5-clique with an edge removed in ${\overline{G}}_R$. Again, at most two nonadjacent edges of H are not in G_B. Thus, by Lemma 5, the subgraph induced by $\{v_1,v_3,v_5,v_8,v_9\}$ in G_B contains a 5-cycle, which is a contradiction.

Before proceeding further, we establish the following useful Lemma.

Lemma 10.

Suppose $S=v_1,v_2,\dots ,v_7,v_1$ is a 7-cycle of G_R, then $m(〈S〉)\le 9$.

Proof.

To avoid a 5-cycle in G_R, none of the vertex pairs $v_1{v}_4,v_1{v}_5,v_2{v}_5,v_2{v}_6,v_3{v}_6,v_3{v}_7,v_4{v}_7$ occur as edges of G_R.

Suppose v₁ and v₃ are adjacent in G_R. To avoid the 5-cycle $v_1,v_6,v_5,v_4,v_3,v_1$, we see that v₁ is not adjacent to v₆. To avoid the 5-cycle $v_1,v_3,v_4,v_6,v_7,v_1$, we see that v₄ is not adjacent to v₆. To avoid the 5-cycle $v_1,v_3,v_4,v_5,v_7,v_1$, we see that v₅ is not adjacent to v₇. To avoid the 5-cycle $v_1,v_3,v_5,v_6,v_7,v_1$, we see that v₃ is not adjacent to v₅. If v₂ is adjacent to both v₄ and v₇, then $v_2,v_4,v_5,v_6,v_7,v_2$ is a 5-cycle, which is a contradiction. Hence, at most one of the pairs $v_2{v}_7$ or $v_2{v}_4$ is an edge of G_R. Thus, if v₁ and v₃ are adjacent, then at most one of $v_2{v}_7$ or $v_2{v}_4$ is an edge of G_R, whence $m(〈S〉)\le 7+2=9$.

We may therefore assume that v₁ is not adjacent to v₃. Similarly, we may assume that none of the pairs $v_2{v}_4,v_3{v}_5,v_4{v}_6,v_5{v}_7,v_1{v}_6,v_2{v}_7$ are edges of G_R. In this case, $m(〈S〉)\le 7$. □

Case 3.

$\mathcal{l}=7$.

By Lemma 10, we have $m_1\le 9$. As $m_2\le 1$ and $m_R\ge 16$, we see that $m_3\ge 6$. Thus, either v₈ or v₉ is adjacent to at least three vertices of C. Without loss of generality, assume v₈ is adjacent to at least three vertices of C. Moreover, suppose without loss of generality, that v₈ is adjacent to v₁. To avoid an 8-cycle, we see that v₈ is not adjacent to both v₂ and v₇. To avoid the 5-cycle $v_8,v_1,v_7,v_6,v_5,v_8$, we see that v₅ is not adjacent to v₈. To avoid the 5-cycle $v_8,v_1,v_2,v_3,v_4,v_8$, we see that v₄ is not adjacent to v₈. Thus, v₈ must be adjacent to both v₃ and v₆, and we obtain the 5-cycle $v_8,v_3,v_4,v_5,v_6,v_8$, which is a contradiction. Thus, this case cannot occur.

Lemma 11.

Suppose $T=v_1,v_2,\dots ,v_8,v_1$ is an 8-cycle of G_R and consider three consecutive vertices u, v, w of T. If u and w adjacent, then $m(〈T〉)\le 12$.

Proof.

Assume u = v₁ and w = v₃ are adjacent. To avoid the 5-cycle $v_2,v_4,v_3,v_1,v_8,v_2$, we see that at most one of the pairs $v_2{v}_4$ or $v_2{v}_8$ occurs as an edge in G_R. To avoid the 5-cycle $v_2,v_3,v_1,v_8,v_7,v_2$, we see that v₂ is not adjacent to v₇. To avoid the 5-cycle $v_2,v_3,v_4,v_5,v_6,v_2$, we see that v₂ is not adjacent to v₆. To avoid the 5-cycle $v_2,v_5,v_4,v_3,v_1,v_2$, we see that v₂ is not adjacent to v₅. By Lemma 10, we have that $m(〈V(T)-\{v_2\}〉)\le 9$, whence $m(〈T〉)=m(〈V(T)-\{v_2\}〉)+{\mathrm{deg}}_{G_R}(v_2)\le 9+3 = 12$. □

Case 4.

$\mathcal{l}=8$.

As G_R does not contain any 5-cycles, the pairs $v_1{v}_5,v_2{v}_6,v_3{v}_7$ and $v_4{v}_8$ are not edges of G_R.

Lemma 12.

Suppose u, v, w are three consecutive vertices of C. Then u is not adjacent to w.

Proof.

Suppose u, v, w are three consecutive vertices of C with u adjacent to w. Without loss of generality, assume u = v₁ and that w = v₃. By Lemma 11, we have $m_1\le 12$, and so v₉ is adjacent to at least four vertices of C.

Suppose v₉ is adjacent to vertex v₁. To avoid a 9-cycle, v₉ is not adjacent to both v₂ and v₈. Note that vertex v_i (i = 4, 5, 6) is the endpoint of a path P₄ having v₁ as its other endpoint. Thus, to avoid a 5-cycle, vertex v₉ is not adjacent to any of the vertices v₄, v₅ or v₆. But then vertex v₉ is only possibly adjacent to the additional vertices v₃ and v₇, which implies that v₉ is adjacent to at most three vertices of C, which is a contradiction. Thus, v₉ is not adjacent to v₁. By symmetry, v₉ is not adjacent to v₃.

Suppose v₉ is adjacent v₇. To avoid 9-cycles, v₉ is not adjacent to both v₆ and v₈. But then v₉ is adjacent to v₂, v₄ and v₅, resulting in a 9-cycle, which is a contradiction. Thus, v₉ is not adjacent to v₇.

If v₉ is adjacent to v₅, then, to avoid a 9-cycle, vertices v₄ and v₆ are not adjacent to v₉. The only additional vertices which v₉ can be adjacent to are v₂ and v₈, which implies that v₉ is adjacent to at most three vertices of C, which is a contradiction. Thus, v₉ is not adjacent to v₅.

It now follows that v₉ is adjacent to the vertices v₂, v₄, v₆ and v₈, which form the 5-cycle $v_9,v_4,v_3,v_1,v_8,v_9$, which is a contradiction.

Thus, v₁ is not adjacent to v₃. The result now follows. □

Suppose v₉ is adjacent to a vertex of C, say v₁. To avoid a 9-cycle, v₉ is not adjacent to both v₂ and v₈. Note that vertex v_i (i = 4, 6) is the endpoint of a path P₄ having v₁ as its other endpoint. Thus, to avoid a 5-cycle, vertex v₉ is not adjacent to both v₄ and v₆. By Lemma 12, we see that $\{v_2,v_4,v_6,v_8,v_9\}$ induces a 5-clique in ${\overline{G}}_R$. Thus, by Lemma 4, the subgraph induced by $\{v_2,v_4,v_6,v_8,v_9\}$ in G_B contains a 5-cycle, which is a contradiction.

Thus, v₉ is not adjacent to any vertices of C and again the subgraph induced by $\{v_2,v_4,v_6,$ $v_8,v_9\}$ in G_B contains a 5-cycle, which is a contradiction.

Case 5.

$\mathcal{l}=9$.

First consider the case when we have three consecutive vertices u, v, w on the cycle C with u adjacent to w. Without loss of generality, assume u = v₁ and w = v₃. Let $C\prime =v_1,v_3,\dots ,v_9,v_1$. To avoid the 5-cycle $v_2,v_3,v_1,v_9,v_8,v_2$, we see that v₂ is not adjacent to v₈. By symmetry, we see that v₂ is not adjacent to vertex v₅ either. To avoid the 5-cycle $v_2,v_7,v_8,v_9,v_1,v_2$, we see that v₂ is not adjacent to v₇. By symmetry, v₂ is not adjacent to v₆ either. To avoid the 5-cycle $v_3,v_1,v_9,v_2,v_4,v_3$, we see that at most one of the pairs $v_2{v}_9$ and $v_2{v}_4$ is an edge of G_R. Thus, ${\mathrm{deg}}_{G_R}(v_2)\le 3$.

Suppose $u\prime ,v\prime ,w\prime$ are three consecutive vertices of $C\prime$ such that $u\prime$ and $w\prime$ are adjacent. Then, by Lemma 11, $m(〈C\prime 〉)\le 12$, and so $m_R=m(〈C\prime 〉)+{\mathrm{deg}}_{G_R}(v_2)\le 12+3=15$, which is a contradiction.

Thus, if $u\prime ,v\prime ,w\prime$ are three consecutive vertices of $C\prime$, then $u\prime$ is not adjacent to $w\prime$. So, the pairs $v_1{v}_4,v_3{v}_5$, $v_4{v}_6,v_5{v}_7,v_6{v}_8,v_7{v}_9$, $v_1{v}_8,v_3{v}_9$ are not edges of G_R. Recall that v₂ is not adjacent to any of the vertices in the set $\{v_5,v_6,v_7,v_8\}$. To avoid the 5-cycle $v_1,v_2,v_3,v_4,v_5,v_1$, the pair $v_1{v}_5$ is not an edge. To avoid the 5-cycle $v_1,v_3,v_4,v_5,v_6,v_1$, the pair $v_1{v}_6$ is not an edge. To avoid the 5-cycle $v_3,v_4,v_5,v_6,v_7,v_3$, vertex v₃ is not adjacent to v₇. To avoid the 5-cycle $v_3,v_2,v_1,v_9,v_8,v_3$, vertex v₃ is not adjacent to v₈. To avoid the 5-cycle, $v_4,v_5,v_6,v_7,v_8,v_4$, vertex v₄ is not adjacent to v₈. To avoid the 5-cycle $v_4,v_3,v_2,v_1,v_9,v_4$, vertex v₄ is not adjacent to v₉. To avoid the 5-cycle $v_5,v_6,v_7,v_8,v_9,v_5$, vertex v₅ is not adjacent to v₉. To avoid the 5-cycle $v_6,v_9,v_1,v_2,v_3,v_6$, only one of the pairs $v_6{v}_9$ and $v_3{v}_6$ may be an edge of G_R. To avoid the 5-cycle $v_7,v_1,v_2,v_3,v_4,v_7$, only one of the pairs $v_1{v}_7$ and $v_4{v}_7$ may be an edge of G_R. Recall that at most one of the pairs $v_2{v}_9$ and $v_2{v}_4$ may be edge of G_R. The pair $v_5{v}_8$ may be an edge of G_R, and so $m(G_R)\le 10+3+1=14$, which is a contradiction.

We therefore assume that if we have three consecutive vertices u, v, w on the cycle C, then u is not adjacent to w. Thus, $v_1,v_3,v_5,v_7,v_9,v_2,v_4,v_6,v_8,v_1$ is a cycle in ${\overline{G}}_R$.

To avoid the 5-cycle $v_1,v_2,v_3,v_4,v_5,v_1$, vertex v₁ is not adjacent to v₅. To avoid the 5-cycle $v_1,v_9,v_8,v_7,v_6,v_1$, vertex v₁ is not adjacent to v₆.

Similarly, pairs $v_2{v}_6,v_2{v}_7,v_3{v}_7,v_3{v}_8,v_4{v}_8,v_4{v}_9,v_5{v}_9$ are not edges of G_R. Only an additional 9 edges may be in G_R.

We next show that v₅ and v₈ are not adjacent. Suppose, to the contrary, that v₅ and v₈ are adjacent. To avoid the 5-cycle $v_8,v_5,v_4,v_3,v_2,v_8$, we see that v₂ is not adjacent to v₈. To avoid the 5-cycle $v_3,v_9,v_8,v_5,v_4,v_3$, we see that vertex v₃ is not adjacent to v₉. To avoid the 5-cycle $v_8,v_5,v_2,v_1,v_9,v_8$, we see that vertex v₂ is not adjacent to v₅. Thus, we have ten edges in G_R so far, with only five additional edges which may be in G_R. Thus, $m_R\le 15$, which is a contradiction.

We conclude that v₅ and v₈ are not adjacent, and, by symmetry, that v₃ and v₆ are not adjacent. It now follows that $\{v_1,v_3,v_8,v_5,v_6\}$ induces a $K_5-e$ in ${\overline{G}}_R$. By Lemma 5, the subgraph induced by $\{v_1,v_3,v_8,v_5,v_6\}$ in G_B has a 5-cycle, which is a contradiction.