¿Cómo ir de Árbol a Pedidos Totales?

Question

Dado un árbol $T=(X,E)$, ¿se garantiza que para cualquier orientación de las aristas $E$, existe un orden total estricto que lo preserve?

Por ejemplo, sea $X=\{x_1,x_2,..x_n\}$ y $E=(x_i,x_{i+1})$ el resultado es un árbol $T$. Sea $G$ el grafo dirigido de $T$ (agrega direcciones al conjunto de aristas en $T$). ¿Siempre es el caso de que existe un orden total $\succ$ que extienda/se iguale a $G$?

Answer 1

Sí, por inducción en el número de nodos. Es claramente cierto si hay solo un nodo. En general, elimina un nodo hoja, ordena el árbol restante e inserta el nodo hoja en el orden. Solo hay una restricción que se debe cumplir al hacerlo, y se cumple trivialmente.

Answer 2

Sí, cada pedido se puede extender a un pedido total por el teorema de extensión de Szpilrajn.