# Finding partition with maximum number of edges between sets

Given a graph (say in adjacency list form), is there an algorithm to find a partition of vertices such that the number of edges between the two sets of the partition is the maximum possible?

For example, for the following set of edges of a graph with vertex set $$\{1, 2, 3, 4, 5, 6\}$$: $$\{(1, 2), (2, 3), (3, 1), (4, 5) , (5, 6), (6, 4)\}$$, one possible "maximum" partition is $$\{\{1, 3, 4, 6\}, \{2, 5\}\}$$ with $$4$$ edges between the sets $$\{1, 3, 4, 6\}$$ and $$\{2, 5\}$$.