Proofs (discrete mathematics)

19
0
Hello all,

I am stuck on some homework, basically I am stuck on the problems dealing with proofs. I am not asking for complete answers just any direction would be helpful.

1) I have to prove the Grötzsch graph is not 3-colorable (vertex can be colored in such a way that no edge shares 2 vertices with the same color) using proof by contradiction. So far I have, "assume the Grotzsch graph is 3- colorable, then there exists a configuration such that the graphs' edge endpoints share the same color." I'm confused on what to do next, how to continue the proof.

http://upload.wikimedia.org/wikipedia/commons/thumb/4/4b/Grötzsch_graph.svg/480px-Grötzsch_graph.svg.png

2) Prove that the 5 K graph ( sometimes called K 5,5 ) graph is not planar by proof by cases.
I started off proving that its not planar but planar means that the graph cannot possibly be rearranged such that no edges cross.

3) (B − A) ∪ (C − A) = (B ∪ C) − A
Let A, B, and C be any set. I have that x is an element of both the left and right side. I know I have to start off by assuming x is an element of [(B − A) ∪ (C − A)] however I'm not sure what to do next or how to prove its an element of both sides of the equation.

Any help to move forward in my problems would be awsome.
 
Last edited:
19
0
no help?
 

The Physics Forums Way

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top