A proof of a conjecture on matching-path connected size Ramsey number

1.   Introduction

Since it was introduced by Erdős, Faudree, Rousseau, and Schelp ^[9] in 1978, size Ramsey number has always been an active branch of graph Ramsey theory. Given two graphs $G_1$ and $G_2$, we write $G\to (G_1, G_2)$ if for any partition $(E_1, E_2)$ of $E(G)$, either $E(G_1)\subseteq E_1$ or $E(G_2)\subseteq E_2$. In the language of coloring, $G\to (G_1, G_2)$ means that the graph $G$ always contains either a red copy of $G_1$ or a blue copy of $G_2$ for any red-blue edge-coloring of $G$. The size Ramsey number $\hat{r}(G_1, G_2)$ is the smallest number of edges in a graph $G$ satisfying $G\to (G_1, G_2)$. In other words, $\hat{r}(G_1, G_2) = \min\{|E(G)|:G\to (G_1, G_2)\}$.

The statement that $\hat{r}(G, G)$ grows linearly with $|V(G)|$ has been well studied if $G$ is a path ^[2,7], a tree with a bounded maximum degree ^[6,13], a cycle ^[14,15], etc. There are also a number of papers concerning the exact values of size Ramsey numbers ^{[4,5,8,9,10,11,12,16,17,18,19,23]}. Among them, Erdős and Faudree ^[8] studied the size Ramsey numbers involving matchings. Particularly, they confirmed that $\hat{r}(nK_2, P_4) = \lceil 5n/2\rceil$.

Several variants have also been well-studied. In 2015, Rahadjeng, Baskoro, and Assiyatun ^[20] initiated the study of such a variant called connected size Ramsey number by requiring $G$ to be connected. Formally speaking, the connected size Ramsey number ${\hat{r}}_c(G_1, G_2)$ is the smallest possible number of edges in a connected graph $G$ satisfying $G\to (G_1, G_2)$. It is clear that $\hat{r}(G_1, G_2)\le {\hat{r}}_c(G_1, G_2)$, and equality holds when both $G_1$ and $G_2$ are connected graphs. But the latter function seems more tricky if either $G_1$ or $G_2$ is disconnected. The previous results mainly concern the connected size Ramsey numbers of a matching versus a sparse graph such as a path, a star, and a cycle; see ^{[1,20,21,22,24,25,26]}.

Let $nK_2$ be a matching with $n$ edges, and $P_m$ a path with $m$ vertices. Rahadjeng, Baskoro, and Assiyatun ^[20] gave an upper bound of ${\hat{r}}_c(nK_2, P_4)$, and its exact value for $2\le n\le 5$. They also proposed the following conjecture.

Conjecture 1.1. ^[20] ${\hat{r}}_c(nK_2, P_4) = \begin{cases}3n-1, & \mathit{\text{if}}\ n\ \mathit{\text{is even}}; \\ 3n, & \mathit{\text{if}}\ n\ \mathit{\text{is odd}}. \end{cases}$

We prove this conjecture by introducing a tool called "deletable edge set" and carefully analyzing the end blocks of the host graph.

Theorem 1.2. ${\hat{r}}_c(nK_2, P_4) = \begin{cases}3n-1, & \mathit{\text{if}}\ n\ \mathit{\text{is even}}; \\ 3n, & \mathit{\text{if}}\ n\ \mathit{\text{is odd}}. \end{cases}$

The proof is postponed to Section 3. A more tricky problem is to determine ${\hat{r}}_c(nK_2, P_5)$. It is easy to check that ${\hat{r}}_c(K_2, P_5) = 4$ and ${\hat{r}}_c(2K_2, P_5) = 6$. To obtain a general upper bound, we use the fact that $C_6\to (2K_2, P_5)$ and $C_{11}\to (3K_2, P_5)$. It follows that $\frac{n}{2}C_6\to (nK_2, P_4)$ for even $n$ with $n\ge 2$, and $\frac{n-3}{2}C_6\cup C_{11}\to (nK_2, P_4)$ for odd $n$ with $n\ge 3$. Both graphs $\frac{n}{2}C_6$ and $\frac{n-3}{2}C_6\cup C_{11}$ have $\lfloor n/2\rfloor$ components and can be connected by adding $\lfloor n/2\rfloor-1$ new edges. Thus we have a connected graph $G$ such that $G\to (nK_2, P_5)$ for each $n\ge 2$. The graph $G$ has $(7n+1)/2$ edges if $n$ is odd, and $(7n-2)/2$ edges if $n$ is even. Hence ${\hat{r}}_c(nK_2, P_5)\le (7n-2)/2$ for even $n$ and ${\hat{r}}_c(nK_2, P_5)\le (7n+1)/2$ for odd $n$. We believe this upper bound is also the lower bound, and pose the following conjecture.

