Electronic Journal of Graph Theory and Applications 13 .
, 163Ae170 Connected size Ramsey numbers of matchings versus a small path or cycle Sha Wanga,b .
Ruyu Songa,b .
Yixin Zhanga,b .
Yanbo ZhangOa,b School of Mathematical Sciences.
Hebei Normal University.
Shijiazhuang 050024.
China b Hebei Research Center of the Basic Discipline Pure Mathematics.
Shijiazhuang 050024.
China .
wang, rysong, yxzhan.
@stu.
cn, ybzhang@hebtu.
O corresponding author Abstract Given two graphs G1 .
G2 , the connected size Ramsey number rCc (G1 .
G2 ) is defined to be the minimum number of edges of a connected graph G, such that for any red-blue edge colouring of G, there is either a red copy of G1 or a blue copy of G2 .
Concentrating on rCc .
K2 .
G2 ) where nK2 is a matching, we generalise and improve two previous results as follows.
Vito.
Nabila.
Safitri, and Silaban (J.
Phys.
Conf.
Ser.
, 2.
obtained the exact values of rCc .
K2 .
P3 ) for n = 2, 3, 4.
determine its exact values for all positive integers n.
Rahadjeng.
Baskoro, and Assiyatun (Proc.
Indian Acad.
Sci.
: Math.
Sci.
, 2.
proved that rCc .
K2 .
C4 ) O 5n Oe 1 for n Ou 4.
We improve the upper bound from 5n Oe 1 to UO.
n Oe .
/2UU.
In addition, we show a result which has the same flavour and has exact values: rCc .
K2 .
C3 ) = 4n Oe 1 for all positive integers n.
Keywords: Ramsey number, connected size Ramsey number, matching, path, cycle Mathematics Subject Classification : 05C55, 05D10 DOI: 10.
5614/ejgta.
Introduction Graph Ramsey theory is currently among the most active areas in combinatorics.
Two of the main parameters in the theory are the Ramsey number and the size Ramsey number, which are defined as follows.
Given two graphs G1 and G2 , we write G Ie (G1 .
G2 ) if for any edge colouring Received: 2 January 2025.
Revised: 10 March 2025.
Accepted: 26 March 2025.
Connected size Ramsey numbers of matchings versus a small path or cycle Sha Wang et al.
of G such that each edge is coloured either red or blue, the graph G always contains either a red copy of G1 or a blue copy of G2 .
The Ramsey number r(G1 .
G2 ) is the smallest possible number of vertices in a graph G satisfying G Ie (G1 .
G2 ).
The size Ramsey number rC(G1 .
G2 ) is the smallest possible number of edges in a graph G satisfying G Ie (G1 .
G2 ).
That is to say, r(G1 .
G2 ) = min{|V (G)| : G Ie (G1 .
G2 )}, and rC(G1 .
G2 ) = min{|E(G)| : G Ie (G1 .
G2 )}.
The size Ramsey number was introduced by ErdoUs.
Faudree.
Rousseau, and Schelp .
Some variants have also been studied since then.
In 2015.
Rahadjeng.
Baskoro, and Assiyatun .
initiated the study of such a variant called connected size Ramsey number by adding the condition that G is connected.
Formally speaking, the connected size Ramsey number rCc (G1 .
G2 ) is the smallest possible number of edges in a connected graph G satisfying G Ie (G1 .
G2 ).
It is easy to see that rC(G1 .
G2 ) O rCc (G1 .
G2 ), and equality holds when both G1 and G2 are connected graphs.
But the latter parameter seems trickier when G1 or G2 is disconnected.
The previous results are mainly concerned with the connected size Ramsey numbers of a matching versus a sparse graph such as a path, a star, and a cycle.
Let nK2 be a matching with n edges, and Pm a path with m vertices.
Vito.
Nabila.
Safitri, and Silaban .
gave an upper bound of rCc .
K2 .
Pm ), and the exact values of rCc .
K2 .
P3 ) for n = 2, 3, 4.
/2 Oe 1, if n is even.
Theorem 1.
For n Ou 1, m Ou 3, rCc .
K2 .
Pm ) O .
/2 Oe 3, if n is odd.
Equality holds for m = 3 and 1 O n O 4.
Other related results can be found in .
If m is much larger than n, this upper bound cannot be Because ErdoUs and Faudree .
constructed a connected graph which implies rCc .
K2 .
Pm ) O Oo m c m, where c is a constant depending on n.
But for small m, the above upper bound can be Our first result determines the exact values of rCc .
K2 .
P3 ) for all positive integers n, which generalises the equality of Theorem 1.
Theorem 1.
For all positive integers n, we have rCc .
K2 .
P3 ) = UO.
n Oe .
/2UU.
Rahadjeng.
Baskoro, and Assiyatun .
proved that rCc .
K2 .
C4 ) O 5n Oe 1 for n Ou 4.
This upper bound can be improved from 5n Oe 1 to UO.
n Oe .
/2UU.
Theorem 1.
For all positive integers n, we have rCc .
K2 .
C4 ) O UO.
n Oe .
/2UU.
Now we prove the theorem by constructing a graph with UO.
n Oe .
/2UU edges.
Let K3,3 Oe e be the graph K3,3 with one edge deleted.
It is easy to check that K3,3 Oe e Ie .
K2 .
C4 ).
We use nG to denote n disjoint copies of G.
If n is even, then n2 (K3,3 Oe .
Ie .
K2 .
C4 ).
The graph (K3,3 Oe .
has n/2 components and can be connected by adding n/2 Oe 1 edges.
If n is odd, then nOe1 (K3,3 Oe .
O C4 Ie .
K2 .
C4 ).
The graph nOe1 (K3,3 Oe .
O C4 has .
/2 components and can be connected by adding .
Oe .
/2 edges.
In both cases, we obtain a connected graph with UO.
n Oe .
/2UU edges and hence the upper bound follows.
It seems likely that the determination of rCc .
K2 .
C4 ) for all n is tricky.
We believe the upper bound is tight and pose the following conjecture.
Connected size Ramsey numbers of matchings versus a small path or cycle Sha Wang et al.
Conjecture 1.
For all positive integers n, rCc .
K2 .
C4 ) = UO.
n Oe .
/2UU.
Even though solving the above conjecture seems out of our reach, we show a result which has the same flavour and has exact values: rCc .
K2 .
C3 ) = 4n Oe 1.
Theorem 1.
For all positive integers n, we have rCc .
K2 .
C3 ) = 4n Oe 1.
Proofs of Theorem 1.
2 and Theorem 1.
4 will be presented in Section 2 and Section 3, respectively.
To prove the lower bounds, we need to discuss the connectivity of a graph G.
If G is not 2-connected, the basic properties of blocks and end blocks are needed, which can be found in Bondy and Murty .
Chap.
Moreover, the following terminology is used frequently in the We say G has a (G1 .
G2 )-colouring if there is a red-blue edge colouring of G such that G contains neither a red G1 nor a blue G2 .
Thus, it is equivalent to G Ie (G1 .
G2 ).
A matching versus P3 For the upper bound, we know that C4 Ie .
K2 .
P3 ).
If n is even, then n2 C4 Ie .
K2 .
P3 ).
The graph n2 C4 has n/2 components and can be connected by adding n/2 Oe 1 edges.
If n is odd, then nOe1 C4 O P3 Ie .
K2 .
P3 ).
The graph nOe1 C4 O P3 has .
/2 components and can be connected by adding .
Oe .
/2 edges.
In both cases, we obtain a connected graph with UO.
n Oe .
/2UU edges and hence the upper bound follows.
For the lower bound, we use induction on n.
The result is obvious for n = 1, 2.
Assume that for k < n and any connected graph G with UO.
k Oe .
/2UU edges, we have G Ie .
K2 .
P3 ).
Now consider G to be a connected graph with minimum number of edges such that G Ie .
K2 .
P3 ).
Thus, for any proper connected subgraph GA of G, we have GA Ie .
K2 .
P3 ).
Since n Ou 3.
G has at least six edges.
Suppose to the contrary that G has at most UO.
n Oe .
/2UU edges.
We will deduce a contradiction and hence rCc .
K2 .
P3 ) Ou UO.
n Oe .
/2UU.
An edge set E1 of a connected graph G is called deletable, if E1 satisfies the following conditions:
E1 can be partitioned into two edge sets E2 and E3 , where E2 forms a star and E3 forms a .
any edge of E(G) \ E1 is nonadjacent to E3 .
the graph induced by E(G) \ E1 is still connected.
Note that for a deletable edge set E1 , the graph G Oe E1 may have some isolated vertices, but all edges of G Oe E1 belong to the same connected component.
We have the following property of a deletable edge set.
Claim 2.
Every deletable edge set has size at most two.
Proof.
Let E1 be a deletable edge set.
If |E1 | Ou 3, then the graph induced by E(G)\E1 has at most UO.
n Oe .
/2UU Oe 3 edges and hence an (.
Oe .
K2 .
P3 )-colouring by induction.
We then colour all edges of E2 red and all edges of E3 blue.
This is a .
K2 .
P3 )-colouring of G, a contradiction.
Connected size Ramsey numbers of matchings versus a small path or cycle Sha Wang et al.
A non-cut vertex of a connected graph is a vertex whose deletion still results in a connected That is, every vertex of a nontrivial connected graph is either a cut vertex or a non-cut Since E3 in the definition of a deletable edge set can be empty, the edges incident to a non-cut vertex form a deletable edge set.
We have the following direct corollary.
Claim 2.
Every non-cut vertex has degree at most two.
If G is a 2-connected graph, by Claim 2.
G is a cycle.
Beginning from any edge of G, we may colour all edges consecutively along the cycle.
We alternately colour two edges red and one edge blue, until all edges of G have been coloured.
Obviously G contains no blue P3 .
From .
n Oe .
/2 O 3.
Oe .
and the colouring of G we see that G contains no red matching with n Thus.
G Ie .
K2 .
P3 ).
Now we assume that G is connected but not 2-connected.
Recall that a block of a graph is a subgraph that is nonseparable and is maximal with respect to this property.
An end block is a block that contains exactly one cut vertex of G.
We have the following observation.
Claim 2.
Every end block is either a K2 or a cycle.
Proof.
Let B be an end block with at least three vertices, and let v be the single cut vertex of G that is contained in B.
Since B is 2-connected, the subgraph B Oe v is still connected.
By Claim 2.
every non-cut vertex has degree two.
It follows that B Oe v is either a path or a cycle.
We see that v has two neighbours in B.
If not, v has at least three neighbours in B, each of which has degree one in B Oe v.
Since a path has two vertices of degree one and a cycle has no vertex of degree one.
B Oe v is neither a path nor a cycle, a contradiction.
Hence, every vertex of B has two neighbours in B.
Since B is 2-connected, it must be a cycle.
Since G is not 2-connected, there is at least one cut vertex.
Choose any cut vertex as a root, denoted by r.
For a vertex u of G, if any path from u to r must pass through a cut vertex v, then u is called a .
descendant of v.
For any edge e of G, if both ends of e are descendants of v, then e is called an edge descendant of v.
For a cut vertex v, the block containing v but no other descendant of v is called a parent block of v.
It is obvious that every cut vertex has a unique parent block, except that the root r has no parent block.
If v is a cut vertex but every descendant of v is not a cut vertex of G, we call v an end-cut.
It is obvious that G has at least one end-cut.
We have the following property of end-cuts.
Claim 2.
Every end-cut is contained in a unique end block, which is K2 .
Moreover, if an end-cut is not the root of G, its parent block is also K2 .
Proof.
Let v be an end-cut.
If v is not the root r, by the definition of end-cut, every block containing v is an end block, except for its parent block.
If we delete v and all descendants of v from G, the induced subgraph is still connected, denoted by GA .
This is because, any vertex of GA is not a descendant of v.
For any two vertices of GA , there is a path joining them in G without passing through v.
So the path still exists in GA and hence GA is connected.
In the following, regardless of whether v is the root or not, we first colour all edges incident to v red, then give a colouring of all edge descendants of v.
After that, we find a colouring of GA by the inductive hypothesis.
We prove that this edge colouring of G is an .
K2 .
P3 )-colouring under certain conditions.
Connected size Ramsey numbers of matchings versus a small path or cycle Sha Wang et al.
By Claim 2.
3, every end block is either a K2 or a cycle.
Assume that v has t1 neighbours in its parent block.
Note that if v is the root of G, then t1 = 0.
Assume v is contained in t2 blocks which are K2 , and in t blocks which are cycles.
Let p1 2, p2 2, .
, pt 2 be the cycle lengths of these t cycles.
If we remove v from G, the cycles become t disjoint paths with lengths p1 , p2 , .
, pt We colour all edges incident to v red.
For each path with length pi , where 1 O i O t, we colour all edges from one leaf to the other leaf consecutively along the path, alternately with one edge blue and two edges red.
Now we have coloured x := t1 t2 2t p1 p2 A A A pt edges, no blue P3 appears, and the maximum red matching has y := 1 UO.
/3UU A A A UO.
/3UU If v is the root, then we have already coloured all edges of G.
So x O UO.
n Oe .
/2UU, and we need to check that y O n Oe 1.
Since G has at least six edges, we have 6t2 7t p1 Ou 11.
Thus, n Ou .
/5 Ou .
t2 4t 2p1 A A A 2pt .
/5 Ou .
p1 A A A pt .
/3 > y.
This implies that G Ie .
K2 .
P3 ).
If v is not the root, recall that GA is formed by the remaining edges and is connected.
can use the inductive hypothesis.
The graph GA has at most UO.
n Oe .
/2UU Oe x edges, which is UO.
Oe 2x/.
Oe .
/2UU O UO.
Oe UO2x/5UU) Oe .
/2UU.
So GA has an (.
Oe UO2x/5UU)K2 .
P3 )-colouring.
It is not difficult to check that G has no blue P3 , and the maximum red matching has at most y n Oe UO2x/5UU Oe 1 edges.
It is left to show that under what conditions y n Oe UO2x/5UU Oe 1 is less than n.
So we deduce a contradiction.
Since v has at least one neighbour in its parent block, it follows that t1 Ou 1.
If t Ou 1, then 1 .
Oe .
/3 O .
/5, and UO.
/3UU O .
/5.
Thus, y = 1 UO.
/3UU UO.
/3UU A A A UO.
/3UU O 1 UO.
/3UU .
/3 A A A .
/3 O 1 UO.
/3UU .
Oe .
/3 2.
2 A A A pn )/5 O .
/5 .
/5 2.
2 A A A pn )/5 O 2.
1 t2 2t p1 p2 A A A pt )/5 = 2x/5.
If t = 0 and t1 t2 Ou 3, then y = 1 < 6/5 O 2x/5.
In both cases, we have y O 2x/5 and hence y n Oe UO2x/5UU Oe 1 < n.
Now we consider the remainder case when t = 0 and t1 t2 O 2.
Since v is an end-cut, we have t2 Ou 1.
Thus, t1 = t2 = 1.
It follows from t = 0 and t2 = 1 that v is contained in a unique end block which is K2 .
It follows from t1 = 1 that v has only one neighbour in its parent block.
Since each block is either a K2 or a 2-connected subgraph, the parent block of v must be K2 .
Let v be an end-cut.
By Claim 2.
4, it cannot be the root of G.
Let u be the other end of its parent block, and v the descendant of v.
If u is contained in an end block which is an edge uu , then uv, uu , vv form a deletable edge set.
If u is contained in an end block which is not an edge, by Claim 2.
3, the end block is a cycle.
Let u be a neighbour of u on the cycle.
Then uv, uu , vv form a deletable edge set.
If u has at least two end-cuts as its descendants, let w be another end-cut and uw, ww edge descendants of u.
Then uv, vv , uw, ww form a deletable edge set.
If u has only one end-cut as its descendant, which is v, then all edges incident to u and the edge vv form a deletable edge set.
By Claim 2.
1, each of the above cases leads to a contradiction.
This completes the proof of the lower bound.
Connected size Ramsey numbers of matchings versus a small path or cycle Sha Wang et al.
A matching versus C3 Now we prove Theorem 1.
The graph nC3 has n components and can be connected by adding n Oe 1 edges.
Denote this connected graph by H.
It follows from nC3 Ie .
K2 .
C3 ) that H Ie .
K2 .
C3 ).
Thus, rCc .
K2 .
C3 ) O 4n Oe 1.
Set G = {G : |E(G)| O 4n Oe 2, and G Ie .
K2 .
C3 )}.
We will prove that G is an empty set and hence the lower bound follows.
Suppose not, choose a graph G from G with minimum order and minimum size subjective to its order.
Thus, for any proper connected subgraph GA of G with at most 4k Oe 2 edges, we have GA Ie .
K2 .
C3 ).
We present the proof through a sequence of claims.
Claim 3.
The minimum degree of G is at least two.
Proof.
Suppose that G has a vertex v of degree one.
Then G Oe v has an .
K2 .
C3 )-colouring.
can be extended to an .
K2 .
C3 )-colouring of G by colouring the edge incident to v blue, which contradicts our assumption that G Ie .
K2 .
C3 ).
Thus, (G) Ou 2.
Claim 3.
The graph G has no cut edge.
Proof.
Suppose that G has a cut edge e.
Then G Oe e has two connected components X and Y .
Let k1 , k2 be the integers such that 4k1 Oe 5 O |E(X)| O 4k1 Oe 2 and 4k2 Oe 5 O |E(Y )| O 4k2 Oe 2 Then X has a .
1 K2 .
C3 )-colouring and Y has a .
2 K2 .
C3 )-colouring.
It can be extended to an (.
1 k2 Oe .
K2 .
C3 )-colouring of G by colouring e blue.
So the maximum red matching has at most k1 k2 Oe 2 edges.
From .
k1 Oe .
k2 Oe .
1 O |E(X)| |E(Y )| 1 O 4n Oe 2 we deduce that k1 k2 Oe 2 O n Oe 1/4, a contradiction which implies our claim.
Claim 3.
The graph G is 2-connected.
Proof.
If G is not 2-connected, let v be a cut vertex of G, and B1 .
B2 , .
BEe the blocks containing v, where Ee Ou 2.
If v has only one neighbour in Bi for some i with 1 O i O Ee, then Bi is not 2connected.
Since any block is either 2-connected or a K2 .
Bi has to be K2 .
Hence.
Bi is a cut edge .
Chap.
, which contradicts Claim 3.
Thus, for each Bi with 1 O i O Ee, v has at least two neighbours in Bi .
The vertex set V (G) can be partitioned into two parts X and Y as follows.
If any path from u to v has to pass through a vertex of B1 other than v, then u OO X.
otherwise u OO Y .
Let G1 and G2 be the subgraphs induced by X O .
and Y respectively.
It is obvious that G1 contains B1 and G2 contains B2 O A A A O BEe .
And they share only one vertex, which is v.
Let k1 , k2 be the integers such that 4k1 Oe 5 O |E(G1 )| O 4k1 Oe 2 and 4k2 Oe 5 O |E(G2 )| O 4k2 Oe 2 respectively.
Then G1 has a .
1 K2 .
C3 )-colouring and G2 has a .
2 K2 .
C3 )-colouring.
Combining the two colourings we have an (.
1 k2 Oe .
K2 .
C3 )-colouring of G.
So the maximum red matching has at most k1 k2 Oe 2 edges.
From .
k1 Oe .
k2 Oe .
O |E(G1 )| |E(G2 )| O 4n Oe 2 we deduce that k1 k2 Oe 2 O n.
If k1 k2 Oe 2 < n, then this colouring is an .
K2 .
C3 )-colouring of G.
k1 k2 Oe2 = n, then we have |E(G1 )| = 4k1 Oe5 and |E(G2 )| = 4k2 Oe5.
We obtain an .
K2 .
C3 )colouring of G as follows.
If Ee = 2, then both B1 Oe v and B2 Oe v are connected.
Hence, both G1 Oe v and G2 Oe v are connected, which implies that they have a (.
1 Oe .
K2 .
C3 )-colouring and a (.
2 Oe .
K2 .
C3 )-colouring, respectively.
It can be extended to an (.
1 k2 Oe .
K2 .
C3 )-colouring Connected size Ramsey numbers of matchings versus a small path or cycle Sha Wang et al.
of G by colouring all edges incident to v red.
Thus.
G Ie .
K2 .
C3 ).
If Ee Ou 3, then for each i with 2 O i O Ee, we delete an edge vvi from Bi .
Both G1 Oe v and G2 Oe .
v2 , .
, vvEe } are connected.
they have a (.
1 Oe .
K2 .
C3 )-colouring and a (.
2 Oe .
K2 .
C3 )-colouring, respectively.
It can be extended to an (.
1 k2 Oe .
K2 .
C3 )-colouring of G by colouring the remaining edges red.
Again.
G Ie .
K2 .
C3 ).
Claim 3.
The maximum degree of G is at most three.
Proof.
For any vertex v of G, by Claim 3.
G Oe v is still connected.
If d.
Ou 4.
G Oe v has at most 4.
Oe .
Oe 2 edges and hence an (.
Oe .
K2 .
C3 )-colouring by the choice of G.
It can be extended to an .
K2 .
C3 )-colouring of G by colouring all edges incident to v red, a contradiction.
Thus, the maximum degree of G is at most three.
Claim 3.
The graph G is 3-regular.
Proof.
By Claim 3.
1 and Claim 3.
4, 2 O d.
O 3 for any vertex v of G.
If G is 2-regular, by Claim 3.
G is a cycle.
If G is a triangle, then n Ou 2.
We colour all edges of G red, which is a .
K2 .
C3 )-colouring.
If G is not a triangle, then we colour all edges of G blue, which is a (K2 .
C3 )-colouring.
Thus.
G cannot be 2-regular.
If G is not 3-regular, then G has some vertices with degree two and some with degree three.
There exist two adjacent vertices with degrees two and three respectively, denoted by v1 and v2 .
Since G Oe v2 is connected, and v1 has only one neighbour in G Oe v2 , it follows that G Oe .
1 , v2 } is This graph has at most 4.
Oe .
Oe 2 edges and hence an (.
Oe .
K2 .
C3 )-colouring.
can be extended to an .
K2 .
C3 )-colouring of G by colouring all edges incident to v2 red and the remaining edge incident to v1 blue, a contradiction which implies our claim.
Claim 3.
Each edge of G is contained in at least one triangle.
Proof.
Suppose that G has an edge e which is not contained in any triangle.
By Claim 3.
G Oe e is connected.
It follows from the choice of G that G Oe e has an .
K2 .
C3 )-colouring.
It can be extended to an .
K2 .
C3 )-colouring of G by colouring e blue, a contradiction.
Consider a triangle v1 v2 v3 .
By Claim 3.
5, each of v1 , v2 , v3 has another neighbour, denoted by v4 , v5 , v6 respectively.
If v4 , v5 , v6 are the same vertex, then v1 , v2 , v3 , v4 forms a K4 .
Since G is a 3-regular 2-connected graph, the whole graph G is a K4 and n Ou 2.
We colour the triangle v1 v2 v3 red, and the other three edges blue.
This is a .
K2 .
C3 )-colouring of G, a contradiction.
Thus, at least two of v4 , v5 , v6 are distinct, say, v4 and v5 are two distinct vertices.
The vertex v3 cannot be adjacent to both v4 and v5 , since otherwise d.
3 ) Ou 4.
Without loss of generality, assume that v3 is not adjacent to v4 .
Moreover, v4 is not adjacent to v2 , since otherwise d.
2 ) Ou 4.
Claim 3.
6, v1 v4 is contained in a triangle, denoted by v1 v4 v6 .
Since v6 is different from v2 , v3 , we have d.
1 ) Ou 4, a final contradiction.
Acknowledgement We are grateful to the anonymous reviewers for their valuable suggestions.
Yanbo Zhang was partially supported by the National Natural Science Foundation of China (NSFC) under Grant No.
11601527 and by the Natural Science Foundation of Hebei Province under Grant No.
A2023205045.
Connected size Ramsey numbers of matchings versus a small path or cycle Sha Wang et al.
References