  We introduce a new technique to certify lower bounds on the multicut size
using network coding. In directed networks the network coding rate is not a
lower bound on the multicut, but we identify a class of networks on which the
rate is equal to the size of the minimum multicut and show this class is closed
under the strong graph product. We then show that the famous construction of
Saks et al. that gives a $\Theta(k)$ gap between the multicut and the
multicommodity flow rate is contained in this class. This allows us to apply
our result to strengthen their multicut lower bound, determine the exact value
of the minimum multicut, and give an optimal network coding solution with rate
matching the multicut.
