Results 1 to 2 of 2

Thread: 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
    20,429
    Thanks
    2312
    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: Oct 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: Aug 1st 2011, 04:30 AM
  3. Replies: 6
    Last Post: Nov 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: Feb 12th 2009, 12:40 AM

Search Tags


/mathhelpforum @mathhelpforum