A coloring of a simple graph is the assignment of a color to each vertex of the graph so that no two adjacent vertices are assigned the same color. The chromatic number of a simple graph G, denoted χ(G), is minimum number of colors needed for a coloring of G.
Suppose that every vertex of a simple undirected graph G has degree at most d. Prove that G has a d + 1 coloring, i.e., χ(G) ≤ d + 1. Use induction on n, the number of vertices of G.
Also, for every n ≥ 1, construct a 2-colorable graph with n vertices such that every vertex has degree ≥ (n − 1)/2 (i.e., low degree is a sufficient but not a necessary condition for low chromatic number).
Typically I would write where I am for a problem like this, but I have no idea how to approach this proof. Any and all help would be much appreciated.