The authors introduce and study an eigenvalue upper bound ℝrsquo;(G) on the maximum cut mc(G) of a weighted graph. The function ℝrsquo;(G) has several interesting properties that resemble the behaviour of mc(G). The following results are presented. The authors show that ℝrsquo; is subadditive with respect to amalgam, and additive with respect to disjoint sum and 1-sum. They prove that ℝrsquo;(G) is never worse that 1.131 mc(G) for a planar, or more generally, a weakly bipartite graph with nonnegative edge weights. The authors give a dual characterization of ℝrsquo;(G), and show that ℝrsquo;(G) is computable in polynomial time with an arbitrary precision.
