# Large chromatic number implies a clique (weakened Hadwiger's conjecture)

This is an exercise from chapter 7 of Diestel's 'Graph theory':

Show that there exists a function $$f$$ such that each graph $$G$$ of chromatic number at least $$f(r)$$ contains a $$K_r$$ minor.

My attempts Use induction on $$r$$.

I try to find a vertex $$u\in V(G)$$ such that $$N(u)$$ induces a subgraph whose chromatic number is at least $$f(r-1)$$.

Pick an arbitrary vertex $$v$$. We may assume that $$\chi(G-v)=f(r)-1$$, otherwise eliminate $$v$$ and continue with $$G-v$$. Now, in any vertex coloring of $$G$$, $$N(u)$$ uses $$f(r)-1$$ colors. However, this may be due to some structure in $$G-(\{u\}\cup N(u))$$. And I am stuck here.

Additional information that may be useful

Some references attribute a result to Klaus Wagner in 1964. Seemingly this well-known mathematician wrote few English articles and I even failed to find his original paper.

Note that this is only an exercise and I post it here deliberately instead of overflow. Recent progress on this conjecture is welcomed but that's not my purpose.

Thanks!

• The usual (as far as I know) way to prove this is in two steps: 1) you prove that any graph with chromatic number $k$ contains a subgraph with min degree at least $k-1$, or said otherwise, a $k$-degenerate graph has chromatic number at most $k + 1$. I think this is done by induction on the number of vertices. 2) Then the second step is Mader theorem, every graph with large average degree contains a complete minor. Commented Aug 4, 2023 at 0:24
• FYI, Wagner and Mader Theorem should be both in Diestel. Commented Aug 4, 2023 at 0:26
• Thanks for your comment @ThomasLesgourgues. That helped me to come up with a valid proof! It occurs that Diestel removes Mader's theorem (1967) from exercises in chapter 7 in the 5th edition, but I somehow found it in the 3rd edition (2006). Besides, in the 5th edition, exercises that aim for proof of a named theorem no longer mention the name as RD wrote in the preface. Again, thanks for your hint! Commented Aug 4, 2023 at 6:34

This answer is fully inspired by @Thomas Lesgourgues.

Lemma A graph $$G$$ in which $$|E(G)|\geq 2^{k-3}|V(G)|$$ contains a $$K_k$$-minor.

Proof

If $$G$$ has some edge $$e$$ included in less than $$2^{k-3}$$ triangles, then $$E(G/e)\geq 2^{k-3}V(G)-2^{k-3}=2^{k-3}(V(G)-1)$$. Hence, we switch to $$G/e$$ to find a $$K_k$$-minor. Noted that this cannot always happen, so we will arrive at some graph $$G$$ where each edge $$e$$ lies in at least $$2^{k-3}$$ triangles.

Let $$t(e)$$ be the number of triangles that contain $$e$$. We have a crucial observation: $$\sum_{v\in V}|E(G[N(v)])|=\sum_{e\in E(G)}t(e)\geq 2^{t-3}|E(G)|=2^{t-4}\sum_{v\in V}d(v).$$

The first '=' comes from the double counting of $$\{(v,e)\in V\times E:\text{v is the opposite vertex to e in some triangel}\}.$$

Thus, we come up with some vertex $$v$$ such that $$H=G[N(v)]$$ satisfies $$|E(H)|\geq 2^{k-4}d(v)$$. Hence, we may apply induction on $$k$$ to discover a $$K_{k-1}$$-minor in $$H$$ and come up with a $$K_k$$-minor in $$G$$ together with $$v$$.

Lemma A graph $$G$$ whose chromatic number is at least $$k$$ contains a subgraph $$H$$ where $$\delta(H)\geq k-1$$.

Proof

Keep removing vertices in $$G$$ to obtain a $$k$$-critical subgraph $$H$$.

In the end, we derive

Theorem Every $$(2^{k-2}+1)$$-chromatic graph has a $$K_k$$ minor.