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!

  • $\begingroup$ I don't see why this is correct. How can u be sure that there is no need for the fifth color? $\endgroup$ – lvi Feb 26 '14 at 12:07
  • 1
    $\begingroup$ 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$. $\endgroup$ – Casteels Feb 26 '14 at 12:16
  • $\begingroup$ OHHH ! Now I get it. Thank you! $\endgroup$ – lvi Feb 26 '14 at 13:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.