We write the ILP formulation of the min multi-cut problem. We have that for every edge E with cost c(e) a variable x(e). This variable x(e) is equal to 1 if edge E is part of the cut. Moreover, we like that for every pair of vertices that we have to disconnect and for every path that connects these pair of vertices there exists at least one edge of this path that is part of the cut. So, the sum of the variables over all the edges of the path is bigger or equal to 1. And every edge is either part of the cut or is not part of the cut. So, we have the integral constraints over the variables.

---