Let's assume that Graph $G = <V,E>$ has two Spanning Trees $G_a = <V, T_1>$ and $G_b = <V,T_2>$ where $T_1 \cap T_2 = \emptyset$ and $T_1 \cup T_2 = E$. Prove that $\chi(G) \le 4$
$\chi(G)$ is the chromatic number.
Well I know that every tree can be colored by only two colors. Will this help ?
I think it's necessary to disprove the existence of $K_5$ clique. But how ?
Don't worry about $K_5$, but you do want to start off with coloring both $G_a$ and $G_b$ with two colors, say $0$ and $1$. Now you want to somehow combine these two colorings into a coloring of $G$. Well, what happens if you just concatenate the colors from $G_a$ and $G_b$ on each vertex? E.g., if $v$ is colored $0$ in $G_a$ and colored $1$ in $G_b$, color it $01$ in $G$.
So is this a proper coloring of $G$ using colors $00,01,10,11$?
Added: By the way, such a graph can certainly not have a $K_5$ subgraph, since otherwise, $G_a$ or $G_b$ would have at least $5$ edges from this subgraph, and thus would contain a cycle. However, while not having a $K_5$ subgraph is a necessary condition for $\chi(G)\leq 4$, it is not sufficient!