Results 1 to 2 of 2

Math Help - graph or prove problem

  1. #1
    Junior Member
    Joined
    Aug 2009
    Posts
    33

    Question graph or prove problem

    (i) Can there be a collection of 4 persons in which every person has exactly two friends?
    (ii) Can there be a collection of 6 persons in which every person has exactly three friends?
    (iii) How about a collection of 7 persons in which every person has exactly three friends?

    For each case draw the friendship graph if such setting is possible, or prove it is impossible.

    please explain to me thank you!!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,966
    Thanks
    1785
    Awards
    1
    Quote Originally Posted by quah13579 View Post
    (i) Can there be a collection of 4 persons in which every person has exactly two friends?
    (ii) Can there be a collection of 6 persons in which every person has exactly three friends?
    (iii) How about a collection of 7 persons in which every person has exactly three friends?
    i) Think rectangle.
    ii) Think K_{3,3}
    iii) Can a graph have an odd number of odd vertices?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph theory: Prove min degree(G_n) >= k
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 9th 2011, 09:26 PM
  2. (Graph Theory)Prove that graph X is a tree.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 1st 2011, 04:30 AM
  3. Replies: 6
    Last Post: November 12th 2010, 08:03 AM
  4. Prove a graph doesn't exists
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 4th 2010, 12:39 PM
  5. Prove continuous -> graph is closed
    Posted in the Calculus Forum
    Replies: 4
    Last Post: February 12th 2009, 12:40 AM

Search Tags


/mathhelpforum @mathhelpforum