Prove that any 2-colorable graph can be colored exactly (1-approximation) in polynomial time. One way to do this is to provide a high-level exact algorithm and explain why it is correct.
Prove that any 2-colorable graph can be colored exactly (1-approximation) in polynomial time. One way to do this is to provide a high-level exact algorithm and explain why it is correct.