Partitioning 2-edge-coloured bipartite graphs into monochromatic cycles
Fabrício Siqueira Benevides Arthur Lima Quintino Alexandre Talon


Accelerating multipartite entanglement generation in non-Hermitian superconducting qubits
    H. H. Jen
    September 9, 2024
=========================================================================================



§ ABSTRACT 
    Given an r-colouring of the edges of a graph G, we say that it can be partitioned into p monochromatic cycles when there exists a set of p vertex-disjoint monochromatic cycles covering all the vertices of G. In the literature of this problem, an edge and a single vertex both count as a cycle.
    
    We show that for every 2-colouring of the edges of a complete balanced bipartite graph, K_n,n, it can be partitioned into at most 4 monochromatic cycles. This type of question was first studied in 1970 for complete graphs and in 1983, by Gyárfás and Lehel, for K_n,n. In 2014, Pokrovskiy, has showed that any 2-colouring of the edges of K_n,n can be partitioned into at most 3 paths. It turns out that finding monochromatic cycles instead of paths is a natural question that has also being asked for other graphs. In 2015, Schaudt and Stein have showed that at most 14 cycles are necessary.





§ INTRODUCTION



An r-colouring of a graph G is a colouring of its edges with up to r different colours. For such an r-colouring we say that the coloured graph is partitioned into p monochromatic cycles when there exist a set of p vertex-disjoint monochromatic cycles covering all the vertices of G. We are interested in the cycle partitioning number of G, that is the smallest number, _r(G), such that, for every r-colouring of G, it can be partitioned into into at most _r(G) monochromatic cycles. In the literature of this problem, an edge and a single vertex both count as a cycle.

In the 1970’s, Lehel made an influential conjecture stating that when the edges of a complete graph K_n are coloured with two colours, it can be partitioned into at most two monochromatic cycles. Łuczak, Rödl and Szemerédi <cit.> confirmed this conjecture for sufficiently large complete graphs, after preliminary work of Gyárfás <cit.>. In 2010, Bessy and Thomassé <cit.> proved it for every complete graph, with a surprisingly short proof. For fixed r, the best upper bound, to our knowledge, is _r(K_n) ≤ 100r log r, for n large enough (see <cit.>).

In the 2-colour case, if we replace cycles by paths, the problem becomes much easier. As noted by Gerencsér and Gyárfás <cit.> in 1967: the vertex set of any 2-edge-coloured complete graph can be partitioned into two paths of different colours. To prove it, take any red-blue colouring of K_n and suppose that R and B are vertex disjoint red and blue paths, with respective endpoints r and b. Let v ∉V(R)∪ V(B). If vr is red or vb is blue then we can extend R or B accordingly. Otherwise, without loss of generality rb is red and {R∪ rb ∪ bv, B-{b}} is a pair of red-blue paths covering one extra vertex. 

The general problem has also been studied for the case where the base graph G is a fair complete k-partite graph and for graphs with large minimum degree in general. We point to <cit.> for a (2016) survey and call attention to a couple of (older and newer) results.

Let us now define the basic concepts that we will use throughout this paper.


We say that a path is simple when it is the union of a blue path, v_1v_2… v_i and a red path, v_iv_i+1… v_k. We call v_i the turning point of the path. 



We say that a bipartite graph is balanced when its partition classes have the same number of vertices. 



Let G be a bipartite graph with partition classes X and Y, whose edges are coloured red and blue. The colouring on G is split when X and Y can each be partitioned into two non-empty sets, X=X_1∪ X_2 and Y=Y_1∪ Y_2, such that all edges between X_i and Y_j are red for i=j and blue for i≠ j. (Figure <ref>).



In 1983, Gyárfás and Lehel <cit.> showed that every balanced complete bipartite graph with a two-colouring that is not split contains two vertex-disjoint monochromatic paths that cover all but at most one of its vertices. This result was later extended by Pokrovskiy.


Let G be a balanced complete bipartite graph whose edges are coloured red and blue. There is a vertex-partition of G into two monochromatic paths with different colours if, and only if, the colouring on G is not split.



 Let G be a complete bipartite graph G with a split colouring of its edges into red and blue. The vertices of G cannot be partitioned into two monochromatic cycles of different colours.

 
By <Ref> (or by a very simple argument), the graph G cannot be partitioned into two paths of different colours. Therefore, it cannot be partitioned into two cycles of different colours either.


However, for split colourings the following is (trivially) true (but we include a proof for completeness).


Let G be a balanced complete bipartite graph whose edges are coloured red and blue. If the colouring on G is split, then G can be vertex-partitioned into at most 3 monochromatic cycles. Furthermore, two cycles suffice if and only if |X_1| = |Y_1| or |X_1| = |Y_2|.


Let X and Y be the partition classes of G. And X = X_1∪ X_2, Y = Y_1∪ Y_2 as in the definition of split colouring (<Ref>). We may assume without loss of generality that |X_1|≥ |Y_1|. As |X|=|Y|, we have |X_1|-|Y_1|=|Y_2|-|X_2| and, therefore, |X_2|≤ |Y_2|. Hence, G can be vertex-partitioned into a red cycle that covers all vertices in Y_1 and |Y_1| vertices in X_1, a red cycle that covers all vertices in X_2 and |X_2| vertices in Y_2 and a blue cycle that covers all the remaining vertices in X_1 and Y_2. And clearly, if |X_1| = |Y_1|, then |X_2| = |Y_2| and two cycles (of same colour) suffice.

On the contrary, suppose that two monochromatic cycles suffice. By <Ref> they must be of the same colour. Suppose, without loss of generality that both are red. Each cycle must be entirely contained in X_1∪ Y_1 or X_2∪ Y_2. And because all the sets X_1, X_2, Y_1 and Y_2 are non-empty, one cycle must cover vertices in X_1∪ Y_1 and the other in X_2∪ Y_2. And each cycle covers as many vertices in X as in Y. Therefore |X_1| = |Y_1| and |X_2| = |Y_2|. Note: similarly blue cycles suffice if and only if |X_1| = |Y_2| and |X_2| = |Y_1|.


A natural conjecture would be that every 2-colouring of a balanced bipartite graph that is not split can be partitioned into at most 2 monochromatic cycles. In <Ref> we give an example of a colouring that is not split and needs at least 3 cycles. 

For upper bounds, using the regularity method, Schaudt and Stein <cit.> showed that for every k, a 2-edge-coloured sufficiently large k-partite graph G, such that no partition class of G contains more than half of its vertices, can be partitioned into at most 14 monochromatic cycles. For k=2, they proved that this can be done with at most 12 monochromatic cycles.

Our main contribution is to reduce this number to only 4 monochromatic cycles, for any balanced bipartite graph. Also, note that our result does not require G to be large.


If G is a balanced complete bipartite graph whose edges are coloured red and blue, then G can be partitioned into at most 4 monochromatic cycles.






 §.§ An alternative short proof of Theorem <ref>


To make the results of this paper self-contained, we provide a proof for <Ref>, more direct than the original one in <cit.>. It is worth noting that a short proof of this result is also presented in <cit.> (section 4.2).




We argue that if G does not have a Hamiltonian simple path, then the colouring on G is split.

Let P=(r_s,…,r_1,x,b_1,…,b_t) be a simple path of maximum size in G, where x is its turning point and r_s and b_t are its red and blue endpoints respectively. If P is not Hamiltonian, then we have the following three cases to analyze.



  * Its endpoints belong to different partition classes. (See Figure <ref>.)



Since G is balanced, we know that there is at least one vertex that does not belong to P in each partition class. Hence, let y∉ V(P) be a vertex such that x and y belong to different partition classes. We may assume without loss of generality that the edge xy is red. Hence, the simple path (y,x,r_1,…,r_s,b_t,…,b_1) is bigger than P, a contradiction.


  * Its endpoints and its turning point belong to the same partition class. (See Figure <ref>.)



Let y∉ V(P) be a vertex that belongs to the other partition class. We may assume without loss of generality that the edge xy is red. Hence, the simple path (r_s,…,r_1,x,y,b_t,…,b_1) is bigger than P, a contradiction.


  * Its endpoints belong to the same partition class and its turning point belongs to the other. (See Figure <ref>.)



Let X and Y be the partition classes of G. In order to prove that the colouring on G is split, we shall define hereafter sets X_1, X_2, Y_1 and Y_2 satisfying all conditions of Definition <ref>. For this, we assume without loss of generality that x∈ X.

Firstly, let X_1=X∩ V(P), Y_1'=Y∩ V(P_R) and Y_2'=Y∩ V(P_B). We want to show that the edges between X_1 and Y_1' are red, whereas the edges between X_1 and Y_2' are blue. Indeed, the edge r_sx is red, since otherwise the simple path (r_1,…,r_s,x,b_1,…,b_t) would satisfy case (B), with turning point r_s. Hence, 


    for each  r_i∈ X_1 , the edge  r_ib_t  is blue,


since otherwise the simple path (r_i-1,…,r_1,x,r_s,…,r_i,b_t,…,b_1) would satisfy case (B), with turning point b_t. Now, suppose by way of contradiction that the edge r_jx is blue for some fixed r_j∈ Y_1', with 1<j<s. Hence, let y∈ X∖ V(P). Then,


    for each  r_i∈ Y_1' , the edge  yr_i  is blue,


since otherwise the simple path (y,r_i,…,r_1,x,r_s,…,r_i+1,b_1,…,b_t) would be bigger than P. In particular, we know by (<ref>) that the edge r_j-1b_t is blue and by (<ref>) that the edges yr_1 and yr_j are blue too. Hence, we see that G[V(P)∪{ y }] can be vertex-partitioned into a red path with an even size and a simple cycle whose red and blue paths also have an even size, namely into the red path (r_j+1,…,r_s) and the simple cycle whose red and blue paths are (r_1,…,r_j-1) and (r_1,y,r_j,x,b_1,…,b_t,r_j-1) respectively. Now, consider one such vertex-partition 𝒫 of G[V(P)∪{ y }] in which the size of the blue path of the simple cycle is maximum. Let (u_1,…,u_k) be the red path and (v_1,…,v_l) and (v_l,w_1,…,w_m,v_1) be respectively the red and blue paths of the simple cycle of 𝒫 (see Figure <ref>). Since all paths have an even size, we know that each path has an endpoint in each partition class of G. Without loss of generality, we may assume then that u_1 and v_1 belong to the same partition class and, therefore, that u_k and v_l belong to the other. The edges u_1v_l and u_kv_1 cannot be both blue, since then G[V(P)∪{ y }] could be vertex-partitioned into the red path (v_2,…,v_l-1) and the simple cycle (u_1,…,u_k,v_1,w_m,…,w_1,v_l), whose blue path is bigger than that of the simple cycle of 𝒫. Without loss of generality, we may assume then that the edge u_kv_1 is red. Hence, the simple path (u_1,…,u_k,v_1,…,v_l,w_1,…,w_m) is bigger than P, a contradiction. Thus, for each r_i∈ Y_1', the edge r_ix is red. Analogously, for each b_i∈ Y_2', the edge b_ix is blue. In other words, we just showed that the edges between x and Y_1' are red, whereas the edges between x and Y_2' are blue. Furthermore, we know by (<ref>) that each r_i∈ X_1 is the turning point of a simple path Q such that X_1=X∩ V(Q), Y_1'=Y∩ V(Q_R) and Y_2'=Y∩ V(Q_B), namely of the simple path Q=(r_i-1,…,r_1,x,r_s,…,r_i,b_t,…,b_1). Analogously, we know that each b_i∈ X_1 also is the turning point of a simple path with such property. Hence, we may conclude that the edges between X_1 and Y_1' are red, whereas the edges between X_1 and Y_2' are blue, which is what we wanted to show.



Now, let X_2=X∖ V(P), Y_1”={ z∈ Y∖ V(P)the edge  xz  is red} and Y_2”={ w∈ Y∖ V(P)the edge  xw  is blue}. By (<ref>), we know that for each y∈ X_2 and each r_i∈ Y_1', the edge yr_i is blue. Analogously, for each y∈ X_2 and each b_i∈ Y_2', the edge yb_i is red. For each y∈ X_2 and each z∈ Y_1”, the edge yz is blue, since otherwise the simple path (y,z,x,r_1,…,r_s,b_2,…,b_t) would be bigger than P. Analogously, for each y∈ X_2 and each w∈ Y_2”, the edge yw is red. For each z∈ Y_1” and each r_i∈ X_1, the edge r_iz is red, since otherwise the simple path (r_s,…,r_i+1,r_i-2,…,r_1,x,z,r_i,b_1,…,b_t) would satisfy case (B), with turning point z. Analogously, for each w∈ Y_2” and each b_i∈ X_1, the edge b_iw is blue. For each z∈ Y_1” and each b_i∈ X_1, the edge b_iz is red, since otherwise the simple path (r_s,…,r_1,x,z,b_i,…,b_1,b_i+2,…,b_t) would satisfy case (B), with turning point z. Analogously, for each w∈ Y_2” and each r_i∈ X_1, the edge r_iw is blue.

Thus the sets X_1, X_2, Y_1=Y_1'∪ Y_1” and Y_2=Y_2'∪ Y_2” satisfy all conditions of Definition <ref>, and so the colouring on G is split.









§ PROVING MAIN THEOREM



Thanks to <Ref>, we only have to prove <Ref> when the given colouring is not split. Our proof is self-contained apart from the following result.


Let G be a balanced complete bipartite graph whose edges are coloured red and blue. If the colouring on G is not split, then G can be vertex-partitioned into a monochromatic path and a monochromatic cycle with different colours.


We observe that the above is a corollary to <Ref>, and follows from a very short case analysis on the parity of the paths given by <Ref>. This is done in details in Section 4.1 of <cit.>.
We also note that Section 4.2 of <cit.> presents an alternative proof of <Ref> that is also short and self-contained.

In view of <Ref>, it is enough to prove the following lemma. 


Let G be a balanced complete bipartite graph whose edges are coloured red and blue. If G has a monochromatic Hamiltonian path, then G can be vertex-partitioned into at most 3 monochromatic cycles.


In fact, let H be any balanced complete bipartite graph with a two-colouring on its edges. When we apply <Ref> to H, the monochromatic cycle we obtain must be even because H is bipartite. And since H is balanced, the monochromatic path given by <Ref> is also even. So its vertices induce a balanced complete bipartite subgraph of H that contains a monochromatic Hamiltonian path.

<Ref> is best possible, in the sense that even with the extra condition that the colouring of the bipartite graph contains a Hamiltonian monochromatic path, there are 2-colourings that cannot be partitioned into 2 monochromatic cycles, as illustrated bellow.


Let G be a be a balanced complete bipartite graph on 2n vertices, with bipartition S = {x_1, …, x_n}∪{y_1,…,y_n}. Take the colouring where:


  * x_1y_1, x_2y_2 and all edges of the form x_1y_i and y_1x_i for i ≥ 3 are blue;

  * the edges x_2y_i for i ≥ 4 are blue;

  * all the other edges are red.

Then G contains a Hamiltonian red path and cannot be partitioned into two monochromatic cycles.



Since the graph induced by 3 = {x_3, …, x_n}∪{y_3,…,y_n} has all edges coloured red, there is a path P starting in x_3 and ending in y_3 and passing through all vertices of 3. The red path x_1y_2x_3Py_3x_2y_1 is a red Hamiltonian path of G.

Now we show that G cannot be partitioned into 2 monochromatic cycles. First, the vertex y_1 cannot belong to a cycle with more than two vertices: such a cycle would be blue because only one red edge is incident to y_1, and it would then contain one x_i with i ≥ 2 but such an x_i only has one incident blue edge, towards y_1, hence it could not continue further. Now, if we make a cycle with y_1 only, given the fact that the graph is bipartite, we cannot make a single cycle with all the 2n-1 remaining vertices.
Let us now assume we have a partition into two monochromatic cycles. One cycle must contain y_1 and exactly one of the x_l's. The other cycle must contain y_2, therefore it cannot be blue since only one blue edge is incident to that vertex. So it needs to be a red cycle, and then cannot contain x_1 (only one incident red edge), hence the first cycle is x_1y_1. Then this second cycle, which is red, must contain both x_2 and y_2 but x_2 has only one incident red edge in G ∖{x_1, y_1} so this is a contradiction.





Next we present the structure of the proof of <Ref>. In all that follows, we consider a balanced complete bipartite graph G whose edges are coloured red and blue and contains a red Hamiltonian path. We also consider that this colouring is not split, and we want to show that there is partition of G into at most 3 monochromatic cycles.

Our idea is to search for more structure in the above graph G. Let's say that each partition class of G has n vertices. We will label its vertices in a particular way. Then, in order to prove <Ref>, we use induction with on a parameter k, 1≤ k ≤ n, with a well chosen hypothesis. We will try to show the existence of a specific subgraph which we will define later as a blue even plait: the first k/2 vertices with even indices from both classes (of the bipartition) inducing a complete blue bipartite graph, and the same with the first k/2 vertices with odd indices. This exists for k=1, and we will show that if G cannot be partitioned into three monochromatic cycles and the induction hypothesis holds with k, then it also holds with k+1. Iterating this will give us our result, because a blue even plait shall be trivially partitioned into 2 blue cycles. The proof will mostly consists in looking at specific edges and proving that they are blue (though we also need to argue that a few edges are red), with the goal to increase the order of the blue even plait.

We split this section into two subsections. Subsection <ref> contains some preliminary results that we will use many times and help us to organise the other subsection in a concise way. Subsection <ref> is devoted to the main proof of <Ref>, which is longer. The preliminary results include a lemma with a short inductive proof which suffices to deduce a weakening of <Ref> with 4 cycles, which in turn (by the above arguments) implies a weakening of <Ref> with 5 cycles.



Let G be a balanced complete bipartite graph whose edges are coloured red and blue. If G has a monochromatic Hamiltonian path, then G can be vertex-partitioned into at most 3 monochromatic cycles.






 §.§ Preliminary structural results


Throughout the rest of this paper we deal with balanced complete bipartite graphs whose edges are coloured red and blue that have a monochromatic Hamiltonian path. Therefore, in order to avoid exhaustive repetitions, it will be convenient to establish the following convention for the order of the vertices in such a path.


A balanced complete bipartite graph with 2n vertices whose edges are coloured red and blue is a red zigzag graph when its partition classes are X={ x_1,…,x_n } and Y={ y_1,…,y_n } and the Hamiltonian path 
    P=(x_1,y_2,x_3,y_1,…,x_4,y_3,x_2,y_1)
 is red. (See Figure <ref>.)

For every k≤ n, we also define the sets:

    k   = {x_i : i≤ k}∪{y_i : i≤ k}, 
    k   = {x_i : i< k}∪{y_i : i < k}, 
    k   = {x_i : i≥ k}∪{y_i : i≥ k}, 
    k   = {x_i : i> k}∪{y_i : i> k}.

We denote by x_iPy_j the red Hamiltonian subpath of P starting from vertex x_i and ending at y_j, both end-vertices being included.





In addition to these and to other definitions that will appear later, we shall also establish some simple facts that will help us in the proofs of the main results of this section. Such facts will be just stated as remarks, since they are straightforward or can be easily checked.


Let G be a red zigzag graph with 2n vertices. Then, for i≤ n:


  * if the edge x_iy_i is red, then the subgraph G[i] has a red Hamiltonian cycle, namely (x_iPy_i). (See Figure <ref>.)
      

  * if the edge x_iy_i+2 (resp. x_i+2y_i) is red, then the subgraph G[i] can be vertex-partitioned into two red cycles, namely into the red cycle (x_i,y_i+2Px_i+2,y_i+1) (resp. (x_i+1,y_i+2Px_i+2,y_i)) and the edge-cycle (x_i+1,y_i) (resp. (x_i,y_i+1)). (See Figure <ref>.)





In the above language, proving Lemma <ref> is the same as proving that every red zigzag graph can be vertex-partitioned into at most 3 monochromatic cycles. Therefore, we see that the lemma below is a weaker version of Lemma <ref>, which allows one extra monochromatic cycle to be used. As compensation, this version gives us some additional information about the monochromatic cycles of the obtained partition.


