1
I'd like to propose a variation on Aleksandr Logunov's proof, that I find to be a bit simpler (arguable).
Let's prove that we can make a tree from a collection of disjoint trees.
So suppose we have a collection of at least two disjoint trees in the plane (if there were only one we would be done).
Without loss of generality, suppose that no two vertices ...
1
Disclaimer: the proof is quite technical. OTOH, I don't see a comfortable way to do this, because the initial set of segments can be as crazy as possible, even if none of them intersects.
Let's prove that we can make a tree not only from the set of disjoint segments, but also from the set of disjoint trees. So, the initial statement will be just a special ...
1
Let $T$ be a tree on $n$ vertices. Root $T$ in an arbitrary vertex $r$ and let $p(v)$ denote the parent of vertex $v \neq r$ in $T$. For $v \in V$, let $C(v)$ denote the children of $v$ in $T$.
A path $\langle v_1, v_2, v_3, v_4 \rangle$ of length $3$ in $T$ is of exactly one of the following two forms (when the path's traversal direction is ignored):
Type ...
Only top voted, non community-wiki answers of a minimum length are eligible
