Proof by induction - Proving graph has a degree.

Question

I have this question:

For a +’ve integer z, the colour z of the graph is the assignment of one of z’s possible colours to each individual vertex of said graph. So that no 2 adjacent vertex receive the same colouring. Every vertex should be assigned one colour only and not necessary to use all the colors. I.e. colours not assigned to any vertex.

Prove, if each vertice of a graph A has degree at most z, then A has a (z + 1) - coloring.

How would you solve this?

Answer 1

You can simply assign colors to the vertices one by one in an arbitrary order. Under the assumptions given, there will always be at least one color available for each vertex when you're considering it.

If you're explicitly required to use induction instead of just explain an algorithm to $(z+1)$-color the graph, then you could prove by induction of $n$ that

For every $n\in\mathbb N$, and every set of $n$-vertices in the graph, there is a valid color assignment for those $n$ vertices that doesn't assign the same color to two neighboring vertices.

Then apply this lemma with $n=|V|$.

Answer 2

Proof by induction on number of vertices in the graph:

BASE: A graph of one vertex has no edges, hence every vertex is of degree at most z. Obviously it can be colored with one color, which is at most (z+1) colors. [note: if you want you could start with the graph of no vertices, in which case both the assumptions and conclusion hold vacuously]

INDUCTION: Suppose every graph of N vertices, for which every vertex is of degree at most z, can be (z+1)-colored. Consider any graph of N+1 vertices for which each vertex is of degree at most z. Pick any vertex and remove it and all its edges; the resulting graph has N vertices each of degree at most z [since removing an edge cannot increase the degree of a vertex], hence is (z+1)-colorable. Color the resulting graph with at most (z+1) colors. Now add back the removed vertex and all removed edges, retaining the existing coloration. Since that vertex has degree at most z, it is adjacent to at most z colors, so there is at least one of the (z+1) colors not used on any vertex adjacent to it. Color that vertex with that unused color. The original (N+1) vertex graph has now been shown to be (z+1)-colorable, hence all such graphs have been so shown (because we picked an arbitrary graph).