Graph: What is $R(K_{1,5},K_{1,5})$.

92 Views Asked by At

We define $R(H_1,H_2)$ to be the least number such for every graph $G$ with at least $R(H_1,H_2)$ vertices, either $H_1\subset G$, or $H_2\subset G^c$. What is $R(K_{1,5},K_{1,5})$ ?

I would say that is $10$. Indeed, if we consider $K_9$ and color each edges adjacent to a vertices $c$ suche that 4 edges is blue and 4 edges is red, we will never obtain $K_{1,5}$. With $K_{10}$, the pigeon hole principle tells us that at least $5$ edges has the same color what conclude the proof.

Do you agree ?