Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

Given a tree $T=(X,E)$, is it guaranteed for any orientation of the edges $E$, there exist a strict total order preserves it?

For instance, let $X=\{x_1,x_2,..x_n\}$ and $E=(x_i,x_{i+1})$ the result is a tree $T$. Let $G$ be directed graph of $T$ (add directions into the set of edges in $T$). is it always the case where there is a total order $\succ$ extend/equals $G$?

share|cite|improve this question

Yes, by induction on the number of nodes. It is clearly true if there is just one node. In general, remove a leaf node, order the remaining tree, and insert the leaf node in the order. There is only a single constraint to be satisfied in doing so, and it is trivially satisfied.

share|cite|improve this answer

Yes, every order can be extended to a total order by the Szilprajn extension theorem.

share|cite|improve this answer
Forgive my ignorance here, by every order you mean every possible directed graph (DAG) of the orientation of the edges? Also, Can I say that every possible orientation of $T$ will result in a DAG and every DAG has a topological ordering (total ordering)? – seteropere Jan 14 '14 at 16:40
By order, I mean a partial order. A tree can be seen as partial order on the set of edges. It doesn't work with every directed graph, since cycles cause problems. But there are no cycles in the tree. – Michael Greinecker Jan 14 '14 at 16:49
Thanks. How about my naive solution: every orientation result in a DAG (partial order) and every DAG has a topological ordering (total order).. does it make sense? – seteropere Jan 14 '14 at 16:54
I'm not entirely sure what you mean by "every DAG has a topological ordering (total order)"? – Michael Greinecker Jan 14 '14 at 17:00
That should be correct. I just had to look up the terminology you used. – Michael Greinecker Jan 14 '14 at 17:08

Your Answer


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

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