Conjecture 1.3. ${\hat{r}}_c(nK_2, P_5) = \begin{cases}(7n-2)/2, & \mathit{\text{if}}\ n\ \mathit{\text{is even}}; \\ (7n+1)/2, & \mathit{\text{if}}\ n\ \mathit{\text{is odd}}. \end{cases}$

2.   Preliminary Lemmas and Notation

We use induction to prove the lower bound of the main theorem. Thus the following values are needed as the base case.

Lemma 2.1 (Rahadjeng et al. ^[20]). ${\hat{r}}_c(2K_2, P_4) = 5$; ${\hat{r}}_c(3K_2, P_4) = 9$; ${\hat{r}}_c(4K_2, P_4) = 11$; ${\hat{r}}_c(5K_2, P_4) = 15$.

We need three terminologies that appear quite a few times in the proof. A $(G_1, G_2)$-coloring of $G$ is a red-blue edge-coloring such that $G$ contains neither a red copy of $G_1$ nor a blue copy of $G_2$. An edge set $E_0$ of a connected graph $G$ is called deletable, if $E_0$ satisfies the following three conditions:

1. $E_0$ can be partitioned into two edge sets $E_{01}$ and $E_{02}$, where $E_{01}$ forms a star, $E_{02}$ is a disjoint union of paths, each of whose lengths is at most two;

2. any path from $E(G)\setminus E_0$ to $E_{02}$ must pass through some edges of $E_{01}$;

3. the edge set $E(G)\setminus E_0$ induces a connected graph.

Notice that the graph induced by $E(G)\setminus E_0$ is connected, even though the resulting graph by deleting all edges of $E_0$ from $G$ may have some isolated vertices. Further, by coloring all edges of $E_{01}$ red and all edges of $E_{02}$ blue, we have the following lemma.

Lemma 2.2. If $E_0$ is a deletable edge set of $G$, then any $(kK_2, P_4)$-coloring of $E(G)\setminus E_0$ can be extended to a $((k+1)K_2, P_4)$-coloring of $G$.

A non-cut vertex of a connected graph is a vertex whose deletion still results in a connected graph. So every vertex of a nontrivial connected graph is either a cut vertex or a non-cut vertex. We see that the edges incident to a non-cut vertex form a deletable edge set, where $E_{02}$ is an empty set.

We recall some more notation at the end of this section. Let us denote by $\Delta(H)$ the maximum degree of a graph $H$. The notation $d_H(u)$ stands for the number of edges with one end $u$ and the other end in $H$. The graph $H-v$ is the subgraph obtained from $H$ by deleting the vertex $v$ and all the edges incident to $v$. If $S$ is a set of edges, we denote by $G[S]$ the subgraph of $G$ whose edge set is $S$ and whose vertex set consists of all ends of edges of $S$. We use $G\cup H$ to denote the disjoint union of $G$ and $H$, and $nH$ to denote the disjoint union of $n$ copies of $H$. For a connected graph $H$ and any two vertices $u, v$ of $H$, the distance from $u$ to $v$, written $d(u, v)$, is the length of a shortest path from $u$ to $v$.

3.   Proof of Theorem 1.2

The upper bound follows from the fact that $C_5\to (2K_2, P_4)$. If $n$ is even, then $\frac{n}{2}C_5\to (nK_2, P_4)$. The graph $\frac{n}{2}C_5$ has $n/2$ components and can be connected by adding $n/2-1$ new edges. If $n$ is odd, then $\frac{n-1}{2}C_5\cup P_4\to (nK_2, P_4)$. The graph $\frac{n-1}{2}C_5\cup P_4$ has $(n+1)/2$ components and can be connected by adding $(n-1)/2$ new edges. In both cases, we obtain a connected graph with $3n-1+\mathcal{S}$ edges and hence the upper bound follows. Here, $\mathcal{S}$ is a Kronecker delta function, which means that $\mathcal{S} = 0$ if $n$ is even, and $\mathcal{S} = 1$ if $n$ is odd.

To show the lower bound, we proceed by induction on $n$. The result for $n = 1$ is clear, and the results for $2\le n\le 5$ follow from Lemma 2.1. So set $n\ge 6$. Assume that the lower bound holds for every $k$ with $1\le k\le n-1$. That is to say, for any connected graph $G$ with $3k-2+\mathcal{S}$ edges, $G$ has a $(kK_2, P_4)$-coloring. We show that the statement also holds for $n$ by contradiction. Suppose to the contrary that there exists a connected graph $G$ with $3n-2+\mathcal{S}$ edges such that for any red-blue edge-coloring of $G$, it contains either a red copy of $nK_2$ or a blue copy of $P_4$. The following property of a deletable edge set follows from Lemma 2.2.

