The Basic Idea for a Solution

To implement a solution to the 2 coloring problem, we need to visit each node of the graph, which can be done via a depth-first or breadth-first traversal. Initially, none of the nodes is colored so we can assign an arbitrary color to the first node. Once the traversal begins, we check two cases for a node n:

• One or more adjacent nodes of n have been assigned the same color. n can be assigned the opposite color.
• Two or more adjacent nodes of n have been assigned opposite colors. It is not possible to assign n a valid color.

These two cases are shown in the figure below. The gray node has to be assigned a color.