If G is a red zigzag graph with 2n vertices, then G can be vertex-partitioned into at most t monochromatic cycles satisfying one of the following conditions.


  * t=2.

  * t=3 and the edge x_1y_1 is used in some blue cycle of the partition.

  * t=4 and the edges x_1y_1 and x_2y_2 are used in different blue cycles of the partition.




The proof is by induction on n. For n≤ 2, the graph G satisfies condition (i) trivially. For n≥ 3, we may assume that G does not satisfy condition (i), since otherwise we would be done. Hence, by Remark <ref>, we know that the edges x_1y_1, x_1y_3 and x_3y_1 are blue. Now, we apply the inductive hypothesis to the subgraph G[1]. If G[1] satisfies conditions (i) or (ii), then we may simply take the edge x_1y_1 as a blue cycle and so we see that G satisfies conditions (ii) or (iii), respectively. On the other hand, if G[1] satisfies condition (iii), then we may use the edges x_1y_1, x_1y_3 and x_3y_1 to extend the blue cycle of the partition of G[1] that uses the edge x_3y_3 and so we see that G satisfies condition (iii) as well. In any case, the result follows.


In view of the proof of Theorem <ref>, observe that the lemma above has a certain relevance by itself, since it implies that 5 monochromatic cycles are sufficient to vertex-partition any balanced complete bipartite graph whose edges are coloured red and blue, which already improves results from <cit.> (where it is proved that large balanced bipartite graphs can be partitioned into 12 cycles), with a significantly shorter proof. 

 However, Lemma <ref> is just the first step towards Theorem <ref>. The next step is to introduce some tools to prove <Ref>. We will also prove a weaker version of <Ref>, which will make the proof of <Ref> clearer.



Let G be a red zigzag graph with 2n vertices. For 2≤ k≤ n, the set k is a blue special set when the following two conditions hold:


  * the subgraph G[k-2] is either empty of has a blue Hamiltonian cycle,

  * the subgraph G[k-1] has blue Hamiltonian cycle, and

  * the subgraph G[k] has a blue Hamiltonian cycle that uses the edges x_k-1y_k-1 and x_ky_k.



Furthermore, we need the following remark.


Let G be a complete bipartite graph and C_1=(u_1,…,u_s) and C_2=(v_1,…,v_t) be two disjoint blue cycles in G, where u_1,v_1∈ X. Then u_1v_t and v_1u_s are edges of G. If those edges are both blue, then there is a blue cycle in G that passes through all edges in C_1 and C_2 except u_1u_s and v_1v_t and covers all vertices in C_1 and C_2, namely (u_1,…,u_s,v_1,…,v_t). (See Figure <ref>.)




The following lemma shows us that the existence of a blue special set in a red zigzag graph is a sufficient extra condition to make Lemma <ref> valid.


Let G be a red zigzag graph with 2n vertices. If G has a blue special set, then G can be vertex-partitioned into at most 3 monochromatic cycles.



Let k be a blue special set in G for some 2≤ k≤ n. By Definition <ref> (iii), G[k] has a blue Hamiltonian cycle.
Hence, we may assume that n > k+2, since otherwise we would be done.
By Remark <ref>(b) and Definition <ref> (iii), we may also assume that the edges x_k-1y_k+1, x_k+1y_k-1, x_ky_k+2 and x_k+2y_k are blue, since otherwise we would be done.

Now, we apply <Ref> to the subgraph G[k]. If G[k] satisfies condition (i), then we may simply take a blue Hamiltonian cycle in G[k] to obtain a good partition of G. 
By Remark <ref>, if G[k] satisfies condition (ii), then we  use the edges x_k-1y_k+1 and x_k+1y_k-1 to combine the blue cycle that uses the edge x_k+1y_k+1 from the 3-cycle partition of G[k] with the blue Hamiltonian cycle of G[k] (since it uses the edge x_k-1y_k-1), thereby obtaining a good partition of G. Observe that the previously built blue cycle also passes through the edge x_ky_k. Hence, if G[k] satisfies condition (iii), then first we do the same operation as in the previous case (using edges x_k-1y_k+1 and x_k+1y_k-1) and after that we use the edges x_ky_k+2 and x_k+2y_k to build a blue cycle in G that covers all vertices in G[k] and all vertices of two different blue cycles of the partition of G[k] (remember that the edges x_k+1y_k+1 and x_k+2y_k+2 were in different cycles of the partition). Thereby obtaining a desired partition of G. In every case, the result follows.


To prove the next lemma, it will be necessary to make a more involved analysis of the edges compared to what we did in the proofs of Lemmas <ref> and <ref>. Therefore, as a way to facilitate our work and the reader's understanding, we shall make some considerations first.


    An edge x_iy_j in a red zigzag graph is even when i and j have the same parity, i.e., when i+j is even.



 Usually, if an even edge with “low” values for its indices is red, we can then partition the edges into 3 monochromatic cycles. Otherwise if that edge is blue we can look at other edges. The fact that such an edge is blue helps us little by little to establish a nice blue structure.


Let G be a red zigzag graph with 2n vertices. For 1≤ k≤ n, the subgraph G[k] is a blue even plait when all its even edges are blue. We denote by G_k^O the subgraph of G formed by vertices of odd indices in k, and G_k^E the one formed by vertices of even indices.




Let G be a red zigzag graph with 2n vertices. If G[k] is a blue even plait, for 1 ≤ k≤ n, then G_k^O and G_k^E are complete balanced bipartite graphs whose edges are all blue. In particular, each of them is Hamiltonian, so G[k] can be partitioned into at most two monochromatic blue cycles.



A Hamiltonian path in G_k^E starting in x_i and ending in y_j is denoted x_i[E_k]y_j (note that such a path needs to start and finish on different classes of the bi-partition).

A path in G_k^E starting in x_i and ending in x_j that passes through all vertices of G_k^E except for a given y_ℓ is denoted x_i[E_k∖ y_ℓ]x_j (note that such a path needs to start and finish on the same class of the bi-partition).

We use the same notations (x_i[O_k]y_j and x_i[O_k∖ y_ℓ]x_j) for G_k^O.


Such Hamiltonian or quasi-Hamiltonian paths with specific extremities will be extensively used in the proof of <Ref>. Indeed, we will regularly be able to show that a few edges between G_k^O and G_k^E are blue too. Then by choosing carefully the end-vertices of two (quasi-)Hamiltonian paths we will be able to combine the two paths into a cycle passing through all the vertices in G_k^O ∪ G_k^E except at most two of them, helping us to get a decomposition of the red zigzag graph into at most 3 monochromatic cycles.



 §.§ Main proof



After these considerations, we may advance to our next result. As we shall see hereafter, Lemma <ref> follows almost directly from the lemma below.


Let G be a red zigzag graph with 2n vertices which cannot be vertex-partitioned into at most 3 monochromatic cycles. If the subgraph G[k] is a blue even plait for some 1 ≤ k ≤ n-2, then G[k+1] is a blue even plait as well (see Definition <ref>).



