I'm trying to show that for any graph with more than 2 vertices, the graph can be partitioned into two groups such that for every vertex at least half of the vertices its connected to are in the other group.
Intuitively, I believe this could be accomplished by looking at each vertex and swapping what group it's in if it doesn't satisfy the condition in its current group. And just repeating this continually until the graph is correctly partitioned.
Unfortunately, I both don't know for sure that this would work in every case or how to prove that this would work even if it does. The problem would arise when a vertex is moved to the other side and this forces a chain of moves that ends up moving the original vertex back again causing a loop. Again, I intuitively think that the graph would not be able to come back to the same state, but I don't know this for sure and certainly can't prove it yet.
Any suggestions what I should be focusing on to prove this? Or is my planned approach simply wrong? Thank you much!
Figured it out. The reason why this is guaranteed to finish is that every time you move a vertex from the one group to the other it will always raise the number of edges that cross from one group to the other. So it is impossible for this to get into an infinite loop. Next, since the number of edges that cross can't be greater than the number of edges in the graph, this process must terminate. Since it only terminates when the conditions are met, this process will always produce the desired partition.