It is NP-complete to determine whether an arbitrary graph has chromatic number k, where k >= 3. However, determining whether an arbitrary graph has chromatic number 2 is in P. Given a graph G on n...

It is NP-complete to determine whether an arbitrary graph has chromatic number k, where k  >= 3.

However, determining whether an arbitrary graph has chromatic number 2 is in P.

Given a graph G on n vertices, create an algorithm that will return TRUE if  χ(G) = 2 and

FALSE if  χ(G) ≠ 2. Clearly explain how your algorithm works, why it guarantees the correct

output, and determine the running time of your algorithm.

Extracted text: a b d e f g i k