First since G cannot be vertex-partitioned into 3 monochromatic cycles, we can easily see that n ≥ 5. It is also easy to check that G[4] is a blue even plait: if the edge x_1y_1 (resp. x_2y_2) were red, then G (resp. G∖{x1_y1}) would be Hamiltonian; if the edge x_2y_2, x_1y_3 or x_3y_1 were red we could decompose G into a red cycle and one edge; x_3y_3 being red would imply a decomposition into a cycle and two paths. Now if x_2y_4 or x_4y_2 were red we  could decompose G into a red cycle and two edges; if x_4y_4 were red then we would decompose into the big red cycle using x_4y_4, the blue cycle we just showed the existence (x_1y_1x_3y_3) and the edge x_2y_2. We have just proved that the  even edges within G[4] are blue, hence  G[4] is a blue even plait as we announced. Therefore we can assume that k≥ 4, so that each of G_k^O and G_k^E have at least 4 vertices.

Also, Remarks <ref>(a) and <ref>, imply that the edge x_k+1y_k+1 is blue.

Now, suppose by way of contradiction that G[k+1] is not a blue even plait. Hence, there is some natural j less than k+1 such that j and k+1 have the same parity and at least one of the edges x_k+1y_j or x_jy_k+1 is red. We shall show that this implies that G has a blue special set, which is a contradiction by Lemma <ref>.

We divide the remainder of the proof into two cases depending on the parity of k. These cases are treated quite similarly, but at some points they are not absolutely analogous. Therefore, we will give the full details for both cases whenever necessary but we will just guide how to make the analogy whenever possible.



Case A: k is even and k≥ 4, therefore j is odd with 1 ≤ j < k ≤ n-2.


Note that some claims below will require k < n-4, but we will see that these claims are only needed if k < n-4: otherwise the proof would end before.
case




 
         
  *  If there exists 1 ≤ l ≤ k odd such that x_k+1y_l is red, then x_1y_k and x_k-1y_2 are not both blue.
         
  *  If there exists 1 ≤ l ≤ k odd such that x_ly_k+1 is red, then x_ky_1 and x_2y_k-1 are not both blue.



We will prove only (<ref>) since (<ref>) is analogous. So x_k+1y_l is red. Suppose by way of contradiction that the edges x_1y_k and x_k-1y_2 are blue (see Figure <ref>). In this case, we shall prove that k+2 is a blue special set of G. 



First, let us prove that the edge x_ky_l is blue. Indeed, otherwise we could decompose G into the red cycle (x_k,y_k+1Px_k+1,y_l) that covers k+1∪{x_k, y_l} and a blue cycle that covers k∖{x_k, y_l}. More precisely:

    y_2[E_k∖ x_k] y_k  x_1 [O_k∖ y_l] x_k-1 y_2.


Now, we can know construct a blue Hamiltonian cycle for G[k]: say 
y_k[E_k] x_k  y_l [O_k] x_1  y_k.
This is our first step towards proving that k+2 is a blue special set of G.

The edge x_k+1y_k-1 is blue, otherwise G could be vertex-partitioned into the red cycle (x_k,y_k+1Px_k+1,y_k-1) (recall that x_ky_k-1 is also an edge of P) and (similarly to above) a blue cycle that covers all vertices in k except x_k and y_k-1. 
The edge x_l+1y_k+1 is blue too, since otherwise G could similarly be vertex-partitioned into the red cycle (x_l+1,y_k+1Px_k+1,y_l) and a blue cycle that 
covers all vertices in k except x_l+1 and y_l. Therefore, we see that the subgraph G[k+1] has a blue Hamiltonian cycle: 
    C = (x_k+1 y_k+1 x_l+1[E_k] y_2  x_k-1[O_k] y_k-1 x_k+1).

By Remark <ref>(a), it follows that the edge x_k+2y_k+2 is blue.

Next, the edge x_k+2y_k is blue, otherwise G could be vertex-partitioned into the edge-cycle (x_l+1,y_k+1), the red cycle (x_k+1,y_k+2Px_k+2,y_k),  and a blue cycle that covers k∖{x_l+1, y_k}. Note that such blue cycle does not use y_k so it does not benefit from the blue edge x_1y_k but rather x_ky_l. Use edges of G_k^E to go from y_2 to x_k passing through all its vertices except x_l+1 and y_k, add edge x_ky_l go through all vertices in G_k^O finishing in x_k-1 and add the edge x_k-1y_2.
 The edge x_ky_k+2 is blue too, since otherwise G could be vertex-partitioned into the red cycle (x_k,y_k+2Px_k+2,y_k+1), the edge-cycle (x_k+1,y_k-1) and a blue cycle that covers all vertices of k∖{x_k, y_k-1} (using the edges x_1y_k and x_k-1y_2). 
 

 Hence, we see that the subgraph G[k+2] has a blue Hamiltonian cycle that uses the edges x_k+1y_k+1 and x_k+2y_k+2, which can be built by the following manner: take the blue Hamiltonian cycle C of G[k+1] that we have just built. We can require it to contain the edge x_ky_k. Then consider the cycle C' = (C - x_ky_k) + x_ky_k+2x_k+2y_k.
Therefore k+2 is a blue special set of G as needed.



The edges x_k+1y_1 and x_1y_k+1 are blue.


Suppose by way of contradiction that the edge x_k+1y_1 is red (see Figure <ref>). In this case, G can be vertex-partitioned into the red cycle (x_k+1Py_1) and the red path (x_1,y_2Px_k-1,y_k). By Claim <ref>(<ref>), with l=1, we know that the edges x_1y_k and x_k-1y_2 are not both blue. Hence, G can be vertex-partitioned into at most 3 monochromatic cycles, a contradiction. Thus, the edge x_k+1y_1 is blue. Analogously, the edge x_1y_k+1 is blue too, by Claim <ref>(<ref>). Thus, the result follows.





The edge x_k+2y_k+2 is blue.



By <Ref>, we see that the subgraph G[k+1] can be vertex-partitioned into a blue Hamiltonian cycle of G_k^E and a blue cycle that covers x_k+1, y_k+1 and all vertices in G_k^O, which can be built by the following manner: take a blue Hamiltonian cycle of G_k^O that uses the edge x_1y_1; and use the path (x_1,y_k+1,x_k+1,y_1) to extend it. Hence, by Remark <ref>(a), the result follows.


Remember that there is some odd j such that x_k+1y_j or x_jy_k+1 is red. In what remains, without loss of generality, we assume that the edge x_k+1y_j is red.

Note: with that we loose the symmetry between the sets X and Y. We have not made this assumption earlier, because we need Claim <ref> to hold regardless of which x_k+1y_j or x_jy_k+1 is red.

By <Ref>, we know that j ≠ 1, hence all the following claims will be on the assumption that 2 ≤ j. Besides, if k = n-2 then the edge x_k+2y_k+2 = x_ny_n belongs to the red path P, hence is not blue, contradicting <Ref>. Thus if k = n-2 the proof ends here. In the remainder, therefore, we have that:

    2≤ j < k ≤ n-3.

