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?



If $G$ and $H$ are $k$-critical, then applying Hajós construction to $G$ and $H$ makes $k$-critical graph
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$.


