<p>Leaving aside the trivial case (graphs which only have one <span class="math-container">$r$</span>-arborescence), this won't be possible.</p>

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

<ul>
<li><span class="math-container">$F$</span> also contains some <span class="math-container">$(r,s_i)$</span>, so the arborescences are not arc-disjoint, or</li>
<li><span class="math-container">$F$</span> contains <span class="math-container">$(r,t)$</span> for some <span class="math-container">$t\notin\{s_1,\ldots,s_k\}$</span>, and for each <span class="math-container">$i$</span>, an arc <span class="math-container">$(p_i,s_i)$</span> for some (not necessarily distinct) vertices <span class="math-container">$p_1,\ldots,p_k\neq r$</span>. But then we can replace one such arc with <span class="math-container">$(r,s_i)$</span> - it is easy to see that <span class="math-container">$(V,F\cup\{(r,s_i)\}\setminus\{(p_i,s_i)\})$</span> is again an <span class="math-container">$r$</span>-arborescence: For any vertex <span class="math-container">$v$</span> in the subtree of <span class="math-container">$(V,F)$</span> rooted at <span class="math-container">$s_i$</span>, the only path from <span class="math-container">$r$</span> to <span class="math-container">$v$</span> is now the old one, with the prefix up to <span class="math-container">$s_i$</span> replaced by <span class="math-container">$(r,s_i)$</span>; for all other vertices, the paths remain unchanged. This new arborescence is distinct from <span class="math-container">$(V,E)$</span> since it still contains <span class="math-container">$(r,t)$</span>, but they are not arc-disjoint since they both contain <span class="math-container">$(r,s_i)$</span>.</li>
</ul>

CC BY-SA 4.0
2019-08-09T04:48:57.183Z
Thank you so much for such a quick reply!
hxiao
CC BY-SA 4.0
2019-08-08T12:00:18.813Z
2019-08-08T12:00:18.813Z
Klaus Draeger
<p>Let <span class="math-container">$D=(V,A)$</span> be a directed graph with root <span class="math-container">$r$</span>.
An <span class="math-container">$r$</span>-<em>arborescence</em> of <span class="math-container">$D$</span> is a subgraph such that for any <span class="math-container">$v\in V-r$</span>, there is exactly one directed path from <span class="math-container">$r$</span> to <span class="math-container">$v$</span>.
Hence an <span class="math-container">$r$</span>-arborescence is a directed spanning tree whose arcs are directed away from <span class="math-container">$r$</span>.</p>

<p><strong>Question</strong>:
Is there a directed graph <span class="math-container">$D=(V,A)$</span> with root <span class="math-container">$r$</span> such that any two <span class="math-container">$r$</span>-arborescences of <span class="math-container">$D$</span> are arc-disjoint?</p>

<graph-theory><spanning-tree>
Are there digraphs such that any two arborescences are arc-disjoint?
hxiao
# Are there digraphs such that any two arborescences are arc-disjoint?

(Asked by: username_0 on 2019-08-08)

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?

**Tags:** graph-theory, spanning-tree

---

## 1 answers

### Answer by username_1 on 2019-08-08. Score: 1 | Accepted 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)$.

> **Comments:**
> **username_0**: Thank you so much for such a quick reply!  

---

