We are given k colors and we have to assign a single color to every vertex. An edge is satisfied if the vertices on that edge, are of different colors. [*]Prove that you can always find an algorithm which assigns colors to vertices so that at least kk−1∣E∣ edges are satisfied where ∣E∣ is the cardinality of the edges in the graph.[/*]
[*]Prove that there is a poly time deterministic algorithm for this [/*]
graph theorycombinatorics