1 Introduction

In this paper we will follow the basic graph theory terminology and notation as prescribed by [3]. Specifically, let \(G=(V,E)\) be a graph of order n with vertex set V and edge set E. For a set \(S\subseteq V\), the subgraph induced by S in G is denoted by \(\langle S\rangle _{G} \), or just \(\langle S\rangle \) if the context is clear. For bipartite graphs \(G_1, G_2,\ldots ,G_k\), the bipartite Ramsey number \(b(G_1,G_2\), \(\ldots , G_k)\) is the least positive integer b so that any colouring of the edges of \(K_{b,b}\) with k colours will result in a copy of \(G_i\) in the ith colour for some i. The existence of all numbers \(b(G_1,G_2\), \(\ldots , G_k)\) follows from a result of Erdös and Rado [5].

If G is a bipartite graph, then \({{\mathcal {R}}}(G)\) and \({{\mathcal {L}}}(G)\) will denote the right and left partite sets of G respectively, and if \(\left| {\mathcal {R}}(G)\right| =\left| {\mathcal {L}}(G)\right| \), then G is a balanced bipartite graph. If \(G_{i}=G_{j}\) for all \(i,j\in \{1,\dots ,k\}\), then the number \(b(G_{1},G_{2},\dots ,G_{k})\) will be abbreviated as \(b_{k}(G_{1})\). In [8], it is shown that \(b_{k}(C_{4})\le k^2+k-1.\) The result is obtained by making use of the technique of bounding the edges of a \(C_{4}\)-free balanced bipartite graph, colouring the edges of a \(K_{n,n}\) with k colours, and then making sure that n is large enough to yeild a monochromatic copy of \(C_{4}\). For any integer \(s\ge 2,\) the problem of bounding the size of a \(C_{2s}\)-free bipartite graph has been considered, for example see [10]. For integers \(s,t\ge 2,\) where \(s\ne t,\) it is proved, in [11], that \(b(C_{2s},C_{2t})\ge s + t - 1.\) In this paper, our main focus will be geared towards bounding the number \(b(C_{2t_1},C_{2t_2},\ldots ,C_{2t_k})\), where \(t_{i}\) is an integer and \(2 \le t_{i}\le 4,\) for all \(1\le i\le k.\)

The open neighborhood of a vertex v in G is the set \(N_G(v) = \{u \in V \, | \, uv \in E(G)\},\) and the closed neighborhood of v is defined as \(N_G[v] =\{v\} \cup N(v)\). The degree of v is \(\deg _G(v) = |N_G(v)|\) (or \(\deg (v),\) if the context is clear). If u is a vertex of a graph G,  then we will say that u is adjacent to an edge \(e=vw \in E(G),\) if u is adjacent to both v and w. If an edge \(e=vw\) of a graph G is coloured blue, then we will say that v is a blue neighbor of w.

Let \(k\ge 0\) be any integer. If \(k\ge 1,\) then a graph with k components, each of which is isomorphic to \(C_{3},\) will be denoted by \(kC_{3}.\) If \(k=0,\) then the graph \(kC_{3}\) will denote the graph with empty vertex and edge sets.

2 Known Result

The following well known extremal result will prove to be very useful.

Theorem 1

[6] Let G be a graph of order n with no path of length \(\ell \). Then \(m \le (\ell -1)n/2\), with equality if and only if G is the disjoint union of copies of \(K_{\ell }\).

3 Main Result

Theorem 2

Let \(t_1,t_2,\ldots ,t_{k}\) be integers such that \(2 \le t_{i}\le 4,\) for all \(1\le i\le k\). Then \(b(C_{2t_1},C_{2t_2},\ldots ,C_{2t_k}) \le k(t_{1}+t_{2}+\cdots +t_{k}-k+1).\)

The proof of Theorem 2 will rely on two lemmas. The proof of these lemmas will be provided in the last section. Throughout the paper, if G is a balanced bipartite graph we will let \({\mathcal {L}}(G)=\{v_1,v_2,\ldots ,v_n\}\). In the following lemma, if \(\deg (v_{i})\le 1,\) then we set \({\deg (v_{i}) \atopwithdelims ()2} = 0\).

Lemma 3

Let s be an integer with \(2 \le s \le 4,\) and let G be a balanced bipartite graph where \(\left| {\mathcal {L}}(G)\right| \ge s\). If G is \(C_{2s}\)-free then

$$\begin{aligned} \sum _{i=1}^{n}{\deg (v_{i}) \atopwithdelims ()2} \le (s-1){n \atopwithdelims ()2}. \end{aligned}$$

If \(G=K_{n,n}\) and we colour the edges of G with k colours, then, for each vertex \(v_{i},\) we define \(\deg _{j}(v_{i})\) as the degree of \(v_{i},\) in the j’th colour. If \(\deg _{j}(v_{i})\le 1,\) then, again, we set \({\deg _{j}(v_{i}) \atopwithdelims ()2}=0\).

Lemma 4

If \(G=K_{n,n}\) and the edges of G are coloured with k colours, then

$$\begin{aligned} \sum _{i=1}^{n} \sum _{j=1}^{k}{\deg _{j}(v_{i}) \atopwithdelims ()2}\ge (n^3-kn^2)/2k. \end{aligned}$$

4 Proof of Theorem 2

Recall the statement of Theorem 2. For simplicity, let \(t=t_1+t_2+\cdots +t_k\). Let us pick \(n=k(t-k+1),\) and note that \(n > t_{i},\) for all \(1\le i \le k.\) Colour the edges of \(G=K_{n,n}\) with k colours. We may assume, that for any i, where \(2\le i\le k,\) there exists no copy of \(C_{2t_{i}}\) in the i’th colour. Hence, from Lemma 3, it follows, for all \(2\le j \le k,\) that

$$\begin{aligned} \sum _{i=1}^{n}{\deg _{j}(v_{i}) \atopwithdelims ()2} \le (t_{j}-1){n \atopwithdelims ()2}. \end{aligned}$$

From Lemma 4 we obtain the following inequality:

$$\begin{aligned} \sum _{i=1}^{n} \sum _{j=1}^{k}{\deg _{j}(v_{i}) \atopwithdelims ()2}&\ge (n^3-kn^2)/2k,\\ \sum _{i=1}^{n}{\deg _{1}(v_{i}) \atopwithdelims ()2}&\ge (n^3-kn^2)/2k-\sum _{i=1}^{n} \sum _{j=2}^{k}{\deg _{j}(v_{i}) \atopwithdelims ()2},\\ \sum _{i=1}^{n}{\deg _{1}(v_{i}) \atopwithdelims ()2}&\ge (n^3-kn^2)/2k-(t_2 + t_3 +\cdots + t_{k}-k+1){n \atopwithdelims ()2}. \end{aligned}$$

Now a monochromatic copy of \(C_{2t_{1}}\) will occur in the first colour, if, by Lemma 3, the following inequality holds:

$$\begin{aligned} \sum _{i=1}^{n}{\deg _{1}(v_{i}) \atopwithdelims ()2}&\ge (n^3-kn^2)/2k-(t_2 + t_3 +\cdots + t_{k}-k+1){n \atopwithdelims ()2}\\&>(t_{1}-1){n \atopwithdelims ()2}. \end{aligned}$$

Hence,

$$\begin{aligned} \ (n^3-kn^2)/2k-(t_2 +\cdots + t_{k}-k+1){n \atopwithdelims ()2}&>(t_{1}-1){n \atopwithdelims ()2},\\ \ (n^2-kn)/2k-(t - k)(n-1)/2&\ge 0. \end{aligned}$$

The roots of the parabola \(f(x)=(x^2-kx)/2k-(t - k)(x-1)/2\) can easily be determined as \(x=k(t-k+1)/2 \pm k\left( ((t-k+1)/2)^2-(t-k)/k\right) ^{\frac{1}{2}}\). Observe that the inequality \(\left( ((t-k+1)/2)^2-(t-k)/k\right) ^{\frac{1}{2}} < (t-k+1)/2\) holds. Our choice of \(n=k(t-k+1)\) yields \(f(n) > 0,\) and so the above inequality is satisfied. This completes the proof of Theorem 2. \(\square \)

5 Proof of Lemmas

Proof of Lemma 4

