Proofs (discrete mathematics)

  • Thread starter thrive
  • Start date
  • #1
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.
 
Last edited:

Answers and Replies

  • #2
19
0
no help?
 

Related Threads on Proofs (discrete mathematics)

  • Last Post
Replies
0
Views
1K
  • Last Post
Replies
2
Views
1K
Replies
4
Views
727
Replies
2
Views
2K
  • Last Post
Replies
3
Views
3K
Replies
1
Views
6K
  • Last Post
Replies
4
Views
12K
Replies
7
Views
4K
Top