# Tag Info

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