Thread: 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.

haven't studied this course for many years, but I think you did a fine job.

Originally Posted by ilikedmath

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.

Originally Posted by Plato

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?

Originally Posted by ilikedmath

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.

Originally Posted by Plato

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!