If $G$ has two $k$-colorable subgraphics then $G$ is $k$-colorable Let $G$ be a graph such that $V (G)$ = $X∪Y$ and there are at most $k - 1$ XY-edges. Suppose the sub-graph generated by $X$ is $k$-colorable by vertices, and the sub-graph generated by $Y$ is also $k$-colorable by vertices. Show that $G$ is also $k$-colorable.
It is clear that the graph $G$ is not bipartite, since it has edges within $X$ and $Y$, also $X$ and $Y$ are disjoint
Let's say that $H_1$ is the subgraph induced by $X$ and $H_2$ subgraph induced by $Y$
Since $H_1$ is $k$-colorable, there exists $γ_1$ :$ X → [k]$
Since $H_2$ is $k$-colorable, there exists $γ_2$ :$ Y → [k]$
To prove that $G$ is $k$-colorable we need to find a function $Γ$ : $X∪Y → [k]$
However I don't quite understand how I can do it, can you help me?
 A: Suppose that we define $\Gamma: X \cup Y \to [k]$ by choosing one of the $k!$ bijections $\phi : [k] \to [k]$ uniformly at random, and defining
$$
    \Gamma_\phi(v) = \begin{cases} \gamma_1(v)  & v \in X \\ \phi(\gamma_2(v)) & v \in Y\end{cases}
$$
For every edge $xy$ where $x \in X$ and $y \in Y$, the probability that $\gamma_1(x) = \phi(\gamma_2(y))$ is always $\frac1k$, because $\phi(\gamma_2(y))$ is equally likely to be any of the $k$ colors. There are only $k-1$ such edges.
Therefore the expected number of edges between $X$ and $Y$ where $\Gamma_\phi$ fails to be a $k$-coloring is only $(k-1) \cdot \frac1k$. This means that there must be a choice of $\phi$ for which $\Gamma_\phi$ has fewer than $\frac{k-1}{k}$ bad edges: that is, no bad edges at all.
A: A graph is k-colorable if it is possible to color the vertices of the graph using $k$ colors in such a way that no two connected vertices receives the same color. The question says that the vertex set of the graph $G$,$V(G)$ can be partitioned into two sets $(A,B)$ such that the number of edges with one end in $A$ and another end in $B$ is bounded by $k-1$. We also know that the sub-graph induced by $A$ or by $B$ is $k$ color-able. 
However, knowing those facts wouldn't deduce that the graph is not bipartite. Right? If you have less than $k$ vertices in $A$ or $B$ then for sure the subgraph induced by $A$ or by $B$ will be $k$ color-able(because even if you assign a different color to vertices in $A$ or in $B$, you would still need at most the number of vertices in $A$ color to color the vertices in $A$, similarly, you would need at most the number of vertices in $B$ colors to color vertices in $B$). 
We know that the subgraph induced by $A$ and the subgraph induced by $B$ is $k$ colorable. So let's just do a proper coloring of both sub-graphs first. Ok after we have given a proper coloring to both sub-graphs, let us now look at the original graph $G$. Now there might be conflicting colors between some vertices in $A$ and some vertices in $B$. So let's look a such an edge $(a,b), a\in A, b\in B$.Let's say W.L.O.G that both are colored using color 1. Now because there are at most $k-1$ edges from $A$ to $B$, the vertex $b$ could be connected to at most $k-1$ vertices from $A$. So there must be at least one color out of the $k$ colors, say color i, that hasn't been used to color the neighbors of $b$ in $A$. So then we can swap the two colors 1 and i in all vertices in B that are colored using those two colors. After we did the swapping, the resulting is a proper coloring of the sub-graph induced by $B$, furthermore, the conflicting coloring for $(a,b)$ in the original graph is resolved. 
Hence, by doing this trick of locating the problematic colored pairing one from $A$, one from $B$ and do some color swapping, we can arrive to a proper coloring of the graph $G$ using at most $k$ color. And hence the graph $G$ is k-color-able. 
A: For $i\in[k]$ define
$$F_i=\{j\in[k]:(\exists x\in X)(\exists y\in Y)xy\in E(G)\land\gamma_1(x)=i\land\gamma_2(y)=j\}\subseteq[k].$$
Observe that 
$$\sum_{i=1}^k|F_i|\lt k.$$
Without loss of generality, we assume that
$$|F_1\ge|F_2|\ge\cdots\ge|F_k|.$$
To get a proper $k$-coloring of $G$, it will suffice to choose distinct colors $c_1,c_2,\dots,c_k\in[k]$ such that $c_i\notin F_i$; then we can recolor the vertices in $X$, giving color $c_i$ to vertices $x$ which initially had color $\gamma_1(x)=i$. In order to show that we can choose
$$c_i\in[k]\setminus(\{c_1,\dots,c_{i-1}\}\cup F_i),$$
it will suffice to show that
$$i-1+|F_i|\lt k.$$
This is clear if $|F_i|=0$, so suppose $|F_i|\ge1$. Then $|F_j|\ge1$ for all $j\lt i$, so
$$i-1+|F_i|\le|F_1|+\cdots+|F_{i-1}|+|F_i|\le\sum_{j=1}^k|F_j|\lt k.$$
