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

(Hadw): $K_{\chi(G)}$ is a minor of $G$.

It turns out that for finite graphs, (Hadw) is equivalent to the following statement:


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

(For an explation of the equivalence of (Hadw) and (Hadw2) in the finite case, see this.)

It is easy to see that (Hadw) fails for graphs with infinite chromatic number: $G:=\bigcup_{n\in\omega} K_n$ has chromatic number $\omega$, but $K_\omega$ is not a minor of $G$.

Question: Is (Hadw2) also false for graphs with infinite chromatic number?

  • 2
    $\begingroup$ Is there an easy example? (I got 2 +votes and 2 -votes, plus one close-vote, people seem quite divided on whether this is a valid question or rubbish). $\endgroup$ Commented Oct 23, 2015 at 15:20

1 Answer 1


First, suppose $G$ has a connected component $C\subseteq G$ with the same chromatic number as $G$. If $C\neq G$, we can take $M=C$. If $G=C$, let $M$ be the subgraph of $G$ obtained by removing all edges involving some fixed vertex $v\in G$.

Now suppose $G$ has no connected component with the same chromatic number as $G$. It follows that we can choose an collection of connected components $C_i$ of $G$ such that each $C_i$ has a different chromatic number and $\chi(G)=\sup_i \chi(C_i)$. You can now let $M$ be the union of all but one of the $C_i$.

  • 2
    $\begingroup$ Can't you simplify the argument slightly? If $G$ has isolated vertices, remove them all, and obtain a subgraph $M$ with no isolated vertices. If $G$ has no isolated vertices, remove all edges incident with some fixed vertex $v,$ and obtain a subgraph $M$ with one isolated vertex. $\endgroup$
    – bof
    Commented Oct 24, 2015 at 1:44
  • $\begingroup$ Looks good to me. $\endgroup$ Commented Oct 24, 2015 at 1:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.