Let \(G=K_{n,n}\) and colour the edges of G with k colours. Let us consider the vertex \(v_{1}=v\). Observe that \(\sum _{j=1}^{k}\deg _{j}(v)\)=n. In order to simplify matters we will denote \(\deg _{j}(v)\) by \(d_{j}\). Hence,

$$\begin{aligned} {{\sum _{j=1}^{k}d_{j}\atopwithdelims ()2}}=\,&{n \atopwithdelims ()2}\\ =\,&(d_{1}+\cdots +d_{k})(d_{1}+\cdots +d_{k}-1)/2\\ =&\left( \sum _{j=1}^{k}d_{j}(d_{j}-1) + \sum _{i=1}^{k}\left( d_{i}\sum _{j\ne i}^{}d_{j}\right) \right) \Bigg /2. \end{aligned}$$

Now if we let \(f(d_1,d_2,\ldots ,d_k)\)=\(\sum _{i=1}^{k}(d_{i}\sum _{j\ne i}^{}d_{j}),\) then f is a function with k variables and we can, using Lagrange multipliers, maximize f subject to the constraint \(\sum _{j=1}^{k}d_{j}\)=n. Define \(g(d_1,d_2,\ldots ,d_k)=\sum _{j=1}^{k}\deg _{j}(v)-n.\) Taking partial derivatives, we obtain the following equations to be solved:

$$\begin{aligned} \ f_{d_{1}}(d_1,d_2,\ldots ,d_k)&=\lambda g_{d_{1}}(d_1,d_2,\ldots ,d_k),\\ \ f_{d_{2}}(d_1,d_2,\ldots ,d_k)&=\lambda g_{d_{2}}(d_1,d_2,\ldots ,d_k),\\ \ :\\ \ :\\ \ f_{d_{k}}(d_1,d_2,\ldots ,d_k)&=\lambda g_{d_{k}}(d_1,d_2,\ldots ,d_k),\\ \ g(d_1,d_2,\ldots ,d_k)&=0, \end{aligned}$$

where \(\lambda \) is a constant, and, for all i, \(g_{d_{i}}(d_1,d_2,\ldots ,d_k)=1\) and \(f_{d_{i}}(d_1,d_2,\ldots ,d_k)=2\sum _{j\ne i}^{}d_{j}.\) Solving yields \(d_{i}=n/k,\) for all i. So the extreme value occurs in the point \(P(n/k,\ldots ,n/k),\) and is \((k-1)n^2/k\). We can check, using some algebra, that this is a maximum value, by letting the point \(Q(n/k+\epsilon _1,\ldots ,n/k+\epsilon _k),\) where \(\epsilon _{i}\in \mathfrak {R}\) for all i,  lie on the surfaces \(f(d_1,d_2,\ldots ,d_k)\) and \(g(d_1,d_2,\ldots ,d_k)=0,\) and showing that \(f(n/k+\epsilon _1,\ldots ,n/k+\epsilon _k)\le (k-1)n^2/k.\) Hence, to conclude, we have

$$\begin{aligned}&\sum _{j=1}^{k}{d_{j} \atopwithdelims ()2} + (k-1)n^2/2k\\&\ge \left( \sum _{j=1}^{k}d_{j}(d_{j}-1) + \sum _{i=1}^{k}\left( d_{i}\sum _{j\ne i}^{}d_{j}\right) \right) \Bigg /2\\&={n \atopwithdelims ()2}. \end{aligned}$$

We can do this for every single vertex \(v_{i}\) and summing over all vertices in \({\mathcal {L}}(G),\) we obtain

$$\begin{aligned} \sum _{i=1}^{n}\sum _{j=1}^{k}{\deg _{j}(v_{i}) \atopwithdelims ()2} + (k-1)n^3/2k\ge n{n \atopwithdelims ()2}. \end{aligned}$$

Hence,

$$\begin{aligned}&\sum _{i=1}^{n}\sum _{j=1}^{k}{\deg _{j}(v_{i}) \atopwithdelims ()2}\ge (n^3-kn^2)/2k. \end{aligned}$$

This concludes the proof of Lemma 4. \(\square \)

Proof of Lemma 3

Recall the statement of Lemma 3. Before we continue, observe that the sum \(\sum _{i=1}^{n}{\deg (v_{i}) \atopwithdelims ()2}\) counts each pair of vertices in \({\mathcal {R}}(G)\) zero or more times. Consider first the case where \(s=2\). Now in the \(C_4\)-free balanced bipartite graph G,  every pair of vertices in \({\mathcal {R}}(G)\) is counted at most once in the sum \(\sum _{i=1}^{n}{\deg (v_{i}) \atopwithdelims ()2}\), since otherwise G will contain a \(C_{4}\). Hence, \(\sum _{i=1}^{n}{\deg (v_{i}) \atopwithdelims ()2}\le {n \atopwithdelims ()2}.\) We may assume, henceforth, that \(s=3\) or \(s=4\).

We will prove, by contradiction, that the stated inequality holds. So let us assume that G is \(C_{2s}\)-free and \(\sum _{i=1}^{n}{\deg (v_{i}) \atopwithdelims ()2} \ge (s-1){n \atopwithdelims ()2}+1\). Now construct a graph \(G'\) from the vertices in \({\mathcal {R}}(G)\) as follows: For each pair of vertices u and v in \({\mathcal {R}}(G),\) join u and v with a red edge if there are at most \(s-1\) vertices in \({\mathcal {L}}(G)\) adjacent to both u and v. If there are at least s vertices in \({\mathcal {L}}(G)\) adjacent to both u and v,  join u and v with a blue edge. Let B (R,  respectively) denote the set of blue (red, respectively) edges in \(G'\), whence \(E(G')=B\cup R\) and \(V(G')={\mathcal {R}}(G).\)

Define the weight of an edge \(e=uv\) of \(G'\) as the exact number of vertices in \({\mathcal {L}}(G)\) adjacent to both u and v. Denote it by W(e). Let \(E(G')=\{e'_1,\ldots ,e'_{\ell }\}\) and define \(TW(B)=\sum _{e'_{i}\in B}^{}W(e'_{i})\) and \(TW(R)=\sum _{e'_{i}\in R}^{}W(e'_{i})\). \(\square \)

Claim A: \(B\ne \emptyset \).

Proof

