2 Preliminaries

The symbols $|G|$ , $e(G)$ , $\delta (G)$ and $\Delta (G)$ denote the number of vertices, the number of edges, the minimum degree and the maximum degree of the graph $G$ , respectively. By $\Delta _2(G)$ , we mean the second-largest degree. That is, if $(d_1,d_2,\ldots ,d_n)$ is the degree sequence of $G$ with $d_1\geq d_2 \geq \cdots \geq d_n$ , then $\Delta _2(G)=d_2$ . Let $K_{s,t}$ be the complete bipartite graph with parts of sizes $s$ and $t$ . For a red–blue edge-colouring of a $K_N$ , we let $R$ and $B$ denote the spanning subgraphs of $K_N$ , whose edge sets consist of all red and all blue edges of $K_N$ , respectively. Given a subset $X\subseteq V(G)$ , we write $G[X]$ for the subgraph of $G$ induced by $X$ . For a vertex $v\in V(G)$ , $d_R(v)$ and $d_B(v)$ denote the red degree and blue degree of $v$ , that is, the number of red and blue edges incident to $v$ , respectively. We denote by $N_{R}(v)$ (respectively $N_{B}(v)$ ) the set of vertices adjacent to $v$ by a red (respectively blue) edge.

Our proof also needs the following three important lemmas. The first lemma is due to Dobson and shows that when a graph contains no $K_{2,n}$ , its complement graph contains a large class of trees.

The second lemma is due to Häggkvist and gives an upper bound for $R(T_n, P_m)$ .

Since every tree is a subgraph of a complete bipartite graph, the following holds.

The concept of pancyclicity for graphs was introduced and studied by Bondy [Reference Bondy1] in the early 1970s. A graph $ G $ is pancyclic if it contains cycles of every length between 3 and $|G|$ . Bondy established several sufficient conditions for a graph to be pancyclic. The third lemma is one such degree condition.

3 Proof of Theorem 1.6

From (1.1), we have $R(T_n, C_m) \geq 2n - 1$ for every odd integer $m \geq 3$ . In what follows, we show that if $m \geq 3$ is odd and $n \geq 2m-4$ , then $R(T_n, C_m) \leq 2n - 1$ . Let $N=2n-1$ . Assume that $K_N$ has a red–blue edge colouring such that it contains neither a red $T_n$ nor a blue $C_m$ .

If $\delta (R) \geq n - 1$ , then clearly $T_n$ can be embedded into $R$ . Hence, $\delta (R) \leq n - 2$ , which implies $\Delta (B) = N- 1 - \delta (R) \geq n$ . Let $u \in V(K_N)$ be such that $d_B(u) = \Delta (B)$ . Then, there must be one edge in $B[N_B(u)]$ , which together with $u$ forms a blue $C_3$ and so gives a contradiction. Hence, we may assume $m\geq 5$ .

We claim that $\Delta (R)\ge n-1$ and $\delta (R)\ge n/2$ .

If $\delta (B)\ge n>N/2$ , then by Lemma 2.4, since $N=2n-1$ is odd, $B$ is pancyclic and, hence, contains a blue $C_m$ , giving a contradiction. Thus, $\delta (B)\le n-1$ and so

(3.1) $$ \begin{align} \Delta(R) \geq N - 1 - (n - 1) = n - 1. \end{align} $$

Suppose next that $\delta (R)<n/2$ . Let $u$ be a vertex with $d_R(u)=\delta (R)$ . Since $d_R(u)$ is an integer, $d_R(u)\le \lceil n/2\rceil -1$ . Therefore, $d_B(u)\ge 2n-1-\lceil n/2\rceil = n-1+\lfloor n/2\rfloor $ . As $n\ge 2m-4$ , we have $\lfloor n/2\rfloor \ge m-2$ and, hence, $d_B(u)\ge n+m-3$ . By Corollary 2.3, $R(T_n,P_{m-1})\le n+(m-1)-2=n+m-3$ . Thus, $B[N_B(u)]$ contains a blue $P_{m-1}$ , unless $R[N_B(u)]$ contains a red $T_n$ . The latter is impossible, while the former together with $u$ forms a blue $C_m$ , giving a contradiction. Hence,

(3.2) $$ \begin{align} \delta(R) \geq \frac{n}{2}. \end{align} $$

This proves the claim.

Since $e(T_n)=n-1$ , we have $\Delta _2(T_n)\leq n/2$ and $\Delta (T_n)\leq n-1$ for all $n$ -vertex trees $T_n$ . By (3.1) and (3.2), $\Delta _2(T_n)\leq \delta (R)$ and $\Delta (T_n)\leq \Delta (R)$ for all $n$ -vertex trees $T_n$ . If $K_N$ contains no blue $K_{2,n}$ , then applying Lemma 2.1 with $G=R$ and $\overline {G}=B$ shows that $R$ contains every tree $T_n$ , that is, $K_N$ contains a red copy of $T_n$ , giving a contradiction. Hence, $K_N$ contains a blue $K_{2,n}$ .

