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