Show that if the edge set of a graph $G(V,E)$ with $n$ nodes
can be partitioned into $2$ trees,
then there is at least one vertex of degree less than $4$
I have tried to prove this problem with the help of the method of contradiction.
Assume that all vertices of the graph $G$ has degree $\geq 4$
Assume the graph $G$ is partitioned into two trees $T_1$ and $T_2$.
With the help of the above assumptions the only observation I could make is that for every vertex $v$ in $G$ degree of $v$ must be greater than or equal to $2$ in either $T_1$ or $T_2$.
I don't know how proceed with this. Please help.
If my approach for solving this problem is wrong then please provide a different solution.
First of all, trees have a characteristic of $$n = e + 1$$ where $n$ is the number of vertices (nodes) and $e$ is the number of edges. We also have a Handshaking Lemma, which states that $$\sum_{i = 1}^n d_i = 2e$$ where $d_i$ is the degree of $i^{th}$ vertex and $e$ is as above.
Now, suppose $G$ is partitioned into two trees with $e_1$ and $e_2$ edges, with $e_1 + e_2 = e$, and $n_1$ and $n_2$ vertices (not necessarily $n_1 + n_2 = n$). Also, we will have some mutual vertices, say $k$ of them, namely $n_{m_1}, ...,n_{m_k}$. Then we have the following equations: $$n_1 = e_1+1\ (\text{I})$$ $$n_2 = e_2+1\ (\text{II})$$ Now, as you suggested, suppose for a contradiction that every vertex of $G$ has degree greater than or equal to $4$, that is $d_i \ge 4$ for all $i$. Then by Handshaking Lemma, $$4n \le 2e \implies e \ge 2n\ (\text{III})$$ Then, by summing up (I) and (II), we have $$n+k = e + 2$$ (Here notice that we have some mutual vertices so when we sum $n_1$ and $n_2$, we add them twice. I included one mutual pair to $n$ and wrote the other mutual pair seperately as $k$).
Now, by using (III), we have the inequality $$n+k - 2 \ge 2n \implies k \ge n+2$$ This statement says number of mutual vertices $k$ is greater than number of total vertices $n$, which is a contradiction as required.