Coloring of graphs -- Chromatic number and induction

Question

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.

Answer 1

Here's a few hints you may find helpful:

1. Consider a graph with $n + 1$ vertices with max degree $d$; remove an arbitrary vertex. What can you say about the chromatic number of the resulting graph? Now add in the removed vertex - how many possible colors could you potentially be restricted from using?

2. Recall that being 2-colorable is equivalent to being bipartite. Can you construct a bipartite graph on $n$ vertices where each vertex has at least $\frac{n-1}{2}$ neighbors? Hint: For $n$ even, you can do $\frac{n}{2}$.