Understand the common complexity classes IN PYTHON coding.

A workshop organiser is trying to distribute people into groups so that no group has two people who have previously worked together. There's a limit on the number of groups that can be created because each group will be in a separate room. The organiser knows who has worked with whom. Can she distribute the participants as required? The general problem is as follows.

Function:$$workshop groups

Input: people, an undirected graph; number of groups, an integer

Preconditions: people has n $>=2$ nodes; $1<=$ number of groups $<=$ n

Output: ok$,$ a Boolean

Postconditions: ok is true if and only if the set of nodes of people can be divided into number of groups subsets so that neighbouring nodes are in different subsets.

Attached image is an example graph, with nodes representing people and edges representing work relations.

Q$4($a$)(3$ marks$)$

Describe a certificate for a problem instance $($a graph$$people$$and an integer$$number of groups$)$ that has a true output. Give as example a certificate for the graph above and$$number of groups$=3.$

Write your answer here

Q$4($b$)(6$ marks$)$

Explain why certificates for this problem can be verified in polynomial time. In other words, briefly explain what the verifier does, given$$people$,$number of groups$$ and the corresponding certificate, and why it takes polynomial time.

Write your answer here