How Do You Prove Minimum Vertex Degree in Graph Theory?

[ych22]

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.

 

[HallsofIvy]

Yes, proving a statement by proving its contrapositive (proving "A implies B" by proving "not B implies not A") is a standard method of proof.