Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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). – Austin Mohr Feb 4 '12 at 18:28
up vote 2 down vote accepted

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.

share|cite|improve this answer
It seems like you got that the cycle is on at most $r+1$ vertices. Am I missing something? – UserB95 Mar 3 '15 at 17:38
Or the question was just trying to confuse (asking to find a cycle on $2r+1$ vertices as induced subgraph while there is a cycle on $r$ vertices as induced subgraph...) – UserB95 Mar 4 '15 at 15:37
@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. – Andrew Uzzell Mar 9 '15 at 13:56

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.