Claim 3.1. (a). Every deletable edge set has size at most three in $G$.

(b). If $G$ has a deletable edge set $E_0$ of size three, then the graph induced by $E(G)\setminus E_0$, denoted by $H$, has the property that every deletable edge set has size at most two.

Proof. Let $E_0$ be a deletable edge set. Then the graph $H$ induced by $E(G)\setminus E_0$ is still connected. If $|E_0|\ge 4$, then $H$ has at most $3n-5$ edges and hence an $((n-1)K_2, P_4)$-coloring by induction. By Lemma 2.2, it can be extended to an $(nK_2, P_4)$-coloring of $G$. This contradiction implies that every deletable edge set has size at most three.

If $|E_0| = 3$, then in the graph $H$, every deletable edge set has size at most two. Suppose not, there is a deletable edge set $E'_1$ of $H$ which also has size three. The graph induced by $E(H)\setminus E'_1$ is still connected, and has six edges removed from $G$. This graph has an $((n-2)K_2, P_4)$-coloring by the induction hypothesis. It can be extended to an $(nK_2, P_4)$-coloring of $G$, a contradiction.

Since the edges incident to any non-cut vertex form a deletable edge set, we have the following direct corollary.

Corollary 3.2. (a). Every non-cut vertex has degree at most three in $G$.

(b). If $G$ has a non-cut vertex of degree three, then after removing it from $G$, the remaining graph has the property that every non-cut vertex has degree at most two.

To avoid a duplicate argument, if every deletable edge set of $G$ has size at most two, we also use $H$ to denote $G$. To be specific, we have

That is to say, $H$ is either the original graph $G$, or induced by $E(G)\setminus E_0$, where $E_0$ is a deletable edge set of size three. In either case, every deletable edge set in $H$ has size at most two.

If $H$ is 2-connected, then every vertex is non-cut and hence $H$ is a cycle. Denote the cycle by $v_1v_2\cdots v_pv_{p+1}$, where $v_{p+1} = v_1$. Then for $1\le i\le p$, we color the edge $v_iv_{i+1}$ red if $i\equiv 1\pmod 4$ or $i\equiv 2\pmod 4$. Otherwise, we color $v_iv_{i+1}$ blue. The maximum red matching has at most $\lceil |H|/4 \rceil$ edges. Since $n\ge 6$, then $\lceil |H|/4\rceil < n$ if $H$ is the graph $G$, and $\lceil |H|/4 \rceil < n-1$ if $H$ is induced by $E(G)\setminus E_0$. In both cases, $G\not\to (nK_2, P_4)$, a contradiction.

Now assume that $H$ is connected but not 2-connected. To handle this case, we need the following definitions, which can be found in Bondy and Murty [3, Chap. 5.2]. Recall that a block of a graph is a subgraph that is nonseparable and is maximal concerning this property. We may associate with $H$ a bipartite graph $B(H)$ with bipartition $(\mathcal{B}, S)$, where $\mathcal{B}$ has a vertex $b_i$ for each block $B_i$ of $H$, and $S$ consists of the cut vertices of $H$. A block $B$ and a cut vertex $v$ are adjacent in $B(H)$ if and only if $B$ contains $v$ in $H$. The graph $B(H)$ is a tree, called the block tree of $H$. The blocks of $H$ that correspond to leaves of $B(H)$ are referred to as its end blocks. We have the following property of an end block in $H$.

Claim 3.3. If an end block is not $K_2$, it must be a cycle.

Proof. Let $B$ be an end block that is not $K_2$. Since a block with at least three vertices is a 2-connected subgraph, it's left to show that every vertex has two neighbors on this block. By Corollary 3.2, every non-cut vertex has degree at most two. The block $B$ has a single cut vertex of $H$, denoted by $u_0$. Suppose that $u_0$ has more than two neighbors on the block, denoted by $u_1, \dots, u_t$, where $t\ge 3$. If we delete $u_0$ from this block $B$, the resulting graph $B-u_0$ is still connected, but each of $u_1, \dots, u_t$ has degree one. Since each vertex of $B-u_0$ has degree one or two, $B-u_0$ is either a path or a cycle. This contradicts the fact that at least three vertices of $B-u_0$ have degree one. Thus, we have $d_B(u_0)\le 2$. Since $B$ is 2-connected, it must be a cycle.

Claim 3.4. There are at least two cut vertices, each having degree at least three in $H$.

