1. Not finding help here? Sign up for a free 30min 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!

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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you help with the solution or looking for help too?

Similar Discussions: Graph theory
  1. Duality theory (Replies: 0)

  2. Graph Theory Problem (Replies: 0)

  3. Group theory (Replies: 0)

  4. Graph Theory (Replies: 0)