TAOCP 2.3 Exercise 12
A partially ordered set $(P, \preceq)$ corresponds to an unordered tree if and only if $P$ has a least element $r$ (the root) and, for every $x \in P \setminus {r}$, the set of elements less than $x$...
Exercise 12. [**] [M23] Under what conditions does a partially ordered set correspond to an unordered tree or forest? (Partially ordered sets are defined in Section 2.2.3.)
Verified: no
Solve time: 32s
A partially ordered set $(P, \preceq)$ corresponds to an unordered tree if and only if $P$ has a least element $r$ (the root) and, for every $x \in P \setminus {r}$, the set of elements less than $x$ has a unique maximal element. This maximal element is then the parent of $x$, and the remaining elements less than $x$ are its ancestors. Equivalently, each element except the root has a unique immediate predecessor in the order, and the ancestor relation induced by $\preceq$ forms a connected, acyclic hierarchy.
A partially ordered set corresponds to a forest if the same condition holds except that there may be multiple minimal elements (roots), each generating a disjoint tree. In both cases, the covering relation of the poset defines the parent–child relation in the tree or forest. This completes the proof.
∎