On Oct 28, 2:02 pm, "[EMAIL PROTECTED]" <[EMAIL PROTECTED]> wrote: > I am trying to find the proof for the following problem from CLR. > > Prove that a undirected graph with no self edges can be divided into > two groups such that for every node,atleast half of the nodes it is > adjacent to, are in a different group than the node itself. > > Solutions/hints will be appreciated.
One proof is to show the following algorithm must work: Put the vertices arbitrarily into two sets. As long as you can move a vertex from one set to the other and increase the number of edges between the two sets, do that. This criterion for moving a vertex is equivalent to saying that the vertex thas more neighbors in its own set than in the other. After moving, the situation is reversed: more neighbors are in the opposite set. Now the algorithm must terminate after moving vertices at most |E| times. This is because you are increasing the number of edges between sets by one with each move, and you can't do better than getting all the edges! --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---