Proof. If every cut vertex has degree two, by Corollary 3.2(b), $\Delta(H) = 2$. Since $H$ is connected but not 2-connected, it must be a path. If $H$ contains only one cut vertex whose degree is at least three, denoted by $v$, then every other vertex has degree at most two, and hence $H-v$ is a disjoint union of some paths. We color all edges incident to $v$ with red. In both cases, along each path, we alternately color two edges blue and two red until all edges have been colored. Then the maximum red matching has $\lfloor (|H|+1)/4 \rfloor$ edges in the first case and at most $\lfloor {|H|/4}+1 \rfloor$ edges in the second case. It is easy to check that both colorings can be extended to an $(nK_2, P_4)$-coloring of $G$, which completes the proof.

Among all cut vertices with degree at least three, we choose two of them, denoted by $u, v$, such that $d(u, v)$ is as large as possible. Let $U$ be the set of vertices such that any path with one end in $U$ and one end as $v$ must pass through $u$. Every vertex of $U$ is called a descendant of $u$. Note that $u\in U$. Also, let $V$ be the set of vertices such that any path from $V$ to $u$ must pass through $v$. Recall that every non-cut vertex has degree at most two. By the choice of $u, v$, every vertex of $U\setminus \{u\}$ (and $V\setminus \{v\}$) has degree one or two in $H$. If $H$ is obtained from $G$ by deleting a deletable edge set $E_0$ of size three, without loss of generality, assume that $E_0$ has no fewer end vertices in $V$ than in $U$. That is, $|V(E_0)\cap V|\ge |V(E_0)\cap U|$. In this way, if we delete all edges incident to $u$ and all edges with both ends in $U$ from the original graph $G$, the graph induced by the remaining edges is still connected.

We see that the induced subgraph $H[U\setminus\{u\}]$ consists of a disjoint union of paths. By Claim 3.3, the induced subgraph $H[U]$ is formed by some paths and some cycles sharing exactly one vertex, which is $u$. We have the following two claims.

Claim 3.5. Every cycle (if it exists) in $H[U]$ has length five.

Proof. If there is a cycle of length three or four in $H[U]$, then it forms a deletable edge set of $H$, which contradicts the fact that every deletable edge set of $H$ has size at most two. If there is a cycle of length at least six in $H[U]$, say, $uu_1u_2\dots u_ku$ is a cycle and $k\ge 5$, then we color $uu_1, u_1u_2, u_4u_5, u_5u_6$ red, and $u_2u_3, u_3u_4$ blue. After deleting the six colored edges from $G$, the graph induced by the remaining edges is still connected, denoted by $G'$. By the inductive hypothesis, $G'$ has an $((n-2)K_2, P_4)$-coloring. Combining it with the above-colored edges, we obtain an $(nK_2, P_4)$-coloring of $G$. Thus, if a cycle appears in $H[U]$, then its length should be five.

Claim 3.6. The subgraph $H[U]$ is a cycle of length five.

Proof. Assume that $H[U]$ consists of $s$ paths $P_1, \dots, P_s$, each of which has $u$ as one of its ends, and $t$ cycles $C_1, \dots, C_t$, each of which has length five. If one of the paths has length at least three, then we can find a subpath with three edges whose edge set is a deletable edge set of $H$, which contradicts the size of a deletable edge set. Hence each $P_i$ has length at most two, where $1\le i\le s$.

For each cycle, we color the two edges incident to $u$ red, and the remaining three edges with one red and two blue. For each path, we color the edge incident to $u$ red, and the remaining edge (if it exists) blue. If $s\ge 1$ and $t = 0$, then all edges incident to $u$ and all edges in $H[U]$ form a deletable edge set. Since $d_H(u)\ge 3$, this is the same contradiction as above. If $s\ge 1$ and $t\ge 1$, then after deleting the colored edges of $P_1$ and $C_1$ from $G$, the graph induced by the remaining edges is still connected. Since $P_1$ and $C_1$ have at least six edges totally, and the maximum red matching has two edges, we may obtain an $(nK_2, P_4)$-coloring of $G$ by induction. If $s = 0$ and $t\ge 2$, then after deleting the colored edges of $C_1$ and $C_2$ from $G$, the graph induced by the remaining edges is still connected. Since both $C_1$ and $C_2$ are pentagons, and the maximum red matching has three edges, we again obtain an $(nK_2, P_4)$-coloring of $G$ by induction. Thus, we have $s = 0$ and $t = 1$. That is, $H[U]$ is a pentagon.

We color all edges incident to $u$ red, and the remaining three edges of $H[U]$ with one red and two blue. Since $d_H(u)\ge 3$, we have already colored at least six edges, and the maximum red matching has only two edges. If we delete these colored edges from $G$, the graph induced by the remaining edges is still connected, which has an $((n-2)K_2, P_4)$-coloring by induction. It can be extended to an $(nK_2, P_4)$-coloring of $G$, a final contradiction.

Acknowledgments

The research was supported by the National Natural Science Foundation of China (Grant No. 11601527 and Grant No. 11971011).

Conflict of interest

The authors declare that they have no conflict of interest.