Problem $3.(15$ points$)$ For a directed weighted graph $G=(V,E,w),$ the decision version of the maximum $s-t$ flow problem asks whether, for a given flow value of $k,$ one can find an $s-t$ flow function $f$ satisfying $|f|k.$

Consider an algorithm that takes in an s$-$t cut set SsubeV and in polynomial time computes cut$(S)={\displaystyle \underset{\text{i}\text{i}\text{n}\text{S}}{\overset{?}{}}},j!$inSw$(i,j).$ Explain how this can be used to design a no$-$verifier to prove the problem is in co$-$NP$.$ In particular, explain what you would use as a certificate. Justify your answer. Hint: the answer involves the max$-$flow$/$min$-$cut theorem.