5
$\begingroup$

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.

  • 0
    Your negation of (3) is not quite right. If $G$ does not fulfill (3), then there is *one* tree on $r$ vertices that does not appear as an induced subgraph. In this case, $G$ need not contain any cycle (for example, when $G$ is itself a tree).2012-02-04

1 Answers 1

2

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.

  • 1
    @UserB95 Yes, exactly, I seem to have proved something stronger than what was asked for. Perhaps a different, but still natural, approach yields the weaker statement.2015-03-09