I initially encountered this problem in CLRS Intro to Algorithms, problem B-2.c:

[prove that] any group of people can be partitioned into two subgroups such that at least half the friends of each person belong to the subgroup of which that person is not a member.

I found some notes online by a Carnegie Mellon professor and former IMO gold medalist, that briefly discusses this problem (on page 3 of the notes):

Let G be a graph. It is possible to partition the vertices into two groups such that for each vertex, at least half of its neighbors ended up in the other group. Solution: Take a max-cut: the bipartition which maximizes the number of crossing edges.

That is all that is said. I also found a thread that discusses the same problem, and that too simply states that a max cut always solves the problem.

I found another thread that discusses a procedure for swapping vertices until the desired property is reached. The procedure is seen to be guaranteed to terminate since it always increases the number of crossing edges. (It is not certain and probably not true that such a procedure always reaches the max cut however, but I understand why it works.)

However, it is not immediately obvious to me why a max cut is guaranteed to solve the problem, and the way the result is stated in the first two links above seems to suggest that the result follows immediately simply from the fact that it is max cut. The initial theorem requires that every vertex must have at least half of its edges crossing the partition. How does this immediately follow from finding the partition the maximizes the total number of edges crossing?

  • 1
    $\begingroup$ Regarding the relationship between the maximum cut and the swapping procedure: in general, it's typical of many graph theory proofs that for any solution along the lines of "Locally improve this structure until it cannot be improved further" there is an equivalent solution along the lines "Start with a maximal structure that cannot be locally improved". In this case, the structure is a vertex cut and "locally improve" means "move a vertex to the other side, increasing the number of cut edges". $\endgroup$ – Misha Lavrov Dec 1 '17 at 19:39

(OP here) I now understand. It is simply because if we had a max cut, then it would be impossible to further increase the number of partition-crossing edges, hence there cannot be any vertices that have less than half of its neighbors in the other partition, since if there were then it would still be possible to increase the number of partition-crossing edges by swapping such vertices to the other side, which contradicts our initial assumption of the partition being a max cut.

  • $\begingroup$ I don't follow, swap what vertices? What do you mean by "such vertices"? $\endgroup$ – Abhijit Sarkar Nov 22 '18 at 5:27
  • $\begingroup$ it's in the same sentence: "such vertices" refers to "vertices that have less than half of its neighbors in the other partition" $\endgroup$ – xdavidliu Nov 23 '18 at 17:14
  • $\begingroup$ You didn't understand my question. "Swapping", by definition, involves 2 things; one here are "vertices that have less than half of its neighbors in the other partition". What's the other? Also, if you had a max cut, and you swapped the vertices, is there any proof that the cut is still valid? If not, then the act of swapping in order to prove by contradiction is invalid as well. $\endgroup$ – Abhijit Sarkar Nov 24 '18 at 7:41
  • $\begingroup$ perhaps a better word for it is move instead of swap. We move a single vertex from one side to the other; not swap two vertices. The proof by contradiction is valid, since if the vertex we are about to move had more neighbors (e.g. connected by an edge) on its own side than neighbors on the other side, then if we move that one vertex to the other side, the number of partition-crossing edges would increase. This contradicts our assumption that it was a max cut. Hence, a max cut must have all vertices with more neighbors on its opposite side. $\endgroup$ – xdavidliu Nov 25 '18 at 11:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.