If each edge of \(G'\) is coloured red, then each pair of vertices in \({\mathcal {R}}(G)\) is counted at most \(s-1\) times in the sum \(\sum _{i=1}^{n}{\deg (v_{i}) \atopwithdelims ()2}\), whence \((s-1){n \atopwithdelims ()2}+1\le \sum _{i=1}^{n}{\deg (v_{i}) \atopwithdelims ()2} \le (s-1){n \atopwithdelims ()2}.\) This is clearly a contradiction. \(\square \)

Since \(G'\) has at least one blue edge, we have, by Claim A, that \(TW(B)\ge s\ge 3.\)

Claim B: \(TW(B)+TW(R)\ge (s-1){n \atopwithdelims ()2}\)+1.

Proof

Let us consider any pair of vertices \(u,v\in {\mathcal {R}}(G).\) Suppose the pair \(\{u,v\}\) is counted exactly \(i\ge 0\) times in the sum \(\sum _{j=1}^{n}{\deg (v_{j}) \atopwithdelims ()2}.\) This happens if and only if \(\{u,v\}\) occurs in the open neighborhoods of exactly i distinct vertices in \({\mathcal {L}}(G).\) Hence, the edge uv in \(G'\) has weight i,  and so the pair \(\{u,v\}\) is counted i times in the sum \(TW(B)+TW(R)\), whence \(TW(B)+TW(R)\ge \sum _{j=1}^{n}{\deg (v_{i}) \atopwithdelims ()2}\ge (s-1){n \atopwithdelims ()2}+1.\) \(\square \)

A contradiction will be obtained as follows: We will pick a vertex v in \({\mathcal {L}}(G),\) such that v is adjacent to t blue edges in \(G',\) and t is as large as possible. Let \(TW(B)\ge p,\) where \(p > 0\) is an integer. Observe that TW(B) counts the total number of vertices adjacent to blue edges. The pigeonhole principle implies that there exists a vertex \(v'\in {\mathcal {L}}(G),\) such that \(v'\) is adjacent to at least \(\left\lceil p/n \right\rceil \) blue edges. We will show that the integer p can be chosen such that \(\left\lceil p/n \right\rceil \ge t+1\), and so \(v'\) is adjacent to at least \(t+1\) blue edges, which contradicts our choice of v.

So pick \(v \in {\mathcal {L}}(G),\) such that v is adjacent to exactly t blue edges in \(G',\) and t is as large as possible. Define \(X=\{u\in {\mathcal {R}}(G) | \)For some blue edge e that is adjacent to v,  u is incident with e} and \(Y={\mathcal {R}}(G)-X,\) and set \(\left| X \right| =\alpha .\) Observe that by Claim A, \(\left| X\right| \ge 2.\) Furthermore, for any edge e of \(G',\) let \(A(e)=\{u\in {\mathcal {L}}(G) |\) u is adjacent to e}. We will refer to a path P in \(G'\) as a blue (red, respectively) path, if the edges on P are all blue (red, respectively). Let \(X'\) (\(Y',\) respectively) denote the graph with vertex set X (Y,  respectively) and edge set consisting of all the blue and red edges that have both ends in X (Y,  respectively). For the remainder of the paper we set \({n-\alpha \atopwithdelims ()2}=0\) if \(n-\alpha \le 1.\)

Case A: \(s=3.\)

Claim 1: There exists no path P of length two in \(X'\), with one edge of P being blue, and the other edge of P having weight at least 2.

Proof

Suppose, to the contrary, that \(P:x_1,x_2,x_3\) is a path in \(X',\) with edges \(e_1=x_1x_2\) and \(e_2=x_2x_3\), such that \(W(e_1)\ge 2\) and \(e_2\) is blue. Recall that v is adjacent to every vertex on P. As \(W(e_{2})\ge 3\) and \(W(e_{1})\ge 2,\) we can choose, without loss of generality, vertices \(v_{1}\in A(e_1)-\{v\}\) and \(v_{2}\in A(e_2)-\{v,v_1\}\). The vertices \(v,x_1,v_1,x_2,v_2,x_3\) form a \(C_6\) in G,  a contradiction. \(\square \)

Claim 2: For every red edge e of \(X',\) we have that \(W(e)=1\).

Proof

Suppose, to the contrary, that for some red edge \(e=x_1x_2\) of \(X',\) \(W(e)=2.\) Now since each vertex in X is incident with a blue edge which is adjacent to v,  we have that there exists a vertex \(x_3\) in \(X-\{x_1,x_2\}\), such that \(e_{1}=x_{2}x_{3}\) is a blue edge in \(X'\). Obviously, the path \(P:x_1,x_2,x_3\) has the forbidden property described in Claim 1, and P lies in \(X'\). By Claim 1, we obtain a contradiction. \(\square \)

By Claim 2 we have, for every red edge e of \(X',\) that \(A(e)=\{v\}\).

Claim 3: Let \(y\in Y\) and, for distinct vertices \(x_1,x_2\in X,\) consider the edges \(e_1=yx_1\) and \(e_2=yx_2.\) If \(W(e_1)\ge 2\), then \(W(e_2)\le 1\).

Proof

We consider the edge \(e_3=x_1x_2\), in \(X'\). Assume that \(W(e_1)\ge 2\) and \(W(e_2)\ge 2\).

Case 1: \(e_3\) is blue.

As \(W(e_1)\ge 2,\) let, with no loss of generality, \(v_1\in A(e_1)-\{v\}.\) As \(W(e_2)\ge 2,\) let \(v'_1\in A(e_2)-\{v\}.\) If \(v'_1\ne v_1,\) then the vertices \(v,x_1,v_1,y,v'_1,x_2\) form a \(C_6\) in G. Hence, \(v'_1=v_1\) and so \(A(e_2)=\{v,v_1\}.\) As \(W(e_3)\ge 3,\) we let \(v_2\in A(e_3)-\{v,v_1\}\). The vertices \(v,x_1,v_2,x_2,v_1,y\) form a \(C_6\).

Case 2: \(e_3\) is red.

Since every vertex in X is incident with a blue edge in \(X',\) there exists a vertex \(x_3\in X\) such that the edge \(e_4=x_1x_3\) is blue, and \(e_4\) is adjacent to v. Pick \(v_1\in A(e_1)-\{v\}\) and \(v'_1\in A(e_2)-\{v\}.\) If \(v_1\ne v'_1,\) then, we have, once again, that the vertices \(v,x_1,v_1,y,v'_1,x_2\) form a \(C_6\) in G. Hence, \(v_1=v'_1\) and so \(A(e_2)=\{v,v_1\}.\) Let \(v_2\in A(e_4)-\{v,v_1\}.\) The vertices \(v,x_3,v_2,x_1,v_1,y\) form a \(C_6\). \(\square \)

Now, by our Claims, we have that the blue edges in \(X'\) form a perfect matching in \(X'.\) Furthermore, for each red edge e in \(X'\), \(W(e)=1\). Thus, \(\alpha =2t.\) Now each red edge in \(Y'\) can have a weight of at most 2. So the total weight of red edges in \(Y'\) is at most \(2{n-\alpha \atopwithdelims ()2}.\) The total weight of red edges in \(X'\) is at most \({2t \atopwithdelims ()2}-t.\) Consider an arbitrary vertex \(y\in Y,\) and all the edges between y and the vertices in X. By Claim 3, at most one of these edges can have weight at least two. Hence, the total weight of the red edges that have one end in X and the other end in Y,  is at most \((2t+1)(n-\alpha ).\) Hence, \(TW(R)\le {2t \atopwithdelims ()2}-t+(2t+1)(n-2t)+2{n-2t \atopwithdelims ()2}\). Note that \(2t\le n.\) Thus,

$$\begin{aligned} TW(B)&\ge 2{n \atopwithdelims ()2}+1-TW(R),\\&=2\left( {n-2t \atopwithdelims ()2}+{2t \atopwithdelims ()2}+2t(n-2t)\right) +1-TW(R),\\&\ge (t+1)n+n(t-2)-t(2t-2)+1,\\&\ge tn+1. \end{aligned}$$

Note that if we set \(p=tn+1,\) we have \(\left\lceil p/n \right\rceil =t+1,\) and so the desired result is obtained. \(\square \)

Case B: \(s=4.\)

Claim 1: There exists no path P of length three in \(X',\) where exactly two edges of P are blue, and the remaining edge has weight at least two.

Proof

Let \(P:x_1,x_2,\ldots ,x_4\) be a path within \(X',\) with edges \(e_1=x_1x_2,\) \(e_2=x_2x_3\) and \(e_3=x_3x_4.\) Assume first, to the contrary, that \(e_1\) is blue, \(W(e_2)\ge 2\) and \(e_3\) is blue. As the weight of each blue edge on P is at least four, we can, without loss of generality, let \(v_2\in A(e_2)-\{v\},\) \(v_1\in A(e_1)-\{v,v_2\}\) and \(v_3\in A(e_3)-\{v,v_1,v_2\}.\) Hence, the vertices \(v,x_1,v_1,x_2,v_2,x_3,v_3,x_4\) form a \(C_8\) in G.

Let us now assume, to the contrary, and without loss of generality, that \(e_1\) is red, and that both \(e_2\) and \(e_3\) are blue. Let \(v_1\in A(e_1)-\{v\},\) \(v_2\in A(e_2)-\{v,v_1\}\) and \(v_3\in A(e_3)-\{v,v_1,v_2\}\). The vertices \(x_4,v_3,x_3,v_2,x_2,v_1,x_1,v\) form a \(C_8\) in G, a contradiction. \(\square \)

Claim 2: There exists no path P of length two in \(X'\), such that each edge of P is red and has weight at least two.

Proof

Assume, to the contrary, that \(P:x_1,x_2,x_3\) is a path of length two in \(X',\) with \(e_1=x_1x_2,\) \(e_2=x_2x_3,\) \(W(e_1)\ge 2\) and \(W(e_2)\ge 2.\)

Case 1: The edge \(e_3=x_1x_3\) is blue.

Since every vertex of \(X'\) is incident with a blue edge in \(X',\) we have that there exists a vertex \(x_4\in X,\) such that the edge \(e_4=x_2x_4\) is blue in \(X'.\) But then the path \(P:x_1,x_3,x_2,x_4\) has the forbidden property described in Claim 1, a contradiction.

Case 2: The edge \(e_3=x_1x_3\) is red.

As the vertices \(x_1\), \(x_2\) and \(x_3\) are incident with blue edges in \(X',\) we can find vertices \(x_4\), \(x_5\) and \(x_6,\) such that \(e_4=x_1x_4\), \(e_5=x_2x_5\) and \(e_6=x_3x_6\) are edges of \(X'\) that are blue. If \(x_4\ne x_5\) then we contradict Claim 1. Hence, \(x_4=x_5\) and, by symmetry, \(x_5=x_6.\) Let \(v_1\in A(e_2)-\{v\},\) \(v_2\in A(e_4)-\{v,v_1\}\) and \(v_3\in A(e_5)-\{v,v_1,v_2\}\). The vertices \(v,x_1,v_2,x_4,v_3,x_2,v_1,x_3\) form a \(C_8\) in G,  which is a contradiction. \(\square \)

Claim 3: The total weight of the red edges of \(X'\) is at most \(\alpha /2 + {\alpha \atopwithdelims ()2}\).

Proof

Note that since each vertex in X is incident with a blue edge of \(X'\), the number of blue edges in \(X'\) is at least \(\left\lceil \alpha /2 \right\rceil \). Thus, in \(X'\), there are at most \({\alpha \atopwithdelims ()2}-\alpha /2\) red edges and each red edge has weight at least one, because of v. By Claim 2, there can exist no red path of length two in \(X'\), where both edges on the path have weight at least two.

By Theorem 1, it follows that the number of red edges with weight at least two in \(X'\) is at most \(\alpha /2,\) since otherwise a red path of length two will exist, with each edge on the path having weight at least two. Furthermore, each one of the red edges of \(X'\) with weight at least two, can possibly carry a weight of three. Hence, the total weight of the red edges in \(X'\) is at most \(2\alpha /2+{\alpha \atopwithdelims ()2}-\alpha /2.\) \(\square \)

Before we continue, we need to prove some important lemmas.

Lemma 5

Let \(x_1,x_2,x_3\in X\), \(y_1,y_2\in Y\) and \(x\in \{x_1,x_3\}.\) Define the edges \(e_1=x_2y_1,\) \(e_2=xy_2,\) \(e_3=y_1y_2\) and \(e_4=x_1x_2.\) If \(W(e_1)\ge 3,\) \(W(e_4)\ge 4\) and \(W(e_2)\ge 2,\) then \(W(e_3)\le 1.\)

Proof

Let \(x_1,x_2,x_3\in X\), \(y_1,y_2\in Y\) and \(x\in \{x_1,x_3\}.\) Define the edges \(e_1=x_2y_1,\) \(e_2=xy_2,\) \(e_3=y_1y_2\) and \(e_4=x_1x_2.\) Assume that \(W(e_1)\ge 3,\) \(W(e_4)\ge 4\) and \(W(e_2)\ge 2.\) Suppose, to the contrary, that \(W(e_3)\ge 2.\) Since \(e_1\) and \(e_2\) both have high enough weight, we can let \(v_1\in A(e_2)-\{v\}\) and \(v_2\in A(e_1)-\{v,v_1\}.\)

Let us first assume that \(x=x_1\). Now pick a vertex \(v'_2\in A(e_3)-\{v\}.\) If \(v'_2\notin \{v_1,v_2\},\) then the vertices \(v,x_1,v_1,y_2,v'_2,y_1,v_2,x_2\) form a \(C_8.\) We may assume that \(A(e_3)\subseteq \{v,v_1,v_2\}.\)

Case 1: \(v\in A(e_3).\)

If \(v_2\in A(e_3),\) then let \(v_3\in A(e_4)-\{v,v_1,v_2\}\) and so the vertices \(y_2,v_2,y_1,v,x_2,v_3,x_1,v_1\) form a \(C_8.\) If \(v_1\in A(e_3),\) then let \(v_3\in A(e_4)-\{v,v_1,v_2\}\) and so the vertices \(v,x_1,v_3,x_2,v_2,y_1,\) \(v_1,y_2\) form a \(C_8.\)

Case 2: \(v\notin A(e_3).\)

As \(W(e_3)\ge 2,\) we have that \(A(e_3)=\{v_1,v_2\}\). Now let us consider the edge \(e_2\) and let \(v'_1\in A(e_2)-\{v\}.\) Suppose first that \(v'_1\notin \{v_2,v_1\}.\) Then the vertices \(v,x_2,v_2,y_1,v_1,y_2,v'_1,x_1\) form a \(C_8\). It immediately follows that \(A(e_2)\subseteq \{v,v_1,v_2\}.\) Now if \(v\in A(e_2),\) then let \(v_3\in A(e_4)-\{v,v_1,v_2\},\) and so the vertices \(v,y_2,v_1,y_1,v_2,x_2,v_3,x_1\) form a \(C_8.\) It follows that \(A(e_2)=\{v_1,v_2\}.\) Now let \(v'_2\in A(e_1)-\{v_2,v\}.\) If \(v'_2\notin \{v,v_1,v_2\},\) then the vertices \(v,x_2,v'_2,y_1,v_2,y_2,v_1,x_1\) form a \(C_8,\) whence \(A(e_1)=\{v,v_1,v_2\}.\) Let \(v_3\in A(e_4)-\{v,v_1,v_2\}.\) The vertices \(y_2,v_2,y_1,v,x_1,v_3,x_2,v_1\) form a \(C_8\).

We may assume now that \(x=x_3.\) Let \(v_3 \in A(e_4)-\{v,v_1,v_2\}.\) Suppose first that \(v_1\in A(e_3).\) The vertices \(v,x_1,v_3,x_2,v_2,y_1,v_1,x_3\) form a \(C_8.\) Hence, \(v_1 \notin A(e_3).\) If there exists a vertex \(v'_1 \in A(e_3)-\{v,v_2\},\) then the vertices \(y_2,v'_1,y_1,v_2,x_2,v,x_3,v_1\) form a \(C_8,\) a contradiction. It follows that \(A(e_3)=\{v,v_2\},\) and so the vertices \(v,x_1,v_3,x_2,v_2,y_2,v_1,x_3\) form a \(C_8,\) a contradiction.\(\square \)

Lemma 6

Let \(x_1,x_2,x_3\in X\), \(y_1\in Y\) and define the edges \(e_1=x_1y_1,\) \(e_2=x_2y_1\) and \(e_3=x_3y_1.\) If \(W(e_1)\ge 2\) and \(W(e_2)\ge 2,\) then \(W(e_3)\le 1.\)

Proof

Let \(x_1,x_2,x_3\in X\), \(y_1\in Y\) and define the edges \(e_1=x_1y_1,\) \(e_2=x_2y_1\) and \(e_3=x_3y_1.\) Assume, to the contrary, that \(W(e_1)\ge 2,\) \(W(e_2)\ge 2\) and \(W(e_3)\ge 2.\)

Case 1. There exists a vertex \(x_4\in X-\{x_1,x_2,x_3\},\) such that the edge \(e_4=x_4x_2\) is blue.

Let \(v_1\in A(e_1)-\{v\}.\) Suppose there is a \(v_2\in A(e_2)-\{v,v_1\}.\) Let \(v_3\in A(e_4)-\{v,v_1,v_2\}\) and so the vertices \(v,x_4,v_3,x_2,v_2,y_1,v_1,x_1\) form a \(C_8\). So \(A(e_2)=\{v,v_1\}.\) Suppose that there is a vertex \(v_3\in A(e_3)-\{v,v_1\}.\) Let \(v_4\in A(e_4)-\{v,v_1,v_3\},\) and so the vertices \(v,x_4,v_4,x_2,v_1,y_1,v_3,x_3\) form a \(C_8,\) whence \(A(e_3)=\{v,v_1\}.\) Let us assume now that \(v_2\in A(e_1)-\{v,v_1\}\) and let \(v_3\in A(e_4)-\{v,v_1,v_2\},\) whence the vertices \(v,x_4,v_3,x_2,v_1,y_1,v_2,x_1\) form a \(C_8.\) It follows that \(A(e_1)=\{v,v_1\}.\) Now let \(e_5=x_3x_5\) be any blue edge in \(X'.\)

Let \(v_2\in A(e_5)-\{v,v_1\}\) and \(v_3\in A(e_4)-\{v,v_1,v_2\}.\) Assume first that \(x_5=x_4.\) The vertices \(v_3,x_2,v_1,y_1,v,x_3,v_2,x_4\) form a \(C_8.\) Consider now the case where \(x_5\in X-\{x_2,x_3,x_4\}\). The vertices \(v,x_5,v_2,x_3,v_1,x_2,v_3,x_4\) form a \(C_8,\) a contradiction. We may assume, without loss of generality, that \(x_5=x_2,\) and so the vertices \(v,x_4,v_3,x_2,v_2,x_3,v_1,y_1\) form a \(C_8\) which is a contradiction.

Case 2. There exists no vertex \(x_4\in X-\{x_1,x_2,x_3\},\) such that the edge \(e_4=x_4x_2\) is blue.

Since every vertex in X is incident with a blue edge of \(X'\), we may assume, without loss of generality and by symmetry, that the edges \(e_4=x_2x_3\) and \(e_5=x_1x_2\) are blue. Let \(v_1\in A(e_1)-\{v\},\) \(v_2\in A(e_4)-\{v,v_1\}\) and \(v_3\in A(e_5)-\{v,v_1,v_2\}.\) If \(v_4\in A(e_2)-\{v,v_1,v_2,v_3\}\), then the vertices \(v,x_1,v_1,y_1,v_4,x_2,v_2,x_3\) form a \(C_8,\) whence \(A(e_2)\subseteq \{v,v_1,v_2,v_3\}.\)

Assume first that \(v\in A(e_2).\) Then v is adjacent to \(y_1\) and so the vertices \(v,x_3,v_2,x_2,v_3,x_1,v_1,\) \(y_1\) form a \(C_8\), whence \(v\notin A(e_2).\) If \(v_2\in A(e_2)\) then the vertices \(v,x_3,v_2,y_1,v_1,x_1,v_3,x_2\) form a \(C_8\). If \(v_3\in A(e_2),\) then the vertices \(v,x_3,v_2,x_2,v_3,y_1,v_1,x_1\) form a \(C_8.\) Hence, \(A(e_2)=\{v_1\}\) and this contradicts the fact that \(W(e_2)\ge 2.\) \(\square \)

Lemma 7

Let \(x_1,x_2\in X\) and \(y_1,y_2\in Y.\) Define the edges \(e_1=x_2y_1,\) \(e_2=x_1y_2,\) \(e_3=y_1y_2\) and \(e_4=x_1x_2.\) If \(W(e_1)\ge 3,\) \(W(e_4)\ge 4\) and \(W(e_2)\ge 1,\) then \(W(e_3)\le 2.\)

Proof

Let \(x_1,x_2\in X\), \(y_1,y_2\in Y\) and define the edges \(e_1=x_2y_1,\) \(e_2=x_1y_2,\) \(e_3=y_1y_2\) and \(e_4=x_1x_2.\) Suppose, to the contrary, that \(W(e_1)\ge 3\), \(W(e_2)\ge 1\) and \(W(e_3)\ge 3.\) Now choose \(v_1\in A(e_1)-\{v\}\) and \(v_2\in A(e_3)-\{v,v_1\}\).

If, without loss of generality, \(v_3\in A(e_2)-\{v,v_1,v_2\},\) then the vertices \(v,x_2,v_1,y_1,v_2,y_2,v_3,x_1\) form a \(C_8.\) We may assume that \(A(e_2)\subseteq \{v,v_1,v_2\}.\)

Let us assume first that \(v\in A(e_2).\) Let \(v_4\in A(e_4)-\{v,v_1,v_2\},\) and so the vertices \(v,x_1,v_4,x_2,v_1,y_1,v_2,y_2\) form a \(C_8.\)

Now consider the case where \(v_1\in A(e_2).\) If there exists a vertex say \(v_5\in A(e_1)-\{v,v_1,v_2\}, \) then the vertices \(v,x_2,v_5,y_1,v_2,y_2,v_1,x_1\) form a \(C_8.\) So \(A(e_1)=\{v,v_1,v_2\}.\) Let \(v_6\in A(e_4)-\{v,v_1,v_2\},\) and so the vertices \(v,y_1,v_2,y_2,v_1,x_2,v_6,x_1\) form a \(C_8\) which is a contradiction.

Lastly, we treat the case where \(v_2\in A(e_2).\) Now, if, without loss of generality, \(v_7\in A(e_3)-\{v,v_1,v_2\},\) then the vertices \(v,x_2,v_1,y_1,v_7,y_2,v_2,x_1\) form a \(C_8\), whence \(A(e_3)=\{v,v_1,v_2\}\). By letting \(v_8\in A(e_4)-\{v,v_1,v_2\},\) we see that the vertices \(v,x_1,v_8,x_2,v_1,y_1,v_2,y_2\) form a \(C_8\). \(\square \)

Lemma 8

Let \(x_1,x_2,x_3\in X\) and \(y_1\in Y\). Define the edges \(e_1=x_1x_3,\) \(e_2=x_1x_2,\) \(e_3=x_2x_3,\) \(e_4=y_1x_1\) and \(e_5=y_1x_2.\) If the edges \(e_1,e_2\) and \(e_3\) are blue, and \(W(e_4)\ge 2,\) then \(W(e_5)= 0.\)

Proof

Assume that the edges \(e_1,e_2\) and \(e_3\) are blue, and that \(W(e_4)\ge 2\) and \(W(e_5)\ge 1.\) Without loss of generality, let \(v_1\in A(e_4)-\{v\}.\) We consider first the case where v is adjacent to \(y_1.\) Let \(v_2\in A(e_2)-\{v,v_1\}\) and \(v_3\in A(e_3)-\{v,v_1,v_2\},\) and so the vertices \(v,x_3,v_3,x_2,v_2,x_1,v_1,y_1\) form a \(C_8.\) We may assume that v is not adjacent to \(y_1\) and so \(v\notin A(e_5)\) and \(v\notin A(e_4).\)

Let us assume first that there is a vertex, say \(v_2\), such that \(v_2\in A(e_5)-\{v_1\}.\) Also observe that \(v\ne v_2.\) Without loss of generality, let \(v_3\in A(e_3)-\{v,v_1,v_2\}.\) The vertices \(v,x_3,v_3,x_2,v_2,y_1,v_1,x_1\) form a \(C_8.\) Hence, \(A(e_5)=\{v_1\}.\) The fact that \(W(e_4)\ge 2\) and v is not adjacent \(y_1,\) implies that we may let \(v_2\in A(e_4)-\{v_1\}.\) By letting \(v_3\in A(e_3)-\{v,v_1,v_2\},\) the vertices \(v,x_1,v_2,y_1,v_1,x_2,v_3,x_3\) form a \(C_8.\) \(\square \)

Lemma 9

Let \(x_1,x_2,x_3\in X\), \(y_1,y_2\in Y\) and \(x\in \{x_1,x_3\}\). Define the edges \(e_1=y_1x_2,\) \(e_2=xy_2,\) \(e_3=y_1y_2\) and \(e_4=x_1x_2\). If the edge \(e_4\) is blue, \(W(e_1)\ge 2\) and \(W(e_2)\ge 2,\) then \(W(e_3)\le 2.\)

Proof

Suppose that the edge \(e_4\) is blue, \(W(e_1)\ge 2\) and \(W(e_2)\ge 2.\) Assume, to the contrary, that \(W(e_3)\ge 3.\) Let \(v_1\in A(e_1)-\{v\}\) and \(v_2\in A(e_3)-\{v,v_1\}.\) If \(v_3\in A(e_2)-\{v,v_1,v_2\},\) then the vertices \(v,x_2,v_1,y_1,v_2,y_2,v_3,x\) form a \(C_8,\) a contradiction. Hence, \(A(e_2)\subseteq \{v,v_1,v_2\}\). Assume first that \(v\in A(e_2).\) Let, without loss of generality, \(v_4\in A(e_4)-\{v,v_1,v_2\}.\) The vertices \(v,x_1,v_4,x_2,v_1,y_1,v_2,y_2\) form a \(C_8,\) which is a contradiction.

It follows that \(A(e_2)=\{v_1,v_2\}.\) Note that since \(v_1\in A(e_2),\) we have that \(v_1\) is adjacent to \(y_2.\) Now, without loss of generality, suppose that there is a vertex \(v_3\in A(e_1)-\{v,v_1,v_2\}.\) The vertices \(v,x_2,v_3,y_1,v_2,y_2,v_1,x\) form a \(C_8,\) a contradiction. So \(A(e_1)\subseteq \{v,v_1,v_2\}.\) Let \(v_3\in A(e_4)-\{v,v_1,v_2\}.\)

Now if \(v\in A(e_1),\) then the vertices \(v,x_1,v_3,x_2,v_1,y_2,v_2,y_1\) form a \(C_8,\) a contradiction. Hence, \(A(e_1)=\{v_1,v_2\}.\)

Assume first that \(x=x_3.\) Observe that \(x_3\) is adjacent to both \(v_1\) and \(v_2\), since \(A(e_2)=\{v_1,v_2\}\). The vertices \(x_1,v_3,x_2,v_2,y_2,v_1,x_3,v\) form a \(C_8.\) Hence, \(x=x_1.\) Observe that \(x_1\) is adjacent to both \(v_1\) and \(v_2\), since \(A(e_2)=\{v_1,v_2\}\). Assume first that there is a vertex \(v_4\in A(e_3)-\{v,v_1,v_2\}.\) The vertices \(v,x_1,v_2,y_1,v_4,y_2,v_1,x_2\) form a \(C_8\). Hence \(A(e_3)=\{v,v_1,v_2\},\) and the vertices \(v_3,x_1,v,y_1,v_2,y_2,v_1,x_2\) form a \(C_8\), a contradiction. \(\square \)

Lemma 10

\(t\le \alpha -1.\)

Proof

Let \(G''\) be the graph with vertex set X,  and edge set comprising only of blue edges. Observe that \(n(G'')=\alpha \) and \(\left| E(G'')\right| =t.\) By Claim 1, X has no blue path of length 3,  and so, we have, by Theorem 1, that \(t\le \alpha . \) So let us assume that \(\alpha =t.\) Theorem 1 also implies, for some positive integer \(k>0,\) that \(G''=kC_3\). Let C be any arbitrary \(C_3\) component of \(G''\), with vertices labeled \(x_1,x_2\) and \(x_3\). If \(\left| X\right| >3,\) then let \(C'\) be a \(C_3\) component of \(G'',\) with vertices labeled \(x'_1,x'_2\) and \(x'_3,\) such that \(C\ne C'\). In addition, define the edges \(e_1=x_1x_2,\) \(e_2=x_2x_3\) and \(e_3=x_1x_3.\) Likewise, let \(e'_i=x'_ix'_{i+1},\) for \(i\in \{1,2\},\) and \(e'_3=x'_1x'_3.\)

Observation

If \(\left| X\right| >3,\) then \((A(e_1)-\{v\})\cap (A(e'_1)-\{v\})=\emptyset .\)

Proof

Suppose \(G''\) has two blue \(C_3\) components. We claim that \((A(e_1)-\{v\})\cap (A(e'_1)-\{v\})=\emptyset .\) Let \(v_3\in (A(e_1)-\{v\})\cap (A(e'_1)-\{v\}).\) Without loss of generality, let \(v_1\in A(e_1)-\{v,v_3\}\) and \(v_2\in A(e'_1)-\{v,v_1,v_3\}\). The vertices \(v,x_1,v_1,x_2,v_3,x'_1,v_2,x'_2\) form a \(C_8,\) a contradiction. We may conclude that \((A(e_1)-\{v\})\cap (A(e'_1)-\{v\})=\emptyset .\) \(\square \)

Our observation implies that no vertex in \({\mathcal {L}}(G)-\{v\}\) can be adjacent to two blue edges that lie in different \(C_3\) components of \(G''\). Hence, if \(\left| X\right| >3\), then \(\left( \bigcup _{i=1}^{3}A(e_i)\right) \cap \left( \bigcup _{i=1}^{3}A(e'_i)\right) -\{v\}=\emptyset .\) Furthermore, note that \(\left| \bigcup _{i=1}^{3}A(e_i)-\{v\}\right| \ge 3.\) Let us assume first that \(\alpha =n.\) If \(\left| X\right| >3,\) then we can apply our observation to any two arbitrary \(C_3\) components of \(G'',\) and, for each edge \(e\in E(G''),\) count the number of elements in \(A(e)-\{v\},\) and deduce that \(\left| {\mathcal {L}}(G)\right| \ge n+1,\) which is impossible. By the same argument, if \(\left| X\right| =3,\) then \(\left| {\mathcal {L}}(G)\right| \ge n+1,\) which is impossible. We may assume that \(\alpha \le n-1.\)

Let \(y_1\in Y.\) Now, by Lemma 8, the weight of all the red edges between the vertex \(y_1\) and the vertices of C is at most three, and so the weight of all red edges between X and Y is at most \(\alpha (n-\alpha ).\) To avoid contradicting Claim 1, we have that the total weight of a red edge between two vertices in X is exactly one (because of v), and so the total weight of the red edges in \(X'\) is at most \({\alpha \atopwithdelims ()2}-\alpha .\) Lastly, the total weight of red edges in Y can be at most \(3{n-\alpha \atopwithdelims ()2}.\) Hence, \(TW(R)\le {\alpha \atopwithdelims ()2}-\alpha + \alpha (n-\alpha ) + 3{n-\alpha \atopwithdelims ()2}\) and so the fact that \(\alpha \le n-1,\) implies that

$$\begin{aligned} TW(B)&\ge 3{n \atopwithdelims ()2}+1-TW(R),\\&=3\left( {n-\alpha \atopwithdelims ()2}+{\alpha \atopwithdelims ()2}+\alpha (n-\alpha )\right) +1-TW(R),\\&\ge \alpha (\alpha -1)+2\alpha n -2\alpha ^2+1+\alpha ,\\&\ge 2\alpha n -\alpha (n-1)+1,\\&=tn+1+\alpha . \end{aligned}$$

Note that if we set \(p=tn+1+\alpha ,\) we have \(\left\lceil p/n \right\rceil \ge t+1,\) and so the desired result is obtained.\(\square \)

Lemma 11

\(\alpha \le n-2.\)

Proof

Let \(G''\) be the graph with vertex set X and edge set comprising only of blue edges. Observe, once again, that \(n(G'')=\alpha \) and \(\left| E(G'')\right| =t.\)

Claim 4. If \(t=\alpha -1,\) then there exists integers \(k\ge 0\) and \(\ell \ge 1\) such that \(G''=kC_3\cup K_{1,\ell },\) and the total weight of all the red edges of \(X'\) is at most \({\alpha \atopwithdelims ()2}-\alpha +3\).

Proof

Assume that \(t=\alpha -1.\) We will first prove the first part of the claim. Suppose that \(G''\) has a vertex w of degree at least 2. By Claim 1 we have that \(G''\) has no blue \(P_4,\) and so if \(\deg _{G''}(w)\ge 3,\) then every neighbor of w must have degree one in \(G''\). Assume now that \(\deg _{G''}(w)=2,\) and let \(N_{G''}(w)=\{x,y\}\). If \(\deg _{G''}(x)\ge 2,\) then to avoid contradicting Claim 1, we must have that \(\deg _{G''}(x)=2\), \(N_{G''}(x)=\{w,y\}\) and \(N_{G''}(y)=\{w,x\}\), whence w lies on a blue \(C_3\) component of \(G''\). It follows that \(\deg _{G''}(x)=\deg _{G''}(y)=1.\) Hence since \(t=\alpha -1\), there exists integers \(k\ge 0\) and \(\ell \ge 1\) such that \(G''=kC_3\cup K_{1,\ell }.\)

To prove the second part let us consider any red edge in \(X',\) and assume it has weight at least two. If this red edge connects two components of \(G'',\) then we will contradict Claim 1. Hence, the red edge must connect two vertices that lie on a single component C of \(G'',\) where C is a blue \(K_{1,\ell }\) and \(\ell \ge 2.\) Let us consider the central vertex w of C,  and the red edge \(e'=xy\) in C. If \(\ell =2,\) then \(e'\) has weight at most 3 and so the total weight of the red edges of \(X'\) is at most \({\alpha \atopwithdelims ()2}-\alpha +3\). If \(\ell \ge 3,\) then to avoid contradicting Claim 1, we need the weight of any red edge connecting two blue neighbors of w to be at most one. Hence, the total weight of the red edges of \(X'\) is at most \({\alpha \atopwithdelims ()2}-\alpha \)+1. \(\square \)

Case 1. \(\alpha =n.\)

By Claim 3, \(TW(R)\le {\alpha \atopwithdelims ()2}+ \alpha /2.\) Hence,

$$\begin{aligned} TW(B)&\ge 3{\alpha \atopwithdelims ()2}+1-TW(R),\\&= \alpha ^2-3\alpha /2 + 1,\\&= n(\alpha - 3/2)+1. \end{aligned}$$

If \(t\le \alpha - 3/2,\) then \(TW(B)\ge nt + 1.\) By setting \(p=tn+1,\) the desired contradiction is obtained. It follows that \(t=\alpha \) or \(t=\alpha -1.\) By Lemma 10, \(t=\alpha -1.\) By Claim 4 \(TW(R)\le {\alpha \atopwithdelims ()2} - \alpha + 3,\) whence

$$\begin{aligned} TW(B)&\ge 3{\alpha \atopwithdelims ()2}+1-TW(R),\\&= \alpha ^2-2,\\&= n(t+1)-2. \end{aligned}$$

By setting \(p=n(t+1)-2\) and observing that \(n\ge 4,\) the desired contradiction is obtained.

Case 2. \(\alpha =n-1.\)

Let \(y\in Y.\) Of all the red edges between the vertex y and the vertices of X,  we have, by Lemma 6, that at most two of these red edges can have weight at least two. It follows that the weight of the red edges between X and Y is at most \(\alpha (n-\alpha )+4(n-\alpha )\). Hence, \(TW(R)\le n+3+{n-1\atopwithdelims ()2}+(n-1)/2.\) It follows that

$$\begin{aligned} TW(B)&\ge 3{n \atopwithdelims ()2}+1-TW(R)\ge n^2 - 3n/2 - 5/2. \end{aligned}$$

If \(t\le n-3,\) then \(TW(B)\ge n(t+3/2)-5/2.\) So setting \(p=n(t+3/2)-5/2\) leads to the desired contradiction. Hence, \(t=n-2\) and so, by Claim 4 and Lemma 6, we have that \(TW(R)\le {n-1 \atopwithdelims ()2}-(n-1)+3+(n+3),\) whence

$$\begin{aligned} TW(B)&\ge 3{n \atopwithdelims ()2}+1-TW(R),\\&\ge n^2-7,\\&\ge n(t+2)-7. \end{aligned}$$

So setting \(p=n(t+2)-7\) leads to the desired contradiction. \(\square \)

Let A and B be any two disjoint vertex sets of the graph \(G'\). Let E(A, B) denote the set of red edges with one end in A,  and the other in B. We have, by Lemma 6, for every \(y_1\in Y,\) that there can be at most two red edges, between \(y_1\) and the vertices in X,  of weight at least 2. If an edge of \(G'\) is blue then we will interpret it as having a red weight of 0. We partition Y into the following three sets:

\(Y_1=\{y\in Y |\) Only two edges in \(E(X,\{y\}),\) say \(e_1\) and \(e_2,\) have weight at least two, with \(W(e_1)=3\)}.

\(Y_2=\{y\in Y |\) Only one edge in \(E(X,\{y\}),\) say \(e_1,\) has weight at least two, with \(W(e_1)=3\)}.

\(Y_3=\{y\in Y |\) No edge in \(E(X,\{y\})\) has weight three, and at most two edges in \(E(X,\{y\})\) have weight two}.

We will estimate the maximum weight of the red edges in E(X, Y) and in \(E(\left\langle Y \right\rangle _{G'}).\) This maximum value is attained if each red edge in \(E(X,Y)\cup E(\left\langle Y \right\rangle _{G'})\) carries maximum possible weight. Let this total be denoted by q. Observe that if \(y_1\in Y_1,\) then the total weight of the red edges in \(E(\{y_1\},X)\) is at most \(\alpha +4\). Likewise, for \(y_{i}\in Y_{i},\) where \(i\in \{2,3\},\) the total weight of the red edges in \(E(\{y_{i}\},X)\) is at most \(\alpha +2\). It follows that the red edges of \(E(X,Y)\cup E(\left\langle Y \right\rangle _{G'})\) have total weight that is at most \((\alpha +4)\left| Y_1 \right| + (\alpha +2)\left| Y_2 \right| +(\alpha +2)\left| Y_3 \right| +3{n-\alpha \atopwithdelims ()2}\).

Case 1. \(Y_1\ne \emptyset .\)

Let \(y_1\in Y_1\) be a fixed vertex. Lemma 11 implies that \(Y_1\cup Y_2\cup Y_3-\{y_1\}\ne \emptyset \), and so let \(y_2\in Y_1\cup Y_2\cup Y_3-\{y_1\}\). Define \(e_3=y_1y_2\). Now let \(x_2\in X,\) such that the edge \(e_1=x_2y_1\) is red and \(W(e_1)=3\). Since \(x_2\) is incident with a blue edge in \(\left\langle X \right\rangle _{G'},\) we have that there exists a vertex \(x_1\in X-\{x_2\},\) such that \(e_4=x_1x_2\) is blue.

Consider first the case where \(y_2\in Y_2\cup Y_3\). Let \(e_2=x_1y_2.\) If \(W(e_2)\ge 1,\) then, by Lemma 7, we have that \(W(e_3)\le 2\). Hence if \(y_2\in Y_2\cup Y_3\), then observe the following: Either the edge \(e_3\) is red and has weight at most 2,  or the edge \(e_3\) is blue, or the edge \(e_2\) is red and has weight zero.

Assume now that \(y_2\in Y_1-\{y_1\}\). Let \(x\in X-\{x_2\}\) and define the edge \(e_2=xy_2.\) Choose x such that \(e_2\) has weight at least 2. This choice is possible because of how \(Y_1\) is defined. By Lemma 5, we have that \(W(e_3)\le 1\). Hence if \(y_2\in Y_1-\{y_1\},\) then observe the following: Either the edge \(e_3\) is red and has weight at most one.

Case 1.1. \(\left| Y_1 \right| \ge 3\).

Let us revisit the case where \(y_2\in Y_2\cup Y_3.\) Let \(K=E(X,\{y_2\})\cup \{y_1y_2\}\). Observe that the maximum total weight of the red edges in K is \(\alpha +2+3.\) Applying the observations mentioned in the two paragraphs before Case 1.1, we must have that the total weight of the red edges in K must be at most \(\alpha +4.\)

Now revisit the case where \(y_2\in Y_1-\{y_1\},\) and define \(K=E(X,\{y_2\})\cup \{y_1y_2\}.\) Observe that the maximum total weight of the red edges in K is \(\alpha +4+3\). Applying mentioned observations again, we have that the total weight of the red edges in K must be at most \(\alpha +5\).

Now let \(y\in Y_1-\{y_1,y_2\}.\) Assume the edge \(yy_2\) is red. Define \(K=\{yy_2\}.\) The maximum total weight of \(yy_2\) is 3. Using similar arguments as before we can apply Lemma 5, and so \(W(yy_2)\le 1.\) It is also possible for the edge \(yy_2\) to be blue, in which case it carries 0 red weight. Taking all of the above into account we get that \(q\le (\alpha +4)\left| Y_1 \right| + (\alpha +2)\left| Y_2 \right| +(\alpha +2)\left| Y_3 \right| +3{n-\alpha \atopwithdelims ()2}-2(\left| Y_1\right| -1)-2(\left| Y_1\right| -2)-\left| Y_2 \right| -\left| Y_3 \right| .\) From this it follows that \(q\le (\alpha +1)(n-\alpha )+3{n-\alpha \atopwithdelims ()2}+3.\)

It now follows, by Claim 3, that the maximum weight of the red edges of \(\left\langle X\right\rangle _{G'}\) is at most \(\alpha /2 + {\alpha \atopwithdelims ()2}\), whence \(TW(R)\le \alpha (n-\alpha )+n -\alpha + 3{n-\alpha \atopwithdelims ()2}+3+{\alpha \atopwithdelims ()2}+\alpha /2.\) This fact, together with Lemmas 10 and 11 and the relation \(\alpha \ge 2\), implies that

$$\begin{aligned} TW(B)&\ge 3{n\atopwithdelims ()2}+1-TW(R),\\&= 3\left( {\alpha \atopwithdelims ()2}+{n-\alpha \atopwithdelims ()2}+\alpha (n-\alpha )\right) +1-TW(R),\\&\ge n(\alpha -1)+3\alpha /2-2,\\&\ge nt+1, \end{aligned}$$

and so setting \(p=nt+1\) leads to the desired contradiction.

Case 1.2. \(\left| Y_1 \right| =2\).

We can follow the exact same reasoning described in Case 1.1 and deduce that \(q\le (\alpha +4)\left| Y_1 \right| + (\alpha +2)\left| Y_2 \right| +(\alpha +2)\left| Y_3 \right| +3{n-\alpha \atopwithdelims ()2}-2-\left| Y_2 \right| -\left| Y_3 \right| ,\) whence \(q \le (\alpha +1)(n-\alpha )+3{n-\alpha \atopwithdelims ()2}+4.\)

Assume first that \(\alpha =2.\) Then the total weight of the red edges in \(\left\langle X\right\rangle _{G'}\) is 0 and observe that \(0< \alpha /2 + {\alpha \atopwithdelims ()2}-1,\) whence \(TW(R)\le \alpha (n-\alpha )+n -\alpha + 3{n-\alpha \atopwithdelims ()2}+3+{\alpha \atopwithdelims ()2}+\alpha /2.\) It follows, using the same argument used in Case 1.1, that \(TW(B)\ge nt+1\) and so setting \(p=nt+1\) leads to the desired contradiction.

We may assume that \(\alpha \ge 3.\) It now follows, by Claim 3, that the maximum weight of the red edges of \(\left\langle X\right\rangle _{G'}\) is at most \(\alpha /2 + {\alpha \atopwithdelims ()2}\), whence \(TW(R)\le \alpha (n-\alpha )+n -\alpha + 3{n-\alpha \atopwithdelims ()2}+4+{\alpha \atopwithdelims ()2}+\alpha /2.\) This fact, together with Lemmas 10 and 11 and the relation \(\alpha \ge 3\), implies that

$$\begin{aligned} TW(B)&\ge 3{n\atopwithdelims ()2}+1-TW(R),\\&= 3\left( {\alpha \atopwithdelims ()2}+{n-\alpha \atopwithdelims ()2}+\alpha (n-\alpha )\right) +1-TW(R),\\&\ge n(\alpha -1)+3\alpha /2-3,\\&> nt+1, \end{aligned}$$

and so setting \(p=nt+1\) leads to the desired contradiction.

Case 1.3. \(\left| Y_1 \right| =1\).

Following the same reasoning as used earlier, we can deduce that \(q\le (\alpha +4)\left| Y_1 \right| + (\alpha +2)\left| Y_2 \right| +(\alpha +2)\left| Y_3 \right| +3{n-\alpha \atopwithdelims ()2}-\left| Y_2 \right| -\left| Y_3 \right| ,\) and so \(q \le (\alpha +1)(n-\alpha )+3{n-\alpha \atopwithdelims ()2}+3.\) By Claim 3, the maximum weight of the red edges of \(\left\langle X\right\rangle _{G'}\) is at most \(\alpha /2 + {\alpha \atopwithdelims ()2}\), whence \(TW(R)\le \alpha (n-\alpha )+n -\alpha + 3{n-\alpha \atopwithdelims ()2}+3+{\alpha \atopwithdelims ()2}+\alpha /2.\) Hence \(TW(B)\ge nt+1,\) and so setting \(p=nt+1\) leads to the desired contradiction.

We may assume that \(Y_1=\emptyset .\)

Case 2. \(Y_2\ne \emptyset .\)

Let \(y_1\in Y_2.\) By Lemma 11, we can pick a vertex \(y_2\in Y_2\cup Y_3-\{y_1\}\) and define \(e_3=y_1y_2\). Let \(x_2\in X,\) such that for the edge \(e_1=x_2y_1,\) we have that \(W(e_1)=3\). Since \(x_2\) is incident with a blue edge in \(\left\langle X \right\rangle _{G'},\) we have that there exists a vertex \(x_1\in X-\{x_2\},\) such that \(e_4=x_1x_2\) is blue. Let \(e_2=x_1y_2.\) If \(W(e_2)\ge 1,\) then, by Lemma 7, we have that \(W(e_3)\le 2.\) Hence, observe the following: Either \(e_2\) is red and has weight 0, or \(e_2\) is blue, or \(e_3\) is red and it has weight at most 2, or \(e_3\) is blue.

It now follows that \(q\le (\alpha +2)\left| Y_2 \right| + (\alpha +2)\left| Y_3 \right| +3{n-\alpha \atopwithdelims ()2}-(\left| Y_2 \right| -1)-\left| Y_3 \right| ,\) and so \(q \le (\alpha +1)(n-\alpha )+3{n-\alpha \atopwithdelims ()2}+1,\) whence \(TW(R)\le \alpha (n-\alpha )+n -\alpha + 3{n-\alpha \atopwithdelims ()2}+1+{\alpha \atopwithdelims ()2}+\alpha /2.\) By Lemmas 10 and 11, we have that

$$\begin{aligned} TW(B)&\ge 3{n\atopwithdelims ()2}+1-TW(R),\\&= 3\left( {\alpha \atopwithdelims ()2}+{n-\alpha \atopwithdelims ()2}+\alpha (n-\alpha )\right) +1-TW(R),\\&\ge n(\alpha -1)+3\alpha /2,\\&\ge nt+3. \end{aligned}$$

Setting \(p=nt+3\) leads to the desired contradiction.

We may assume that \(Y_2=\emptyset .\)

Case 3. \(Y_3\ne \emptyset .\)

By Lemma 11, choose \(y_1,y_2\in Y_3\) and let \(e_3=y_1y_2\). Let \(x_2\in X,\) and define \(e_1=x_2y_1\).

Assume first that \(W(e_1)\ge 2\). Since \(x_2\) is incident with a blue edge in \(\left\langle X \right\rangle _{G'},\) we have that there exists a vertex \(x_1\in X,\) such that \(e_4=x_1x_2\) is blue. Let \(x\in X-\{x_2\}\) and define \(e_2=xy_2.\) If \(W(e_2)\ge 2\), then, by Lemma 9, we have that \(W(e_3)\le 2.\) Hence either \(e_2\) is red and has weight at most 1, or \(e_2\) is blue, or \(e_3\) is red and has weight at most 2, or \(e_3\) is blue. It now follows that \(q\le (\alpha +2)\left| Y_3 \right| +3{n-\alpha \atopwithdelims ()2}-(\left| Y_3 \right| -1),\) and so \(q \le (\alpha +1)(n-\alpha )+3{n-\alpha \atopwithdelims ()2}+1.\)

We may assume that \(W(e_1)\le 1.\) Since \(y_1\) and \(x_2\) were chosen arbitrarily, we have, for every \(y_1\in Y_3,\) that no red edge in \(E(\{y_1\},X)\) can have weight at least 2. It now follows that \(q\le (\alpha +2)\left| Y_3 \right| +3{n-\alpha \atopwithdelims ()2}-2\left| Y_3 \right| ,\) and so \(q < (\alpha +1)(n-\alpha )+3{n-\alpha \atopwithdelims ()2}+1.\)

Taking all the facts into account, we find that \(TW(R)\le \alpha (n-\alpha )+n -\alpha + 3{n-\alpha \atopwithdelims ()2}+1+{\alpha \atopwithdelims ()2}+\alpha /2.\) By Lemmas 10 and 11, it can be deduced, once again, that \(TW(B)\ge nt+3,\) and so setting \(p=nt+3\) leads to the desired contradiction. \(\square \)