# Homework Help: Graph theory

1. Nov 4, 2008

### squaremeplz

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.