[Math] A Graph as a Union of K forests.

Question

I want to show that a graph G that is a union of k forests has a chromatic number of at most 2k.
I have narrowed my problem down to trying to show that any graph G that is a union of n trees has a vertex of degree at most 2n-1, thus I can show that G is 2k-1 degenerate and prove this theorem by using a known inequality (Chromatic Number $\leq$ Degeneracy of G + 1). that would suffice because any subgraph of G would also be a union of k forests or less, so G would indeed be 2k-1 degenerate.

However I've had difficulties proving this general fact about graphs made of unions of forests and would appreciate some guidance. I'm not sure what the best approach would be, some traits of trees/forests or something else, was unable to make progress via induction.

Thanks a million!

Answer 1

Hint. Let $G$ be a graph which is the union of $k$ forests. (By the way, since a subgraph of a forest is a forest, each subgraph of $G$ is also the union of $k$ forests.)
(a) Find an upper bound (in terms of $k$ and $n$) for the size (number of edges) of $G$.
(b) Find an upper bound for the average degree of a vertex in $G$.
(c) Show that $\delta(G)\le2k-1$. ($\delta = $minimum degree.)
(d) Show that $\chi(G)\le2k.$ Use induction on the number of vertices, unless "degeneracy" has been covered. [P.S. Oops, I just noticed that you mentioned degeneracy in your question! I apologize for my careless reading!]

Spoilers:

An $n$-vertex forest has at most $n-1$ edges. Since $G$ has $n$ vertices and is the union of $k$ forests, $G$ has at most $k(n-1)$ edges. Hence the degree-sum of $G$ is at most $2k(n-1)$, and the average degree is at most $\dfrac{2k(n-1)}n=2k-\dfrac{2k}n\lt2k$. Since the average degree is less than $2k$, there must be a vertex of degree less than $2k$. Let $v$ be a vertex of degree less than $2k$. By the induction hypothesis, the graph $G-v$ is $2k$-colorable. Since $v$ is adjacent to at most $2k-1$ vertices in $G-v$, there is at least one color available for $v$.

This argument only applies to a finite graph $G$, but the theorem is also true for infinite graphs; the infinite case follows from the finite case by the De Bruijn–Erdős theorem.