Prove that for graph any simple graph $G$ we have: $\chi(G) \leq 1+\max\{\delta(H):H \text{ is an induced subgraph} \}$.
Take $G$ and remove any vertex $v$ with degree less than $\chi(G)-1$. Do the same in $G-v$ and continue this process until no vertex has degree less than $\chi(G)-1$. The graph you are left with is an an induced subgraph $H$ with $\delta(H) \geq \chi(G) – 1$.
How can I prove that this algorithm with terminate. Or is there a simpler way to look at it?
Help appreciated.
Best Answer
Take $k=1+\max\{\delta(H):H \text{ is an induced subgraph} \}$, we can show that $G$ can be coloured by $k$ colours greedily.
We start from colouring an arbitrary vertex by some colour from $\{1,\dots,k\}$. If an induced subgraph $H$ has already a feasible $k$-colouring, then pick a vertex not in $H$, then $v$ is at most adjacent to $k-1$ vertices in $H$, hence we can find a colour from $\{1,\dots,k\}$ such that together with the colouring of $H$ we have a feasible $k$-colouring for induced subgraph $H+v$. Hence, the result follows.