Coloriage de graphes — nombre chromatique

Le nombre chromatique χ(G) d'un graphe G est le nombre minimal de couleurs nécessaires pour colorier les sommets de G de sorte que deux sommets adjacents aient des couleurs différentes.

1. Montrer que χ(G) ≥ 2 si et seulement si G contient au moins une arête.
2. Montrer que χ(G) = 2 si et seulement si G est biparti et non vide (ne contient pas de cycle impair).
3. Le graphe complet $K_n$ (n sommets tous reliés entre eux) — quel est son nombre chromatique ?
4. Application : une ville a 5 quartiers. Les quartiers 1-2, 1-3, 2-3, 3-4, 4-5 ont des frontières communes. Combien de couleurs faut-il pour colorier la carte ?