A reformulation of Hadwiger’s conjecture

Let G = (V,E) be a finite, simple, undirected graph. Hadwiger’s conjecture states that

if n = \chi(G) then K_n is a minor of G.

Let’s call that statement (Hadw). We show that it is equivalent to the following statement:

(Hadw’): If G is not a complete graph, then there is a minor M of G such that

  1. M \not \cong G, and
  2. \chi(M) = \chi(G).

It is clear that (Hadw) implies (Hadw’). For the other direction, take any finite graph G and let n = \chi(G). If G is complete, we are done. If not, use (Hadw’) and let M_1 be a proper minor such that \chi(M_1) = n. If M_1 is complete, we are done, otherwise use (Hadw’) again to get a proper minor M_2 of M_1 with \chi(M_2) =n. And so on. Since G is finite, this procedure is bound to end at M_k for some k\in\mathbb{N}. We
have \chi(M_k) = n, and since the procedure ended at k, the graph M_k must be complete. So we get statement (Hadw).

About dominiczypen

I'm interested in general topology, order theory, and graph theory. This link takes you to my preprints on arXiv.
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s