Representing graphs as unions of trees Suppose that $G$ is a simple connected (infinite) locally finite graph (i.e. each vertex has finite valence). Is $G$ a union of finitely many trees? If not, does it hold for graphs $G$ of  bounded valence (i.e. there exists $d$ such that the valence of each vertex is $\le d$)?
 A: If $G$ has colouring number or degeneracy at most $d$ (i.e there is a well=order $<^*$ such that for every vertex $v$ the number of neighbours $w$ of $v$ such that $w <^* v$ is less than $d$) then there is a cute argument (I think originally due to Erdős and Hajnal see this paper) that $G$ is the union of at most $d-1$ forests.
The idea is to rainbow colour for each $v$ the set $E_v$ of `backwards' edges at $v$, that is $E_v = \{ (u,v) \in E(G) \colon u <^* v\}$, with the colours $[d-1]$, which is possible since each $E_v$ has size at most $d-1$. We claim that each colour class is acyclic, and hence a forest. Indeed, if some colour class contains a cycle $C$, then since $C$ is finite it contains a largest vertex $v$ in the well-order. However then both edges in $C$ meeting $v$ must be in $E_v$, contradicting the fact that $C$ was monochromatic.
In fact, for infinite $\lambda$, having colouring number $\lambda^+$ is equivalent to being expressible as the union of $\lambda$ many forests, as shown in the same paper. The converse is not quite true for finite $\lambda$, although if you are expressible as the union of $\lambda$ many forests with $\lambda$ finite another nice compactness argument of Erdős and Hajnal shows that you have colouring number at most $2\lambda$. One should be able to build a counterexample to your other statement from this I expect, by exhibiting a locally finite graph with colouring number $\aleph_0$. For example a union of larger and larger complete graphs joined in a ray should probably work.
If you want the trees in your statement to be disjoint, then I don't know if there is a nice answer.
A: *

*(Unbounded valence.) No. Take disjoint complete graphs on $1,2,\ldots$ vertices and add  some edges between them just to make this connected. Since you need at least $n/2$ trees to cover $K_n$, you can not cover by finitely many trees.


*(Bounded valence.) You may cover such graph by $d$ forests (even if multiple edges are allowed, but certainly no loops). Indeed, the graph is obviously countable. Let $v_1,v_2,\ldots,$ be its vertices. Assume that for each $n$ you may cover the subgraph on $\{v_1,\ldots,v_n\}$ by $d$ forests $L_1^n,\ldots,L_{d}^n$. For each edge $e$ denote $f_n(e)=s\in \{1,2,\ldots,d\}$ if $e\in L_s^n$. By diagonal argument, there exists a subsequence $(n_k)$ such that $f_{n_k}(e)$ is eventually constant for all edges $e$. Denote this constant $f_{\infty}(e)$ and denote $L_i^\infty=\{e: f_{\infty}(e)=i\}$, $i=1,\ldots,d$. These are our forests.
After this compactness abstract nonsense is said, we should prove a statement for a finite graph. There is a Nash-Williams criterion: a finite graph $G=(V,E)$ is a union of $m$ forests if and only if for any $U\subset V$ the number of edges joining vertices of $U$ is at most $m(|U|-1)$. If all degrees are at most $d$, this number of edges is at most $d|U|/2\leqslant d(|U|-1)$ when $|U|\geqslant 2$ (and there is nothing to check for $|U|=1$).
Now, if your trees are allowed to have common edges, just add edges to these forests to make them trees. If they must be disjoint, the statement is again false: take an infinite path $v_1v_2\ldots$ and replace each edge $v_{2i-1}v_{2i}$ by a 4-cycle $v_{2i-1}u_iv_{2i}w_i$.
