1. The problem statement, all variables and given/known data There are (m-1)n+1 people in the room. Show that there are at least n people who mutually do not know each other, or there is a person who knows at least n people 2. Relevant equations 3. The attempt at a solution I think this has to do with hamiltonian walks. The formula expands to m*n + m - n - 1 = x if m and n are both even integers with, m = n or distinct then the result is always odd if m and n are both odd integers with, m = n or distinct then the result is always even if m is an odd integer and n is even then, or vice versa, the result is even does this have to do with x being the number of edges? or do m and n stand for nodes, edges or vice versa? is this related to a hamiltonian cycle? lets say the total number of people x is even. then there is a hamiltonian walk and one person, knows at least n people. if the number is odd, then there is no closed walk because more than two nodes would have odd edges.