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

### Like this:

Like Loading...

*Related*