Contrapositive help understanding these specific examples from Graph Theory

Question

Can somebody explain the contrapositive logic used in this Graph Theory textbook (Introduction to Graph Theory 2nd Edition by D.B. West) when proving Hall's Theorem, and also when proving Berge's Theorem (both proofs along with the contrapositives are on pg. 110 of the textbook)?

I have provided the relevant theorems and excerpts below (so one need not have the textbook):

Berge's Theorem: A matching M in a graph G is a maximum matching iff G has no M-augmenting path.

relevant proof-excerpt: "We prove the contrapositive of each direction; G has a matching larger than M if and only if G has an M-augmenting path.... For the converse, let M’ be a matching in G larger than M; we construct an M-augmenting path."

Hall's Theorem: An X,Y-bigraph G has a matching that saturates X iff |N(S)|$\geq$|S| $\forall$ S $\subseteq$ X.

relevant proof-excerpt: "To prove that Hall’s Condition is sufficient, we prove the contrapositive. If M is a maximum matching in G and M does not saturate X, then we obtain a set S $\subseteq$ X such that |N(S)|<|S|."

I know what a contrapositive is: $(P \Rightarrow Q) \equiv (\neg Q\Rightarrow\neg P)$, but I find these contrapositives complicated to understand.

Answer 1

Sorry, right after asking, I was able to figure it out, as if speaking to rubber-ducky.

For Berge's Theorem, the contrapositive is quite simple. A rewording of the contrapositive given states the following: G has matching M' that is not a maximum matching of G iff there exists an M-augmenting path. Also, since this is an "iff" statement, it is a biconditional statement, so the order of the statements can be flipped around when proving in one particular direction (i.e.: $(P \Leftrightarrow Q) \equiv ((P\Rightarrow Q) \land (Q\Rightarrow P)) \equiv ((\neg Q \Rightarrow \neg P) \land (\neg P \Rightarrow \neg Q))$).

For Hall's Theorem, the contrapositive is similarly straightforward. One need simply realize that having a matching that saturates a partite set, X, in a bipartite graph, G, which is the union of two partite sets $X\cup Y$, is obviously the same thing as having a maximum matching in G (because edges in a matching of a bipartite graph clearly must not go between two vertices of the same partite, by definition of bipartite). Then, this statement follows by the same logic that the contrapositive used in the proof of Berge's Theorem (above) follows. $\mathbb{\square}$

Answer 2

The contrapositive of the conditional $p\implies q$ is $\lnot q\implies\lnot p $.

And the contrapositive of the biconditional $p\leftarrow\rightarrow q$ (which is actually equivalent to ($p\implies q)\land(q\implies p)$) is ($\lnot q\implies \lnot p )\land(\lnot p\implies \lnot q)$