# Graph G with two Spanning Trees

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!
Well, suppose you have two vertices in $G$ joined with an edge and both colored the same color. Argue that such a situation would contradict the "proper coloringness" of the coloring of either $G_a$ or $G_b$. – Casteels Feb 26 '14 at 12:16