Maximum Cut

A maximum cut is a subset of a graph’s vertices such that the number of edges between this subset and the remaining vertices is as large as possible.


Maximum cut for a Chimera unit cell: the blue line around the subset of nodes {4, 5, 6, 7} cuts 16 edges; adding or removing a node decreases the number of edges between the two complementary subsets of the graph.

maximum_cut(G[, sampler])

Returns an approximate maximum cut.

weighted_maximum_cut(G[, sampler])

Returns an approximate weighted maximum cut.