- #1
thrive
- 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/wikiped...ö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.
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/wikiped...ö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: