Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Let $G$ be a directed graph with vertices $x_1,x_2,\cdots 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 thats about all I know. Can someone help me in proving this result?


share|improve this question
aborescences can be made from a euclidean circuit by subtracting the edge in each cycle which goes away from the root. number of arborescences for any root = number of euclidean circuits of graph –  Angela Richardson Jan 1 '12 at 9:03

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.