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.


1 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}$.

  • $\begingroup$ When we remove an arbitrary vertex, that decreases the chromatic number. I can't find a formula/correlation for this though. $\endgroup$
    – J. Sanders
    Commented Aug 8, 2017 at 1:49
  • $\begingroup$ @J.Sanders what do you know about the resulting subgraph? (Hint: you should be applying the IH here). Then what do you know about its neighbors? $\endgroup$
    – platty
    Commented Aug 8, 2017 at 2:02
  • $\begingroup$ Been thinking about this for a few hours and still lost. The whole idea of induction on graph theory really is tough to grasp--could you lay out the IH? $\endgroup$
    – J. Sanders
    Commented Aug 8, 2017 at 6:30
  • $\begingroup$ Why don't you just lay out what you have so far, and we can tweak it together if it doesn't quite work out? It'll probably be more insightful for you that way. $\endgroup$
    – platty
    Commented Aug 8, 2017 at 6:32
  • $\begingroup$ I'm pretty sure I have the first part at this point. My problem with the second part is that I am not sure what is a sufficient proof. By definition of bipartite, all examples I come with follow that formula... how does one go about proving that though? $\endgroup$
    – J. Sanders
    Commented Aug 8, 2017 at 13:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .