We have graph G, let’s get its compliment and call it G’, let’s look at 3 vertices in G’: x,y,z : if x<->y and y<->z , then x<->z (x and y weren’t in different groups in any point of time, same goes for y and z, so x and z weren’t in different groups). This means that any subgraph in G’ is a Complete graph. If vertices x and y are in different subgraphs in G’, then they were in different groups at some point in time. Let’s condensate the G’ (I’ll call it G’’). Now, the problem becomes: we have S vertices in G’’, and have to find the minimum number of operations to get in the end to isolate each vertex. The answer is log(n) rounded up. Here is the setup: grab half vertices from G’’ and put them in A1 (I’ll call this action A1 = G’’/2). Now grab another half and put it into B1(B1 = G’’ - A). Separate them. Step 2: A2 = (A1 /2 + B1 /2), B2 = G’’ – A2. Separate A2 and B2. Now, quarters hate each other. Continue doing step 2, you’ll get 1/8’s hating each other, then 1/16’s and so on.

1 Like