(adsbygoogle = window.adsbygoogle || []).push({}); 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.

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Graph theory

Can you offer guidance or do you also need help?

Draft saved
Draft deleted

**Physics Forums | Science Articles, Homework Help, Discussion**