Question

1. Let G be a bipartite graph with 107 left vertices and 20 right vertices. Two vertices u, v are called twins if the set of neighbors of u equals the set of neighbors of v (triplets, quadruplets etc are defined similarly).

   Show that G has twins.
   Bonus: Show that G has triplets. What about quadruplets, etc.?

Answer 1

Suppose that there are elements on the left and elements on the right. Then the way we can make a graph such that there are no twins is by using the following algorithm:

• Select the first vertex on the left and do not join it to any other vertex on the right.
• Select next vertices on the left and join it to the right vertices in a one on one manner. Notice that we are not supposed to keep any vertex empty hence this follows.
• Now note that you can form exactly pairs from the vertices in the right, and hence select the next vertices from the left and join them to each separate pair. Then do the same for the next points in the left, joining them to separate triplets on the right and so on.
• Continue like this till you reach a point where you take point in the left and join it to all the points in the right. This is the twins saturation point. Any other point in the left will now be either empty or be connected to 1 point or 2 points or... or all points, and hence will inevitably share it's set of neighbours with someone else.

The condition for twins saturation is . Thus for a twin to occur, the condiition has to be that there exists more points beyond the twins saturation point, which, mathematically means .

Now, given is and . We see that and hence this graph cannot have a twin. If there's no twins, then there is no case of any triplet, quadruplet etc.

But note that if and , then and hence there exists at least 1 twin.

For the case of triplets, note that we can use the exact same algorithm as above to avoid making a graph with triplets. First we reach the twins saturation point, and then forget that we ever did anything and start using the algorithm again till we again reach a twin saturation point. Note that this would create lots of twins ( to be exact), but no triplets. This is the triplet saturation point. Any point beyond this will create a triplet. Thus the necessary number of points till the triplet saturation point is and the condition for no triplet is . Thus to have a triplet, we necessarily require .

We note that for and , and hence there exists at least 1 triplet.

Going by the same argument, we see that for an -tuplet to exist, the necessary condition is .

We note that for and , but and hence there exists quadruplets, quintuplets but no sextuplets or further.