# Are there digraphs such that any two arborescences are arc-disjoint?

Let $$D=(V,A)$$ be a directed graph with root $$r$$. An $$r$$-arborescence of $$D$$ is a subgraph such that for any $$v\in V-r$$, there is exactly one directed path from $$r$$ to $$v$$. Hence an $$r$$-arborescence is a directed spanning tree whose arcs are directed away from $$r$$.

Question: Is there a directed graph $$D=(V,A)$$ with root $$r$$ such that any two $$r$$-arborescences of $$D$$ are arc-disjoint?

## 1 Answer

Leaving aside the trivial case (graphs which only have one $$r$$-arborescence), this won't be possible.

Suppose $$(V,E)$$ is an $$r$$-arborescence of $$(V,A)$$. Then $$E$$ contains some (nonzero) number of arcs $$(r,s_1),\ldots,(r,s_k)$$ out of the root (otherwise we are in a trivial case). Now if $$(V,F)$$ is another arborescence, then either

• $$F$$ also contains some $$(r,s_i)$$, so the arborescences are not arc-disjoint, or
• $$F$$ contains $$(r,t)$$ for some $$t\notin\{s_1,\ldots,s_k\}$$, and for each $$i$$, an arc $$(p_i,s_i)$$ for some (not necessarily distinct) vertices $$p_1,\ldots,p_k\neq r$$. But then we can replace one such arc with $$(r,s_i)$$ - it is easy to see that $$(V,F\cup\{(r,s_i)\}\setminus\{(p_i,s_i)\})$$ is again an $$r$$-arborescence: For any vertex $$v$$ in the subtree of $$(V,F)$$ rooted at $$s_i$$, the only path from $$r$$ to $$v$$ is now the old one, with the prefix up to $$s_i$$ replaced by $$(r,s_i)$$; for all other vertices, the paths remain unchanged. This new arborescence is distinct from $$(V,E)$$ since it still contains $$(r,t)$$, but they are not arc-disjoint since they both contain $$(r,s_i)$$.
• Thank you so much for such a quick reply! – hxiao Aug 9 '19 at 4:48