form a cut that includes all of the edges whose duals appear an odd number of times in the tour. The route inspection problem may be solved in polynomial time, and this duality allows the maximum cut problem to also be solved in polynomial time for planar graphs. The Maximum-Bisection problem is known however to be NP-hard.

More generally, whenever maximum cuts can be found in polynomial time for certain classes of graphs, the algorithms for this problem can be extended to the 2- and 3-clique-sums of