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).

Your note is twice as long as the proof you're criticizing :-) The proof, like your note, is essentially just briefly explaining why there must be a saturated graph. Even just explaining the term "saturated graph" would take up about as much space. Compare:

> 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 ...

This saves only a couple of letters, but fails to explain why there should be such a counterexample. Unless the level of the text is such that this can be assumed to be obvious, the first seems preferable.