Define the graph $H_k$ to be a triangle $xyz$, and $k$ edges $xx_1, xx_2, \dots, xx_k$. Define also for a graph $G$, $R(G)$ to be the least integer $n$ such that a 2-colouring of $K_n$ (the complete graph with $n$ vertices) gives a monochromatic $G$
I am given the results that:
- $ R(I_k) = 3k-1$ where $I_k$ is a set of $k$ independent edges
- $R(H_1) = 7$
The information provided suggests to me that I'll somehow need the first point to construct an inductive argument, using the second point as my base step. However, I am unsure of what $R(H_k)$ should be in that case. It would need to be larger than $3k-1$ to be able to use that point and $k=1$ has to give 7 so maybe it could just be $3k+4$?
For the inductive argument then I would have to demonstrate that $R(H_k) > 3k+3$ and $R(H_k) \leq 3k+4$
My issue is that I am having trouble spotting where the $k$ independent edges might come in when I need to show either of these bounds.
Am I on the right track thinking that I'm being set up for an inductive proof here? If so could I please have a little guidance about how to set it up, thank you.