WITH PYTHON CODE

Figure 1: Vertex color assignment on a graph G 1. (5 pts) Discuss the problem complexity of the Vertex Coloring Problem. Is it in P or NP? Is it an easy or a hard problem? 2. (20 pts) Design a greedy algorithm that solves the Vertex Coloring Problem using a greedy color selection rule. Report the pseudocode of your algorithm. 3. (5 pts) What is the time complexity of your algorithm? Is it efficient? Can your algorithm find the optimum solution? 4. (20 pts) Implement your algorithm in Python. Use the input given in the example and report the console outputs. Report your Python code scripts