This allows us to use indices j-1 and k+3 (that we have not used it so far).


The edges x_j+1y_1 and x_2y_j+2 are blue.
 In particular, when j=k-1, this means that x_ky_1 and x_2y_k+1 are blue.


Suppose by way of contradiction that the edge x_j+1y_1 is red (see Figure <ref>). In this case, G can be vertex-partitioned into the red cycle (x_k+1Px_j+1, y_1Py_j) and the red path (x_1,y_2Px_k-1,y_k). By Claim <ref>(<ref>), we know that the edges x_1y_k and x_k-1y_2 are not both blue. Hence, we see that G can be vertex-partitioned into at most 3 monochromatic cycles, a contradiction. Thus, the edge x_j+1y_1 is blue.



Now, suppose by way of contradiction that the edge x_2y_j+2 is red (see Figure <ref>). In this case, the edge x_1y_k is blue, since otherwise G could be vertex-partitioned into the red cycles (x_k+1Py_j+2,x_2Py_j) and (x_1,y_2Px_k-1,y_k) and the edge-cycle (x_j+1,y_1). By Claim <ref>(<ref>), it follows that the edge x_k-1y_2 is red. Observe that the edges x_1y_1 and x_j+1y_k are even and, therefore, blue. Hence, we see that G can be vertex-partitioned into the red cycles (x_k+1Py_j+2,x_2Py_j) and (y_2Px_k-1) and the blue cycle (x_1,y_k,x_j+1,y_1), a contradiction. Thus, the edge x_2y_j+2 is blue.






The edges x_jy_k+2 and x_k+2y_k are blue.


Suppose by way of contradiction that the edge x_jy_k+2 is red (see Figure <ref>). In this case, G can be vertex-partitioned into the red cycle (x_jPx_k+1,y_jPy_k+2) and the subgraph G[j-1]. But, observe that the subgraph G[j-1] is a blue even plait. Hence, by Remark <ref>, we see that G can be vertex-partitioned into 3 monochromatic cycles, a contradiction. Thus, the edge x_jy_k+2 is blue.





Now, suppose by way of contradiction that the edge x_k+2y_k is red. Take the red cycle (x_k+1,y_k+2Px_k+2,y_k), the cover k+2∪{x_k+1, y_k}. We claim that the remaining vertices of G can be vertex-partitioned into at most 3 blue cycles. Indeed, if j=k-1, by <Ref> the edges x_ky_1 and x_2y_k+1 are blue and by <Ref> x_1 y_k+1 is blue  (see Figure <ref>).
Take only the blue cycle
  x_2[E_k∖ y_k] x_k y_1[O_k] x_1  y_k+1 x_2.

On the other hand, if j<k-1, then y_j+2∈ G_k^O (see Figure <ref>).
Again by <Ref> and <Ref>, we can form the blue cycle 
        x_2[E_k∖ y_k] x_j+1 y_1 [O_k∖ x_1] y_j+2 x_2
        
and we also take the edge-cycle (x_1,y_k+1).




The subgraph G[k+2] has a blue Hamiltonian cycle that uses the edges x_k+1y_k+1, x_k+2y_k+2 and x_k+2y_k. Furthermore, the edge x_k+3y_k+3 is blue.


Let us build such a cycle (see <Ref>). We will use the blue edges x_j+1y_1 (<Ref>), x_k+1y_1 and x_1y_k+1 (<Ref>), x_k+1y_k+1 (Remark <ref>(a)), x_k+2y_k (<Ref>), x_k+2y_k+2 (<Ref>), and x_jy_k+2 (<Ref>).

First take the cycle
C = x_j+1[E_k] y_k  x_k+2 y_k+2 x_j [O_k∖ y_1] x_1  y_1  x_j+1.

It is a blue cycle covering all vertices of k∪{x_k+2,y_k+2} and it uses the edge x_1y_1. So C' = C - x_1y_1 +x_1y_k+1x_k+1y_1 is a blue cycle which satisfies the first part of the claim. By Remark <ref>(a), it follows that the edge x_k+3y_k+3 is blue.




As before, if k = n-3 the proof ends here since we have just proved that the edge x_ny_n is blue, whereas it belongs to the red path P. This is a contradiction. Hence, in the remaining claims 
    k ≤ n-4.

This allows us to use indices up to k+4.


The edge x_jy_k+1 is blue.



