In a village (where only dwarfs live) there are k streets, and there are k(n−1)+1 clubs each containing n dwarfs. A dwarf can be in more than one clubs, and two dwarfs know each other if they live in the same street or they are in the same club (there is a club they are both in). Prove that is it possible to choose n different dwarfs from n different clubs (one dwarf from each club), such that the n dwarfs know each other! combinatoricsgraph theory