Find the Ramsey number $R(G, P_3)$

100 Views Asked by At

Let $G$ be a graph with no isolates and $\lvert V(G)\rvert= m$ such that $\overline{G}$ has a perfect matching. I want to show that $R(G, P_3)=m$

Clearly, $R(G, P_3) \geq \lvert V(G) \rvert = m$, so color the edges of $K_m$ using red and blue. I want to show that if the red subgraph does not contain $G$, then the blue subgraph contains $P_3$ (path with 3 vertices).

Now, if the red subgraph is actually a proper subgraph of $G$, then the blue subgraph contains a perfect matching plus at least one other edge, so it contains $P_3$. But what about if the red subgraph does not contain $G$ but is not a proper subgraph of $G$ either?

1

There are 1 best solutions below

0
On

If the blue graph $B$ does not contain $P_3$ then it is a matching, so it is contained in an isomorphic copy of $\overline G$. Then the red graph $\overline{B}$ contains an isomorphic copy of $G$.