I've been doing some exercises about graph theory and I find myself stuck on this one with no idea of to proceed.

Here's the question :

How many different directed trees can be obtained if we assign all possible orientations to edges of an undirected tree having exactly n nodes ? How many of them will be rooted (directed) trees ?

I started by drawing but there's too many structures possible so I searched through the different formulas and equalities we've learned but can't figure out a way to apply any of them for that question.

Thanks in advance for reading my question and trying to help me.


[EDIT] So I just figured something out, simple but yet perfectly answering the question. You have $6$ edges in a $7$ nodes tree. Every edge can be placed in $2$ different directions so you can calculate the number of possible trees easily by writing $2^6 = 64$.
Then to figure out the number of rooted tree is pretty easy, you have $7$ nodes so $7$ possible starting points so $7$ rooted trees within those $64$.


I would attack it this way. I'd use the Matrix-Tree Theorem to obtain the number of unrooted spanning trees. You can then apply $n$ orientations to each tree. So by rule of product, multiply your result from the Matrix-Tree Theorem by $n$.

  • $\begingroup$ That solution would work but the problem is, you don't know which nodes are adjacent so you can't build the adjacent matrix. $\endgroup$ – MaleCommeX Apr 23 '14 at 14:54
  • $\begingroup$ Do you at least know how many edges there are? $\endgroup$ – ml0105 Apr 23 '14 at 14:55
  • $\begingroup$ it's a tree so number of edges = number of nodes -1 in my case there's 7 nodes so 6 edges. $\endgroup$ – MaleCommeX Apr 23 '14 at 14:56
  • $\begingroup$ I know that. But that doesn't give you a count of the number of spanning trees in $G$. If you are orienting a single spanning tree, there are $n$ such ways to do this. I was asking about the number of edges in $G$. $\endgroup$ – ml0105 Apr 23 '14 at 14:58
  • $\begingroup$ Also, I came across this link on the number of acyclic orientations of a graph: www-math.mit.edu/~rstan/pubs/pubfiles/18.pdf $\endgroup$ – ml0105 Apr 23 '14 at 14:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.