Problem $1.$ Prove that the following problems are in NP by explaining what a certificate and a verifier would be$.$ For your verifier, you do not need to provide pseudocode, it suffices to briefly explain a polynomial time procedure that could be applied to your certificate. These problems all apply to an unweighted and undirected graph $G=(V,E).$

$($a$)(5$ points$)$ Find whether $G$ has a Hamiltonian cycle $($which is a cycle that visits each node in $G$ exactly once$).$

$($b$)(5$ points$)$ Find whether there is a way to separate $V$ into two groups SsubeV and $V-S$ so that there are at least $k$ edges with one endpoint in $S$ and the other endpoint in $V-S($i$.$e$.,$ cut$(S)k.$

$($c$)(5$ points$)$ Find whether the longest simple path in $G$ has greater than or equal to $k$ edges.