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)?
Best Answer
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?