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 each $ |V_i| > |V|/2$ .
- $ |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.