# How to go from Tree to Total orders

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$?

-

## 2 Answers

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.

-

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

-
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