A short proof of anti-Ramsey number for cycles
Abstract
Ramsey's theorem states that there exists a least positive integer R(r, s) for which every blue-red edge colouring of the complete graph on R(r, s) vertices contains a blue clique on r vertices or a red clique on s vertices. This work contains a simplified proof of Anti-Ramsey theorem for cycles. If there is an edge e between H and H0, incident to, say, some v ∈ H of color from NEWc(v), then we can make H and H0 connected by adding the edge e and deleting some edge incident to v of the same color as e in H, so the resulting graph G˜ has a connected component of order ≥ 2( k+1/2 ), which contradicts that every connected component is of order ≤ k − 1. Since each component is Hamiltonian and of order ≥ k+1/ 2, to avoid a rainbow Ck, by the same type of argument as in Claim 1, we must have that |c(H, H0 )| = 1.
How to Cite This Article
Noorya Yousifi (2021). A short proof of anti-Ramsey number for cycles . International Journal of Multidisciplinary Research and Growth Evaluation (IJMRGE), 2(3), 108-109. DOI: https://doi.org/10.54660/.IJMRGE.2021.2.3.108-109