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

graph theorygraph-isomorphism

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?