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$)?



Representing graphs as unions of trees
1. (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.
2. (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$.


