Let be a finite, simple, undirected graph. Hadwiger’s conjecture states that
if then is a minor of .
Let’s call that statement (Hadw). We show that it is equivalent to the following statement:
(Hadw’): If is not a complete graph, then there is a minor of such that
- , and
It is clear that (Hadw) implies (Hadw’). For the other direction, take any finite graph and let . If is complete, we are done. If not, use (Hadw’) and let be a proper minor such that . If is complete, we are done, otherwise use (Hadw’) again to get a proper minor of with . And so on. Since is finite, this procedure is bound to end at for some . We
have , and since the procedure ended at , the graph must be complete. So we get statement (Hadw).