Graph properties question Found the question in one of the previous year exams.
Let $r \in \mathbb{N}$. Show that every graph $G$ fulfills at least one of the following properties:
(1) $G$ is $r$-colorable.
(2) $G$ contains an  induced  copy of  any  cycle $C$ on at most $2r+1$ vertices.
(3) $G$ contains an  induced  copy of  every  tree $T$ on $r$ vertices.
What I thought - if $G$ doesn't fulfill (3), then every induced subgraph on $r$ vertices contains a cycle and then $G$ fulfills (2). I think it's vice verse for (2).
But what about when $G$ doesn't fulfill property (1)?
Thanks in advance.
 A: We will show that if $(1)$ and $(3)$ fail, then $(2)$ must hold.  In fact, it is possible to show a slightly stronger result: that if $\chi(G) \geq r + 1$ and there exists a tree $T$ on $r + 1$ vertices such that $G$ does not contain an induced copy of $T$, then $G$ must contain an induced cycle on at most $r + 1$ vertices.
We will need two lemmas.  Recall that $\delta(G)$ denotes the minimum degree of a graph $G$.
Lemma 1. Any graph $G$ satisfies
$$\chi(G) \leq \max\{\delta(H) \mid H \subseteq G\} + 1.$$
Lemma 2. If $\delta(G) \geq r$ and $T$ is a tree on $r + 1$ vertices, then $G$ contains a copy of $T$.
Now we are ready to begin.
Proof: Fix $r \in \mathbb{N}$ and suppose that $G$ is not $r$-colorable.  By Lemma 1, $\chi(G) \geq r + 1$ implies that $\max\{\delta(H) \mid H \subseteq G\} \geq r$, that is, that $G$ has a subgraph $H$ of minimum degree at least $r$.  By Lemma 2, $H$, and hence $G$, contains a copy of every tree on $r + 1$ vertices.
Suppose that there is some tree $T$ on $r + 1$ vertices such that $G$ does not contain an induced copy of $T$.  Then $G$ must contain a cycle on at most $r + 1$ vertices.  Furthermore, the (not necessarily unique) smallest such cycle must be induced.  This completes the proof.
