How does this proof about the the coloring of a Graph work?

Question

Could someone tell me how this Proof works (Statement $\chi(G)=\max \{\chi(B) : B \subset G\}$, especially what is the induction hypothesis and why is this proof working? Does this proof only work on a not connected Graph too? I'm trying to learn something about graphs and coloring, but this kind of induction without the classic structure is new for me.

Answer 1

The proof is made in two parts, first to show $\max{\chi(B)}\leq\chi(G)$ and second to show there exists a graph colouring such that $\max{\chi(B)=\chi(G)}$, leaving the theorem.

The first part is straightforward: a full graph colouring with more colours than those needed for its largest block can have the extra colours "culled" down to fit.

---

The second part is done by induction. The base case is the trivial case of a graph with one block (result by definition).

It is then shown, if you start with a graph with multiple blocks where the property holds, you can reduce the number of blocks by one to get another graph where the property holds.

If you then "fiddle" with the colours of the reduced graph, you can add back the block you removed, getting back the original graph, now with a colouring where the property holds.

Since this applies inductively, you could theoretically work "back down to" the trivial case, and then rebuild the original graph, to get a colouring that does what you want.

Note that the proof is existential, not constructive, so it only shows that you can, not how you can.