- #1
ych22
- 115
- 1
I was attempting a simple graph theory question.
"Let G=(V,E) be a simple graph with n>=3 vertices and 2n-3 edges. Suppose that every subgraph with m(>=2) vertices has <= 2m-3 edges. Let S be the minimum degree for any vertex in V. Prove that S is either 2 or 3."
So I let A be the statement "G=(V,E) is a simple graph with... has <= 2m-3 edges."
Let B be the statement "S is the minimum degree...either 2 or 3".
Is my job to prove that A->B? Can I prove ~B->~A instead? That is, I want to show that if S is 0,1, or >3 then G cannot be a ... with every subgraph with ...
I am self-learning discrete maths and have some uncertainty in propositional logic.
"Let G=(V,E) be a simple graph with n>=3 vertices and 2n-3 edges. Suppose that every subgraph with m(>=2) vertices has <= 2m-3 edges. Let S be the minimum degree for any vertex in V. Prove that S is either 2 or 3."
So I let A be the statement "G=(V,E) is a simple graph with... has <= 2m-3 edges."
Let B be the statement "S is the minimum degree...either 2 or 3".
Is my job to prove that A->B? Can I prove ~B->~A instead? That is, I want to show that if S is 0,1, or >3 then G cannot be a ... with every subgraph with ...
I am self-learning discrete maths and have some uncertainty in propositional logic.