Suppose by way of contradiction that the edge x_jy_k+1 is red. In this case, we shall prove that k+2 is a blue special set of G. Now <Ref> tells us that the edges x_k+1y_1 and x_1y_k+1 are blue. <Ref> tells us that the edges x_j+1y_1 and x_2y_j+2 are blue too. Also, since here we assume that the edge x_jy_k+1 is red we can use the `alternate' version of <Ref> consisting in exchanging X and Y, therefore the edges x_1y_j+1 and x_j+2y_2 are also blue. Figure <ref> shows all those edges.

On the one hand, if j=k-1 then this means that the edges x_2y_k+1 and x_k+1y_2 are blue.  Then x_2 [E_k] y_2  x_k+1 y_1 [O_k] x_1  y_k+1 x_2 is a blue Hamiltonian cycle of G[k+1].
On the other hand if j<k-1 then x_j+2,y_j+2∈ G_k^O. Start with
C = x_2 [E_k] y_2  x_j+2[O_k] y_j+2 x_2. 
C is a blue Hamiltonian cycle of G[k] and we can require it to use the edge x_1y_1 (G_k^O is a blue bipartite complete graph, hence x_j+2[O_k] y_j+2 can be required to use x_1y_1). Therefore C' = C-x_1y_1 +x_1y_x+1x_k+1y_1 is a blue Hamiltonian cycle of G[k+1].

In both cases, by Claim <ref>, we see that k+2 is a blue special set of G, a contradiction. Thus, the result follows.





There is a blue cycle in G that covers all vertices in k+1 except x_k+1 and y_k.



By <Ref> and <Ref> the edges x_j+1y_1, x_2y_j+2 and x_1y_k+1 are blue.

On the one hand if j=k-1, this means that the edges x_ky_1 and x_2y_k+1 are blue (see Figure <ref>). Then 
x_2[E_k∖ y_k] x_k  y_1 [O_k] x_1  y_k+1 x_2 is a blue cycle covering y_k+1 and all vertices of k except y_k.

On the other hand (j < k-1), y_j+2∈ G_k^O. We will also need the edge x_jy_k+1, which is blue by <Ref>. Let
C = x_2 [E_k∖ y_k] x_j+1 y_1  x_1  y_k+1 x_j  y_j+2 x_2. This cycle covers G_k^E ∖ y_k and passes through the vertices x_1, y_1, x_j, y_j+2 in G_k^O. Now, we can replace the edge x_1y_1 of C with a path that covers all remaining vertices of G_k^O.






The edge x_k+1y_k+3 is blue.


Suppose by way of contradiction that the edge x_k+1y_k+3 is red (see Figure <ref>). Hence, by <Ref>, we see that G can be vertex-partitioned into the red cycle (x_k+1,y_k+3Px_k+3,y_k+2), the edge-cycle (x_k+2,y_k) and a blue cycle that covers all vertices in k+1 except x_k+1 and y_k, a contradiction. Thus, the result follows.




The edges x_1y_k and x_k+1y_2 are not both blue.



Suppose by way of contradiction that the edges x_1y_k and x_k+1y_2 are blue (see Figure <ref>). In this case, we shall prove that k+2 is a blue special set of G, a contradiction. The edge x_1y_k+1 is blue by <Ref> and x_j+1y_1 is blue by <Ref>. So,
x_j+1[E_k] y_k  x_1 [O_k] y_1  x_j+1 is a blue Hamiltonian cycle of G[k]. And x_j+1[E_k] y_2  x_k+1 y_k+1 x_1  [O_k] y_1  x_j+1 is a a blue Hamiltonian cycle G[k+1]. 
Together with Claim <ref>, we see that k+2 is a blue special set of G. Thus, the result follows.






The edge x_2y_k+2 is blue.



Suppose by way of contradiction that the edge x_2y_k+2 is red (see Figure <ref>). In this case, G can be vertex-partitioned into the red cycle (x_2Py_k+2), the red path (x_1,y_2Py_k,x_k+1) and the vertex y_1. By Claim <ref>, we know that the edges x_1y_k and x_k+1y_2 are not both blue. Hence, we see that G can be vertex-partitioned into 3 monochromatic cycles (one of which is an edge-cycle), a contradiction. Thus, the result follows.





The edge x_k+3y_k+1 is blue.


Suppose by way of contradiction that the edge x_k+3y_k+1 is red (see Figure <ref>). By <Ref> and <Ref> the edges x_j+1y_1 and x_2y_k+2 are blue. Let 
C = x_j+1[E_k∖ y_k] x_2  y_k+2 x_j [O_k] y_1  x_j+1, which is a blue cycle that covers (k∖ y_k) ∪{y_k+2}. Then G can be vertex-partitioned into the red cycle (x_k+2,y_k+3Px_k+3,y_k+1), the edge-cycle (x_k+1,y_k) and C, a contradiction. Thus, the result follows.







The subgraph G[k+3] has a blue Hamiltonian cycle that uses the edges x_k+2y_k and x_k+3y_k+3. Consequently, the edge x_k+4y_k+4 is blue.



By <Ref>, start with a blue Hamiltonian cycle C,of G[k+2] that uses the edges x_k+1y_k+1 and x_k+2y_k. <Ref> also tell us that x_k+3y_k+3 is blue. Now, extend C by replacing the edge x_k+1y_k+1 by the path x_k+1y_k+3x_k+3y_k+1 (using Claims <ref> and <ref>). This gives the desired blue Hamiltonian cycle of G[k+3]. By <Ref>(a), it follows that the edge x_k+4y_k+4 is blue.




The edges x_k+4y_k and x_k+2y_k+4 are blue.



Suppose by way of contradiction that the edge x_k+4y_k is red (see Figure <ref>). Hence, by Claim <ref>, we see that G can be vertex-partitioned into the red cycle (x_k+1,y_k+2,x_k+3,y_k+4Px_k+4,y_k), the edge-cycle (x_k+2,y_k+3) and a blue cycle that covers all vertices in k+1 except x_k+1 and y_k, a contradiction. Thus, the edge x_k+4y_k is blue.



Now, suppose by way of contradiction that the edge x_k+2y_k+4 is red (see Figure <ref>). By <Ref> and <Ref> the edges x_j+1y_1 and x_2y_k+2 are blue. Together with <Ref> we build the blue cycle
C = x_j+1[E_k∖ y_k] x_2  y_k+2 x_j [O_k∖ y_1] x_1  y_k+1 x_k+1 y_1  x_j+1
that covers (k+1∖ y_k) ∪{y_k+2}.
Thus G can be vertex-partitioned into the red cycle (x_k+2,y_k+4Px_k+4,y_k+3), the edge-cycle (x_k+3,y_k) and C. Hence, we get a contradiction. Thus, the edge x_k+2y_k+4 is blue.



The subgraph G[k+4] has a blue Hamiltonian cycle that uses the edges x_k+3y_k+3 and x_k+4y_k+4.



Using <Ref>, take a blue Hamiltonian cycle of G[k+3] that uses the edges x_k+2y_k and x_k+3y_k+3 and extend it to a blue Hamiltonian cycle of G[k+4] that uses the edges x_k+3y_k+3 and x_k+4y_k+4 by replacing the edge x_k+2y_k by the path (x_k+2,y_k+4,x_k+4,y_k), which is blue by Claims <ref> and <ref>.


Thus, by Claims <ref>, <ref> and <ref>, we see that k+4 is a blue special set of G, which is our final contradiction for Case A.



Case B: k is odd and k≥ 4, therefore j is even with 2 ≤ j < k ≤ n-2.



Most proofs are similar to the ones in Case A. We will give the details on how to derive the A proofs to B proofs. Of course, we should also replace any reference to a Claim A to its Claim B counterpart.
case


 
         
  *  If there exists 1 ≤ l ≤ k odd such that x_k+1y_l is red, them x_2y_k and x_k-1y_1 are not both blue.
         
  *  If there exists 1 ≤ l ≤ k odd such that x_k+1y_l is red, them x_ky_2 and x_1y_k-1 are not both blue.




Interchange the roles of x_1 and x_2, of y_1 and y_2 and of G_k^O and G_k^E in the proof of Claim <ref>.



The edges x_k+1y_2 and x_2y_k+1 are blue.



Suppose by way of contradiction that the edge x_k+1y_2 is red (see Figure <ref>). In this case, G can be vertex-partitioned into the red cycle (x_k+1Py_2), the red path (y_1,x_2Px_k-1,y_k) and the vertex x_1 (a difference here is that in <Ref> we did not have this hanging vertex x_1).  By Claim <ref>(<ref>), we know that the edges x_2y_k and x_k-1y_1 are not both blue. Hence, we see that G can be vertex-partitioned into 3 monochromatic cycles, a contradiction. Thus, the edge x_k+1y_2 is blue. Analogously, swapping the roles of X and Y and using <Ref>(<ref>), the edge x_2y_k+1 is blue too. Thus, the result follows.






The edge x_k+2y_k+2 is blue.



Just interchange the roles of x_1 and x_2, of y_1 and y_2 and of G_k^O and G_k^E.


As in Case A, from this point, without loss of generality
        we assume  that the edge x_k+1y_j is red.
By <Ref> we know that j ≠ 2. And as in Case A, if k = n-2, then the proof ends here: we proved that x_ny_n is red, a contradiction. Hence from now:  
    2 < j ≤ k ≤ n-3





The edges x_j+1y_2 and x_1y_j+2 are blue. In particular, when j=k-1, this means that x_ky_2 and x_1y_k+1 are blue.



This proof is similar to <Ref>, with minor changes. First, to prove that the edge  x_j+1y_2 is blue, we do as in <Ref>, interchanging the roles of x_1 and x_2, and of y_1 and y_2.


 (see Figure <ref>). In this case, G can be vertex-partitioned into the red cycle (x_k+1Px_j+1,y_2Py_j), the red path (y_1,x_2Px_k-1,y_k) and the vertex x_1. By Claim <ref>, we know that the edges x_2y_k and x_k-1y_1 are not both blue. Hence, we see that G can be vertex-partitioned into 3 monochromatic cycles, a contradiction. Thus, the edge x_j+1y_2 is blue.


 
Now, suppose by way of contradiction that the edge x_1y_j+2 is red (see Figure <ref>). Then, G can be vertex-partitioned into the red cycle (x_k+1Py_j+2,x_1Py_j), the red path (y_1,x_2Px_k-1,y_k) and the vertex x_j+1. By Claim <ref>, we know that the edges x_2y_k and x_k-1y_1 are not both blue. Hence, G can be vertex-partitioned into 3 monochromatic cycles, a contradiction. Thus, the edge x_1y_j+2 is blue.







The edges x_jy_k+2 and x_k+2y_k are blue.



To show that x_jy_k+2 is blue, use the proof of <Ref> as is (see Figure <ref>). Then to show that x_k+2y_k is blue, do as in Claim <ref>, interchanging the roles of x_1 and x_2, of y_1 and y_2, of O_k and E_k, and of G_k^O and G_k^E.



The subgraph G[k+2] has a blue Hamiltonian cycle that uses the edges x_k+1y_k+1, x_k+2y_k+2 and x_k+2y_k. Furthermore, the edge x_k+3y_k+3 is blue.



Interchange the roles of x_1 and x_2, of y_1 and y_2 and of G_k^O and G_k^E in the proof of <Ref>.


As in Case A, if k = n-3 then the proof ends here: we proved that x_ny_n is red, a contradiction. Hence, in the remaining claims we have

    k ≤ n-4.



The edge x_jy_k+1 is blue.



Interchange the roles of x_1 and x_2, of y_1 and y_2 and of G_k^O and G_k^E  in the proof of <Ref>.



There is a blue cycle in G that covers all vertices in k+1 except x_k+1 and y_k.



Interchange the roles of x_1 and x_2, of y_1 and y_2 and of G_k^O and G_k^E in the proof of <Ref>.



The edge x_k+1y_k+3 is blue.



The proof of Claim <ref> can be used as is.



The edges x_2y_k and x_k+1y_1 are not both blue.



Interchange the roles of x_1 and x_2, of y_1 and y_2 and of G_k^O and G_k^E  in the proof of <Ref>.



The edge x_1y_k+2 is blue.



Suppose by way of contradiction that the edge x_1y_k+2 is red (see Figure <ref>). In this case, G can be vertex-partitioned into the red cycle (x_1Py_k+2) and the red path (x_k+1,y_kPx_2,y_1). By Claim <ref>, we know that the edges x_2y_k and x_k+1y_1 are not both blue. Hence, we see that G can be vertex-partitioned into at most 3 monochromatic cycles, a contradiction. 





The edge x_k+3y_k+1 is blue.



Interchange the roles of x_1 and x_2, of y_1 and y_2 and of G_k^O and G_k^E in the proof of Claim <ref>.



The subgraph G[k+3] has a blue Hamiltonian cycle that uses the edges x_k+2y_k and x_k+3y_k+3. Consequently, the edge x_k+4y_k+4 is blue.



The proof of Claim <ref> can almost be used as is: just replace Claim <ref> by <ref>.



The edges x_k+4y_k and x_k+2y_k+4 are blue.



Interchange the roles of x_1 and x_2, of y_1 and y_2 and of G_k^O and G_k^E in the proof of Claim <ref>.



The subgraph G[k+4] has a blue Hamiltonian cycle that uses the edges x_k+3y_k+3 and x_k+4y_k+4.




We can use the proof of Claim <ref> almost as is: just use <Ref> instead of <Ref>.


Thus, by Claims <ref>, <ref> and <ref>, we see that k+4 is a blue special set of G, which is our final contradiction for Case B.

This ends the proof of <Ref>.


Now, we may finally prove Lemma <ref>.


Let us take G as in the statement: a balanced complete bipartite graph whose edges are coloured red or blue, and which has a monochromatic Hamiltonian path. Without loss of generality, we can assume this path is red and that its vertices are labelled so that it is a red zigzag graph. Assume for contradiction that G cannot be partitioned into three monochromatic cycles. Let the number of vertices of G be 2n.

By Remark <ref>(a), we may assume that the edges x_1y_1 and x_2y_2 are blue, since otherwise we would be done. Thus, the subgraph G[2] is a blue even plait and so we may apply Lemma <ref> iteratively until k = n-2 inclusive. Therefore n-1 is a blue plait, hence it can be decomposed into two blue cycles C_E and C_O by <Ref>. Finally, G can be decomposed into the red edge-cycle x_ny_n and the two blue cycles C_E and C_O, which is a contradiction and concludes the proof.




§ CONCLUSIONS AND PERSPECTIVES

In this paper, we proved a new bound on the number of monochromatic cycles needed to partition the vertices of any edge-bicoloured complete balanced bipartite graph. We made quite an improvement as the previous known bound was 12 and we reduced it to 4. Also we can point out that our work concerns all graphs, while many paper tackling similar problems focus on large graphs.
For this reason our proofs do not resort to strong results, and is self contained apart from Stein's result (<Ref>) for which we also had an alternate but very similar proof, hence not worthy of being shown here.

We wrote the proof of our main result in a very detailed way, with the goal to make it easy to be verified. So it ended up being somewhat long. Of course, one can make it shorter (but harder to check) by omitting some trivial details and remarks or not explicitly listing all cycles (the reader is free for not reading this details and search for the cycles in the pictures). We could also have omitted the “B claims” (when k is odd), asking the reader to believe that the proofs are similar to the ones of the case when k is even. However, we did not find a way to make the analysis intrinsically shorter. A good reason for this is that many of those cases have to be checked even to deal with small values of k (say k≤ 10).

We also showed that if the colouring is split, then we can partition the vertices into at most three monochromatic cycles and described exactly when 2 cycles are enough (and when are not). And we gave examples of a 2-colouring of a complete balanced bipartite graĵ that is not split and also cannot be partitioned into 2 cycles. Therefore, it remains to decide if the 2-colour cycle partition number of balanced bipartite graphs is 3 or 4. 







