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:
- $V_1$ and $V_2$ cannot be disjoint, so $|V_1| + |V_2| > |V|$.
- $|V_1| + |V_2| \geq |E| + 2$ because $E_1 \cup E_2 = E$ and $|E_i| = |V_i| - 1$.
- 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.