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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|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.