Content deleted Content added
Nealeyoung (talk | contribs) m →External links: external link had changed, I updated it |
m →Max-Cut Lemma: Graph (mathematics) is now a disambiguation link; please fix., replaced: graph → graph{{dn|{{subst:DATE}}}} using AWB |
||
Line 56:
=== Max-Cut Lemma ===
Given any undirected [[Graph (mathematics)|graph]]{{dn|date=January 2016}} ''G'' = (''V'', ''E''), the [[Max cut]] problem is to color each vertex of the graph with one of two colors (say black or white) so as to maximize the number of edges whose endpoints have different colors. (Say such an edge is ''cut''.)
'''Max-Cut Lemma:''' In any graph ''G'' = (''V'', ''E''), at least |''E''|/2 edges can be cut.
| |||