Ore's theorem & Contraposition

Question

This is a question about contraposition i.e.

if P implies Q then it is logically equivalent to not Q implies not P (~Q implies ~P)

What is wrong with the following taken from Graph Theory?

Let G be a (finite and simple) graph with n ≥ 3 vertices. We denote by deg v the degree of a vertex v in G, i.e. the number of incident edges in G to v. Then, Ore's theorem states that if

deg v + deg w ≥ n for every pair of distinct non-adjacent vertices v and w of G

then G is Hamiltonian.

If P = deg v + deg w ≥ n for every pair of distinct non-adjacent vertices v and w of G

and

Q = G is Hamiltonian.

Is it a valid statement to say, using ~Q implies ~P, that

Not Hamiltonian implies that deg v + deg w < n for every pair of distinct non-adjacent vertices v and w of G

This argument suggests a way of working out if a graph is not Hamiltonian! What is wrong with the argument?

Answer 1

First, the negation of $P$ is not "$\deg(v) + \deg(w) < n$ for every pair of distinct, non-adjacent $v,w$" but "there exists a pair of distinct, non-adjacent $v,w$ for which $\deg(v) + \deg(w) < n$". So that's all that being non-Hamiltonian implies.

In general, the negation of a property that says "all things behave in a certain way" is "at least one thing behaves differently", not "all things behave differently".

Second, Ore's theorem can never help us work out if a graph is not Hamiltonian. It gives us a condition that, if true, tells us that $G$ is Hamiltonian. If $P$ is false, we do not learn anything.