# Number of ways to decompose a graph into two trees

Is there an efficient algorithm to count how many ways there are to decompose a given finite simple undirected connected graph $$G = (V, E)$$ into the union of two trees $$T_1 = (V_1, E_1)$$ and $$T_2 = (V_2, E_2)$$ that are not necessarily edge-disjoint? By union I mean $$V = V_1 \cup V_2$$ and $$E = E_1 \cup E_2$$. My initial thoughts:

1. $$V_1$$ and $$V_2$$ cannot be disjoint, so $$|V_1| + |V_2| > |V|$$.
2. $$|V_1| + |V_2| \geq |E| + 2$$ because $$E_1 \cup E_2 = E$$ and $$|E_i| = |V_i| - 1$$.
3. If $$G$$ is a tree then we are counting the number of ways to write $$V = V_1\cup V_2$$ where $$V_1$$ and $$V_2$$ are not disjoint. This can be presumably calculated analytically.
• 3. It's not that simple. Consider tree $1-2-3$: you can't split it as $(1,3)$ and $(2)$. While you do can compute the answer for the case when $G$ is a tree, it's by no means trivial. Currently, I'm not sure it's possible to do this for general graphs efficiently. We can use property 2 (it must hold $2|V| \ge |E| + 2$ for any subgraph) to say that the answer is 0 in some cases. – Dmitry Aug 5 at 13:08
• Your example comprises disjoint vertex sets. – abhi01nat Aug 5 at 13:14
• $1-2-3-4-5$ split as $(1,2,4,5)$ and $(2,3,4)$ – Dmitry Aug 5 at 13:28
• Ah ok understood, thanks! – abhi01nat Aug 5 at 13:32
• @abhi01nat property 1 isn't actually true right? Shouldn't it be $|V_1|+|V_2| > |V|$? Both trees don't have to contain more than half of the nodes only one of them has to. (I'm criticizing the phrase "so each"). – plshelp Aug 11 at 13:43