Let $G=(V,E)$ be an infinite simple, undirected graph with $\chi(G) \geq \aleph_0$. Is there a minor $M$ of $G$ such that
- $M\not\cong G$, and
- $\chi(M)=\chi(G)$
?
MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this communityLet $G=(V,E)$ be an infinite simple, undirected graph with $\chi(G) \geq \aleph_0$. Is there a minor $M$ of $G$ such that
?
For every such $G$ there is an $M$ satisfies your requirement.
It is enough to show that for every graph $G$ with infinite chromatic number has two minors $G_{0}$ and $G_{1}$ such that
$(i)$ $G_{0}$ has no isolated vertex and $G_{1}$ has exact one isolated vertex, and
$(ii)$ $\chi(G_{0}) = \chi(G_{1}) = \chi(G)$.
Proof:
Case 1: If $G$ has at least one isolated vertices, then remove all of them to get $G_{0}$ and remove all but one of them to get $G_{1}$.
Case 2: If $G$ has no isolated vertices, choose one of its vertices, $\nu_{0}$, and remove all of edges which adjacent to $\nu_{0}$ then remove all of its isolated vertices (if there are any) other than $\nu_{0}$. We get our $G_{1}$. It is easy to see that $ \chi(G_{1}) = \chi(G)$. Since if there is a coloring function $c$ maps $V(G_{1})$ to $\kappa \geq \omega$, then let $C$ be the following map from $V(G)$ to $\kappa$:
$(a)$ $C(\nu) = c(\nu) + 2$ if $\nu$ is neither $\nu_{0}$ nor a leaf connected to $\nu_{0}$,
$(b)$ $C(\nu) = 1$ if $\nu$ is a leaf connected to $\nu_{0}$,
$(c)$ $C(\nu_{0}) = 0$.
This conclude the proof.