Results 1 to 3 of 3

Math Help - Graph theory

  1. #1
    Junior Member
    Joined
    Apr 2007
    Posts
    38

    Graph theory

    For the following question, describe a graph model and then answer the question: Must the number of people at a party who do not know an odd number of people be even?

    I was thinking about the corollary, where in any graph, the number of vertices of odd degree is even. Would a directed graph (tree) be the correct graph model for this problem?
    Thank you,
    Keith
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Is "knowning" mutal? If so you use an undirected graph.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,956
    Thanks
    1780
    Awards
    1
    Ordinarily, one would not need a directed graph to model “being acquainted with”. If A knows B then we assume that B knows A.

    However, if that is not a symmetric relationship then here is a counter-example to the problem. Say A, B & C are at a party. A knows B, B knows A & C and C knows A & B. In other words A does not know C. Only one, A, does not know an odd number of people.

    If it is a symmetric relationship then a simple graph will work. An edge exists between two people who do not know each other then the corollary works nicely.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph theory, bipartite Graph
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: March 10th 2012, 06:47 AM
  2. Graph Theory / Chromatic Number of a Complete Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 15th 2011, 10:59 AM
  3. (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
  4. Replies: 0
    Last Post: September 25th 2010, 06:59 AM
  5. Graph Theory - Size of a Line Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 26th 2010, 12:15 AM

Search Tags


/mathhelpforum @mathhelpforum