Proofs (discrete mathematics)

In summary, the conversation is about a student seeking help with homework problems involving proofs. The first problem is to prove that the Grötzsch graph is not 3-colorable using proof by contradiction. The student is unsure how to continue the proof after assuming the graph is 3-colorable. The second problem is to prove that the K 5,5 graph is not planar using proof by cases. The student has started by defining planar and stating that the graph cannot be rearranged to have no crossing edges. The third problem involves proving the equation (B − A) ∪ (C − A) = (B ∪ C) − A for any sets A, B, and C. The student is unsure how
  • #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.
 
Last edited:
Physics news on Phys.org
  • #2
no help?
 

Related to Proofs (discrete mathematics)

1. What is a proof in discrete mathematics?

A proof in discrete mathematics is a logical argument that shows the validity of a mathematical statement. It involves using deductive reasoning and mathematical concepts to demonstrate that a statement is true.

2. Why are proofs important in discrete mathematics?

Proofs are important in discrete mathematics because they provide a rigorous and systematic way of verifying the truth of mathematical statements. They help to establish the validity of mathematical concepts and theorems, which are essential for further understanding and application in various fields.

3. What are the different types of proofs used in discrete mathematics?

There are several types of proofs used in discrete mathematics, including direct proofs, indirect proofs, proof by contradiction, and proof by mathematical induction. Each type of proof has its own specific structure and method of reasoning.

4. How do you construct a proof in discrete mathematics?

To construct a proof in discrete mathematics, you first need to understand the problem or statement you are trying to prove. Then, you need to determine the appropriate proof technique to use and start by writing down the assumptions and definitions. Next, you use logical reasoning and mathematical concepts to derive a conclusion that follows from the assumptions and definitions.

5. What are some common mistakes to avoid when writing proofs in discrete mathematics?

Some common mistakes to avoid when writing proofs in discrete mathematics include using incorrect notation, making assumptions that are not explicitly stated, and using circular reasoning. It is also important to clearly explain each step of the proof and to avoid jumping to conclusions without proper justification.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
11
Views
662
  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
777
  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
801
  • Computing and Technology
Replies
2
Views
381
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
932
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
5
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
Back
Top