2. Let G be a bipartite graph with 10^7 left vertices and 20right vertices. Two vertices u, v are called twins if the set ofneighbors of u equals the set of neighbors of v (triplets,quadruplets etc are defined similarly). Show that G has twins. Showthat G has triplets. What about quadruplets, etc.?
3. Show that there exists a bipartite graph with 10^5 leftvertices and 20 right vertices without any twins.
4. Show that any graph with n vertices and ?(G) ? n/2 + 1 has atriangle.
