Prove or disprove: involves Chromatic numbers, and subgraphs isomorphic to Kr

Question

Prove or Disprove,

a) if a graph $G$ contains a subgraph isomorphic to $K_r$, then the chromatic number is greater than or equal to $r$

b) if the chromatic number is great than or equal to $r$, then $G$ contains a subgraph isomorphic to $K_r$.(converse of a)

would $C_5$ be a counterexample for b)?

Answer 1

Hints:

For a), how many colors would you need to properly color just the $K_r$ subgraph?

For b), $C_5$ has chromatic number 3, but does it contain a $K_3$ subgraph?

Answer 2

If a graph $G$ contains a subgraph isomorphic to $K_r$, then the vertices of this subgraph must be assigned different colors. Thus, the chromatic number of $G$ is at least $r$.

The converse is not true in general since there exist triangle-free graphs (i.e. graphs without a $K_3$) with arbitrarily large chromatic number. Methods to construct such graphs have been shown by Tutte (1947) and by Mycielski (1955). Starting with a triangle-free graph $G_1$, one can construct a sequence of triangle-free graphs $G_2, G_3,\ldots,$ such that the chromatic number of $G_k$ is $k$.