Hello all,(adsbygoogle = window.adsbygoogle || []).push({});

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.

**Physics Forums - The Fusion of Science and Community**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Proofs (discrete mathematics)

Loading...

Similar Threads - Proofs discrete mathematics | Date |
---|---|

I An easy proof of Gödel's first incompleteness theorem? | Mar 6, 2018 |

I Cantor's decimal proof that (0,1) is uncountable | Sep 27, 2017 |

A A "Proof Formula" for all maths or formal logic? | Apr 19, 2017 |

Discrete math proofs help. | Mar 24, 2009 |

Discrete math venn diagram proof | Apr 23, 2008 |

**Physics Forums - The Fusion of Science and Community**