Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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

1 Answer 1

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|improve this answer

Your Answer

 
discard

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.