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$ 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
    Oct 24, 2015 at 1:44
  • $\begingroup$ Looks good to me. $\endgroup$ Oct 24, 2015 at 1:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .