# is it possible to find the maximal min cut in polynomial time?

A maximal minimum cut is a minimum capacity cut with the largest number of edges.

Given an instance of Not-All-Equal 3SAT with $$n$$ variables and $$m$$ clauses, for each variable $$x_i$$, we create two vertices $$v_i$$ and $$v_i'$$ with an edge between them for each variable. In addition, for each clause, for example, $$x_1\vee x_2\vee \neg x_3$$, we add three edges among $$v_1,v_2,v_3'$$ (thus they form a triangle). All edges have weight 0. Now we can see there is a minimum cut (in fact, every cut is a minimum cut) with at least $$n+2m$$ edges if and only if the Not-All-Equal 3SAT instance is satisfiable.