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
    9
    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,705
    Thanks
    1637
    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, 05:47 AM
  2. Graph Theory / Chromatic Number of a Complete Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 15th 2011, 09: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, 03:30 AM
  4. Replies: 0
    Last Post: September 25th 2010, 05:59 AM
  5. Graph Theory - Size of a Line Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 25th 2010, 11:15 PM

Search Tags


/mathhelpforum @mathhelpforum