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.$

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.