Let the two partite sets of the blue $K_{2,n}$ be $\{u_1,u_2\}$ and $U$ , where $|U|=n$ . Set $V=~V(K_N)$ and $W = V \setminus (U \cup \{u_1, u_2\})$ . Then, $|W|=n-3$ .

Clearly, $B[U]$ contains no $P_{m-3}$ . Indeed, if $z_1z_2\cdots z_{m-3}$ is a blue path in $U$ , then since $n-(m-3)=n-m+3>0$ , we may choose $y\in U\setminus \{z_1,\ldots ,z_{m-3}\}$ . Then, $u_1z_1z_2\cdots z_{m-3}u_2yu_1$ is a blue $C_m$ , which is a contradiction.

Let $T^1$ be a subtree obtained from $T_n$ by repeatedly deleting leaves until exactly $n-m+5$ vertices remain. By Corollary 2.3,

$$ \begin{align*} R(T_{n-m+5},P_{m-3})\le (n-m+5)+(m-3)-2=n=|U|. \end{align*} $$

Since $B[U]$ contains no $P_{m-3}$ , the graph $R[U]$ contains a red copy of $T^1$ . If $m=5$ , then $T^1=T_n$ , giving a contradiction. Thus, we may assume $m\ge 7$ .

Starting from this red copy of $T^1$ , greedily extend the embedding along a leaf-adding order from $T^1$ to $T_n$ in $R$ . Since $R$ contains no red $T_n$ , the procedure must fail. Hence, for the current embedded subtree $H$ , there exists a vertex $u_3\in V(H)$ such that $u_3$ is blue-adjacent to every vertex in $V(K_N)\setminus V(H)$ . Moreover, $|V(H)|\le n-1$ .

Since the initial copy of $T^1$ lies entirely in $U$ , and at most $(n-1)-(n-m+5)=m-6$ vertices have been added before the failure, we have $|W\cap V(H)|\le m-6$ .

Set $A=N_B(u_3)\cap W$ . Since $W\setminus V(H)\subseteq A$ ,

$$ \begin{align*} |A|\ge |W|-|W\cap V(H)| \ge (n-3)-(m-6)=n-m+3. \end{align*} $$

We claim that $u_3\notin \{u_1,u_2\}$ . Otherwise, since $u_3$ is blue-adjacent to every vertex of $U$ and $A$ , we have $d_B(u_3)\ge |U|+|A|\ge n+(n-m+3)=2n-m+3$ . Consequently,

$$ \begin{align*} d_R(u_3)\le 2n-2-(2n-m+3)=m-5<n/2, \end{align*} $$

where the last inequality follows from $n\ge 2m-4$ . This contradicts $\delta (R)\ge n/2$ . Hence, $u_3\notin \{u_1,u_2\}$ , as claimed.

Moreover, since $|V(H)|\le n-1$ and $|U|=n$ , there exists $v_1\in U\setminus V(H)$ . By the choice of $u_3$ , the edge $u_3v_1$ is blue. Define

$$ \begin{align*}U_0=U\setminus(\{v_1\}\cup(\{u_3\}\cap U)).\end{align*} $$

Then, $|U_0|\ge n-2$ . Since $U_0\cap A=\emptyset $ and $n\ge 2m-4$ ,

$$ \begin{align*}|U_0\cup A|\ge (n-2)+(n-m+3)=2n-m+1\ge n+m-3.\end{align*} $$

Again by Corollary 2.3, $R(T_n,P_{m-1})\le n+m-3$ , which gives

$$ \begin{align*}|U_0\cup A| \ge R(T_n,P_{m-1}).\end{align*} $$

Since $R$ contains no red $T_n$ , the graph $B[U_0\cup A]$ contains a blue path $P_{m-1}$ , say $P=z_1z_2\cdots z_{m-1}$ .

We now derive a blue $C_m$ according to the positions of the endpoints of $P$ .

• • If $z_1,z_{m-1}\in U_0$ , then $u_1z_1z_2\cdots z_{m-1}u_1$ is a blue $C_m$ .

• • If $z_1,z_{m-1}\in A$ , then $u_3z_1z_2\cdots z_{m-1}u_3$ is a blue $C_m$ .

• • If one of $z_1,z_{m-1}$ lies in $U_0$ and the other in $A$ , without loss of generality, let $z_1\in U_0,~ z_{m-1}\in A$ . Consider the position of $z_{m-3}$ .

  • – If $z_{m-3}\in U_0$ , then $z_1z_2\cdots z_{m-3}u_1v_1u_2z_1$ is a blue $C_m$ .

  • – If $z_{m-3}\in A$ , then $z_1z_2\cdots z_{m-3}u_3v_1u_1z_1$ is a blue $C_m$ .

In all cases, we obtain a blue $C_m$ , giving a contradiction.

The proof of Theorem 1.6 is complete.