Return to Answer

added 63 characters in body

Source Link

edited Jul 27, 2022 at 16:00

19
2

I assume by degree in V-S you mean the degree in the full graph (not restricted to V-S).

I begin partitioning $V=A \cup B$ of basically the same size (off by at most 1).

Now by your condition the sum of degrees in A and in B is both at least (about) $3/2n$. So if I am not done, it means that there is a vertex in B that has no neighbor in A, and a vertex in A that has no neighbor in B: otherwise one between A and B would be your desired set S.

Now I swap them. In the new partition $A’ \cup B’$ they both have a neighbor in the other club (as each point has degree at least 1). Furthermore I cannot have introduced new points that lack a friend in the other club as both vertices previously lacked friends in the other club.

This way I strictly reduced the number of vertices in each club lacking a friend in the other club. And I can do this until I am done as explained in the first paragraph. So eventually I cannot reduce this size anymore and I am done.

I wanted to write in the comments because there is probably a mistake as it seems too easy, but I don’t have enough reputation yet. So apologies if there is a mistake or I misunderstood your problem.

Edit: I misread the problem; see comments below. Apologies!

I assume by degree in V-S you mean the degree in the full graph (not restricted to V-S).

I begin partitioning $V=A \cup B$ of basically the same size (off by at most 1).

Now by your condition the sum of degrees in A and in B is both at least (about) $3/2n$. So if I am not done, it means that there is a vertex in B that has no neighbor in A, and a vertex in A that has no neighbor in B: otherwise one between A and B would be your desired set S.

Now I swap them. In the new partition $A’ \cup B’$ they both have a neighbor in the other club (as each point has degree at least 1). Furthermore I cannot have introduced new points that lack a friend in the other club as both vertices previously lacked friends in the other club.

This way I strictly reduced the number of vertices in each club lacking a friend in the other club. And I can do this until I am done as explained in the first paragraph. So eventually I cannot reduce this size anymore and I am done.

I wanted to write in the comments because there is probably a mistake as it seems too easy, but I don’t have enough reputation yet. So apologies if there is a mistake or I misunderstood your problem.

I assume by degree in V-S you mean the degree in the full graph (not restricted to V-S).

I begin partitioning $V=A \cup B$ of basically the same size (off by at most 1).

Now by your condition the sum of degrees in A and in B is both at least (about) $3/2n$. So if I am not done, it means that there is a vertex in B that has no neighbor in A, and a vertex in A that has no neighbor in B: otherwise one between A and B would be your desired set S.

Now I swap them. In the new partition $A’ \cup B’$ they both have a neighbor in the other club (as each point has degree at least 1). Furthermore I cannot have introduced new points that lack a friend in the other club as both vertices previously lacked friends in the other club.

This way I strictly reduced the number of vertices in each club lacking a friend in the other club. And I can do this until I am done as explained in the first paragraph. So eventually I cannot reduce this size anymore and I am done.

I wanted to write in the comments because there is probably a mistake as it seems too easy, but I don’t have enough reputation yet. So apologies if there is a mistake or I misunderstood your problem.

Edit: I misread the problem; see comments below. Apologies!

Source Link

created Jul 27, 2022 at 15:37

19
2

I assume by degree in V-S you mean the degree in the full graph (not restricted to V-S).

I begin partitioning $V=A \cup B$ of basically the same size (off by at most 1).

Now by your condition the sum of degrees in A and in B is both at least (about) $3/2n$. So if I am not done, it means that there is a vertex in B that has no neighbor in A, and a vertex in A that has no neighbor in B: otherwise one between A and B would be your desired set S.

Now I swap them. In the new partition $A’ \cup B’$ they both have a neighbor in the other club (as each point has degree at least 1). Furthermore I cannot have introduced new points that lack a friend in the other club as both vertices previously lacked friends in the other club.

This way I strictly reduced the number of vertices in each club lacking a friend in the other club. And I can do this until I am done as explained in the first paragraph. So eventually I cannot reduce this size anymore and I am done.

I wanted to write in the comments because there is probably a mistake as it seems too easy, but I don’t have enough reputation yet. So apologies if there is a mistake or I misunderstood your problem.