Here is the definition of Hajós construction.
Let $G$ and $H$ be two undirected graphs, $vw$ be an edge of $G$, and $xy$ be an edge of $H$.
Then the Hajós construction forms a new graph that combines the two graphs by identifying vertices $v$ and $x$ into a single vertex, removing the two edges $vw$ and $xy$, and adding a new edge $wy$.
In many papers about Hajós construction, they consider the following statement as a 'fact':
If $G$ and $H$ are $k$-critical, then applying Hajós construction to $G$ and $H$ obtains a $k$-critical graph.
But I have no idea with how to prove it.
Would you help me?
Best Answer
Let $G$ and $H$ be $k$-critical graphs and $G +_h H$ be the Hajós construction applied to $G$ and $H$ with respect to $vw \in E(G)$ and $xy \in E(H)$. Since $G$ and $H$ are $k$-critical, $G-vw$ and $H-xy$ both have $(k-1)$-colourings. Permute the colours so that the colour of $v$ is the same as the colour of $x$. Then recolour $w$ with the new colour $k$. This yields a $k$-colouring of $G +_h H$. Towards a contradiction, suppose $c$ is a $(k-1)$-colouring of $G +_h H$. Since $\chi(G)=k$, we must have $c(v)=c(w)$. Similarly, since $\chi(H)=k$, $c(x)=c(y)$. This implies $c(w)=c(y)$, which contradicts that $c$ is a proper colouring. Thus, $\chi(G +_h H)=k$.
It remains to show that for every edge $e$ of $G +_h H$, removing $e$ decreases the chromatic number of $G +_h H$. If $e=wy$, then the previous argument (without the recolouring step) shows that $\chi( (G +_h H) \setminus e) \leq k-1$. Therefore, by symmetry, we may assume that $e \in E(G)$. Since $G$ is $k$-critical, $G \setminus e$ has a $(k-1)$-colouring $c$. Since $H$ is $k$-critical, $H \setminus xy$ has a $(k-1)$-colouring $c'$. Since $\chi(H)=k$, $c'(x)=c'(y)$. Since $vw \in E(G \setminus e)$, $c(v) \neq c(w)$. Therefore, permuting the colours so that $c(v)=c'(x)$ gives a $(k-1)$-colouring of $(G +_h H) \setminus e$.