# Proofs by saturating graphs

Recently I saw some graph theory proofs works like the following:

Theorem: If A then B.

Proof: Assume G be a counterexample of A, then saturate the graph(as in add edges) until adding any edge will violate A. Let the saturated graph be G'. Then use G' to derive a contradiction.

Why don't we just chose a saturated graph instead of spending a few sentence to pick any counterexample and then build a saturated example?

Note: A a saturated counterexample always exists if there is a counterexample. For any finite non-empty set, give an partial order, then there exist a maximal element. One can use this to prove any finite non-empty set of graphs A, there has to be a saturated graph(as in adding one more edge, the graph is no longer in A).

-

Let $G$ be a counterexample to $A$. Saturate the graph by adding edges until adding any edge will violate $A$. Let the saturated graph be $G'$. Then...
Let $G$ be a saturated counterexample to $A$, where a graph is saturated if it is impossible to add edges without violating $A$. Then ...