Results 1 to 6 of 6

Math Help - Graph Theory

  1. #1
    Member ilikedmath's Avatar
    Joined
    Sep 2008
    Posts
    98

    Question Graph Theory

    Instructions: Show that there are essentially only 2 models for the following axiom system:

    Undefined terms: point, adjacent to, and color.
    AXIOMS:
    1. There are exactly 5 points.
    2. If point A is adjacent to point B, then point B is adjacent to point A.
    3. If point A is not adjacent to point B, then there exists a point C to which A and B are mutually adjacent.
    4. Each point is assigned a color, red or green.
    5. Any two adjacent points are assigned to different colors.

    My answer:

    R = red point, G = green point

    The models I came up with were:
    Model 1: G R G R G
    and
    Model 2: R G R G R

    Another model could be a vertical orientation, but it would essentially be the same just flipping the models up. The order of the points would still be the same. There is no other way I could think to represent this axiom system where all 5 axioms were satisfied. Is my answer even remotely close to being possibly correct?

    Thank you for your time.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    skeeter's Avatar
    Joined
    Jun 2008
    From
    North Texas
    Posts
    11,621
    Thanks
    426
    haven't studied this course for many years, but I think you did a fine job.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,380
    Thanks
    1473
    Awards
    1
    Quote Originally Posted by ilikedmath View Post
    Instructions: Show that there are essentially only 2 models for the following axiom system:
    Undefined terms: point, adjacent to, and color.
    AXIOMS:
    1. There are exactly 5 points.
    2. If point A is adjacent to point B, then point B is adjacent to point A.
    3. If point A is not adjacent to point B, then there exists a point C to which A and B are mutually adjacent.
    4. Each point is assigned a color, red or green.
    5. Any two adjacent points are assigned to different colors.
    This is really a graph theory question.
    Axiom 3 gives a walk of length 2 between any two vertices so the graph must be connected.
    Axiom 5 (with 4) tells us that the graph cannot contain a 'triangle' or any odd cycle.

    Here are the only two 5-graphs having those properties.
    Attached Thumbnails Attached Thumbnails Graph Theory-model.gif  
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member ilikedmath's Avatar
    Joined
    Sep 2008
    Posts
    98

    Question

    Quote Originally Posted by Plato View Post
    This is really a graph theory question.
    Thanks for looking at the question. That's interesting. How do know this is a graphing theory question?

    The two models you gave make sense. I have a couple of questions:

    1. What is a cycle? and
    2. Would it be okay for me to introduce the lines connecting the points? Would I need to include 'line' as an undefined term so I can connect the points?
    Last edited by ilikedmath; January 29th 2009 at 01:47 PM. Reason: Additional question
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,380
    Thanks
    1473
    Awards
    1
    Quote Originally Posted by ilikedmath View Post
    1. What is a cycle? and
    2. Would it be okay for me to introduce the lines connecting the points? Would I need to include 'line' as an undefined term so I can connect the points?
    What is a cycle? The first graph contains no cycles!
    The second graph conatins one cycle of length four.

    The 'lines' are there just to indicate the relation "adjacent to".
    As such they are not part of the model.
    You could label the points and use pairs to indicate the relation "adjacent to".
    But I think the graph is an easy to see the relationship.

    BTW: Graph Theory is an area of mathematics.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member ilikedmath's Avatar
    Joined
    Sep 2008
    Posts
    98

    Smile

    Quote Originally Posted by Plato View Post
    The second graph conatins one cycle of length four.
    The 'lines' are there just to indicate the relation "adjacent to".
    BTW: Graph Theory is an area of mathematics.
    Awesome, thanks for the quick reply and clear explanation
    The graphs reminded me of Hasse diagrams from Discrete Math. I've taken Modern and Linear Algebra, Calc I-III, Intro to Real Analysis, and Discrete Math. Surely I must have come across some graph theory in at least one of those classes. Thanks again!
    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