Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 ?

share|cite|improve this question

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!

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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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