Show that a graph with maximum degree at most k is k1colorab

Show that a graph with maximum degree at most k is (k+1)-colorable. Please show this by induction on r by removing an edge from the vertex of highest degree, not removing vertex.

Solution

We use induction on the number of edges in the graph, which we denote by n. Let P(n) be the proposition that an n-edges graph with maximum degree at most k is (k + 1)-colorable.

Remove an edge e (and all vertices incident to it), leaving an n-edge subgraph, H. The maximum degree of H is at most k, and so H is (k + 1)-colorable by our assumption P (n).