For every r exists large enough n such that any graph...

Question

Let $r$ be a natural number. Prove that there exists large enough $n$ , such that every connected graph on at least $n$ vertices contains $K_r$, $K_{1,r}$ or $P_{r}$ as induced subgraphs (first one is the complete graph , second is bipartite complete with one side of size 1 and the other side of size $r$ , and the last one is path containing $r$ edges

This smells like a question that requires the diagonal ramsey numbers , but I can't solve this.(I choose n=$R(r,r)+1$ but with no success )

P.S.: I am fully aware that there exists an answer for this question in Diestel's book , but I am looking for another proof(he uses a proposition we didn't learn in the course , but there is no way I would have thought about that proposition during an exam)

Answer 1

Suppose $G$ is a connected graph of order $n$ which does not contain $K_r,K_{1,r}$, or $P_r$ as an induced subgraph; I will derive an upper bound for $n$. Here $P_r$ is a path of length $r$, not a path with $r$ vertices. Let $R=R(r-1,r)$ be the Ramsey number such that any graph of order $R$ either contains an $(r-1)$-vertex clique or else contains an $r$-vertex independent set. Let $\Delta=\Delta(G)$ be the maximum degree of a vertex in $G$.

Claim 1: $\Delta\lt R$.

Proof: If there were a vertex $v$ of degree at least $R$, then by applying Ramsey's theorem to the subgraph of $G$ induced by $N(v)$ we would get either $K_r$ or $K_{1,r}$ as an induced subgraph of $G$.

Claim 2: $\operatorname{diam}(G)\lt r$.

Proof: A shortest path from $u$ to $v$ is an induced path of length $d(u,v)$; since $G$ contains no induced path of length $r$, we must have $d(u,v)\lt r$ for all $u,v\in V(G)$.

Claim 3: $n\le1+\sum_{d=1}^{r-1}\Delta(\Delta-1)^{d-1}\le1+\sum_{d=1}^{r-1}(R-1)(R-2)^{d-1}.$

Proof: Choose a vertex $u$. It's easy to see that for $d\gt0$ we have $|\{v:d(u,v)=d\}|\le\Delta(\Delta-1)^{d-1}$; the upper limit of summation comes from Claim 2; and $\Delta\le R-1$ by Claim 1.

Hence, if $G$ is a connected graph whose order exceeds the bound in Claim 3, then $G$ must have $K_r$ or $K_{1,r}$ or $P_r$ as an induced subgraph.

Answer 2

In claim 1, where seems to be a problem: if N(v) is a complete graph then it's ok to say we have either an r-1 or r click but if N(v) isn't a complete graph then you have a problem, where's really nothing to say in that case so how is it possible to use ramesy in that case?