1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Graph theory

  1. Nov 4, 2008 #1
    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.
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted