We show that the size of maximum cut in a planar graph with $m$ edges is at least $2m/3$. We also show that maximal planar graphs saturate this bound.
翻译:我们显示,平面图中以美元边缘为美元的最大截断值至少为 $3 美元。 我们还显示,最大平面图饱和了这个绑定 。