Prove The Graph Formed by joining 2 Graphs Colorable in k colors by k-1 Edges is Colorable in k Colors The crux of the proof for a graph with $\chi(G)=k+1$ being $k-1$ edge connected relies on the construction that demonstrates a graph $G$ formed by the joining of 2 graphs $G_1$ and $G_2$ each colorable in $k$ colors is colorable in $k$ colors.
It seems obvious to me that this should be true since you only need to join $k-1$ of the $k$ color classes in $G_1$ to the $k$ color classes $G_2$, but I don't see how to construct this formally. Could someone please help by either illustrating this construction or at least pointing me in the right direction?
It may help to know that the original proof by Lovász seems to use infinite descent induction after showing some construction that allows the first color class in $G_1$ to be mapped to one in $G_2$ but I don't understand it.
 A: Let's suppose $G_1$ is colored using colors $C_1, C_2, \dots, C_k$ and $G_2$ is colored using colors $D_1, D_2, \dots, D_k$. We want to color $G$ by relabeling the colors of $G_2$ to $C_1, C_2, \dots, C_k$ in such a way that the edges between the two graphs have endpoints of different colors.
Here's an approach to doing it that might be simpler to think about. Let's just relabel $D_1, D_2, \dots, D_k$ randomly: pick a uniformly random permutation $\sigma$, and replace all instances of $D_i$ with $C_{\sigma(i)}$ for $i=1,2,\dots, k$.
For each of the edges between $G_1$ and $G_2$, the random approach has a $\frac1k$ chance of failing. (Suppose the edge goes from a $C_i$-colored vertex to a $D_j$-colored vertex. There's a $\frac1k$ chance that the random permutation $\sigma$ has $\sigma(j) = i$, so that $D_j$ gets relabeled to $C_i$ and the edge is not properly colored.)
In the very worst case, these failure events are all disjoint: there is no overlap between choices of $\sigma$ that are bad for the first edge, choices bad for the second edge, and so on. But even then, the probability that the random approach fails for any edge is at most
$$
   \underbrace{\frac1k + \frac1k + \dots + \frac1k}_{\text{$k-1$ terms}} = \frac{k-1}{k} < 1.
$$
The only way that the probability of failure can be less than $1$ is if there is a relabeling that works for every edge, and this is what we wanted to show.
