= Mycielskian chromatic increase
{c}
{title2=$\chi(\mu(G))=\chi(G)+1$}
For a nonempty finite <simple graph>, the upper bound copies an optimal <proper vertex colouring> to its <Mycielski shadow vertices> and gives the <Mycielski apex> a fresh colour. For the lower bound, suppose $\mu(G)$ uses $k=\chi(G)$ colours, with $w$ coloured $k$. Shadows avoid $k$. Replace colour $k$ at each original $v_i$ by $u_i$'s colour. Changed originals form an <independent set>; unchanged neighbours differ because $u_iv_j$ is an <edge>. This <proper vertex colouring> of $G$ uses $k-1$ colours, contradicting its <chromatic number>.<Mycielski graphs and PR proofs by Emre Yolcu and others>[§4.1, Proposition 1 and proof, manuscript pp. 6–7]{ref}
The nonempty condition means $V(G)\ne\varnothing$, not $E(G)\ne\varnothing$. An edgeless $n$-<vertex> <graph> with $n\geq1$ has <chromatic number> one; its <Mycielskian> is a <star graph> on $w,u_1,\ldots,u_n$ together with $n$ <isolated vertices>, and needs two colours. If $G$ has no <vertices>, $\mu(G)$ is a single <vertex>, so the same formula also holds with the convention $\chi(G)=0$.
Back to article page
