6
$\begingroup$

I am trying to prove the following result from my book:

Let $G$ be a directed graph with vertices $x_1,x_2,\dotsc, x_n$ for which a directed Eulerian circuit exists.

A spanning arborescence with root $x_i$ is a spanning tree $T$ of $G$, with root $x_i$, such that for all $j\ne i$ there is a directed path from $x_j$ to $x_i$ in $T$.

Show that the number of spanning arborescences of $G$ with root $x_i$ does not depend on $i$.

I understand that the sum of all the indegrees must match with the sum of all outdegrees in $G$, for each time we enter a vertex we also leave it. But that's about all I know.

Can someone help me in proving this result?

  • 0
    Possible duplicate of [Number of spanning arborescences does not depend on $i$.](https://math.stackexchange.com/questions/2137694/number-of-spanning-arborescences-does-not-depend-on-i)2018-05-07

0 Answers 0