Be more specific about subtrees

1 files changed, 13 insertions, 10 deletions

diff --git a/mgr.tex b/mgr.tex
index 1bfba88..9328809 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -770,14 +770,14 @@ singletons constructed according to the following rules:
     \item If $v \in W$ is a maximal in $W$ with respect to the ancestor
         relation $<$ (i.e. there are no other elements of $W$ in the subtree of
         $v$), then the subtree of $v$ is a part of the partition.
-    \item If $v \in W$ has descendants that are in $W$ only in its left subtree,
-        let $w$ be the highest such descendant (there is a unique highest
-        descendant because $W$ is LCA closed). The subtree of $v$ with hole $w$
-        is a part of the partition.
+    \item If $v \in W$ has descendants that are in $W$ only in its left child's
+        subtree, let $w$ be the highest such descendant (there is a unique
+        highest descendant because $W$ is LCA closed). The subtree of $v$ with
+        hole $w$ is a part of the partition.
     \item Symmetrically if $v \in W$ only has descendants that are in $W$ in its
-        right subtree.
-    \item If $v \in W$ has descendants that are in $W$ in both its subtrees we
-        know that $v$'s left and right child are also elements of $W$ by
+        right child's subtree.
+    \item If $v \in W$ has descendants that are in $W$ in both its children's
+        subtrees we know that $v$'s children are also elements of $W$ by
         property \ref{both-subtrees-property} of being partition ready. Put $v$
         into a singleton part on its own, all the other elements of its subtree
         were assigned to parts when its children were handled.
@@ -796,8 +796,9 @@ Take a set of $m$ tree vertices $W$ and consider the following procedure:
 \begin{enumerate}
     \item Let $W'$ be $W$ with the tree's root added.
     \item\label{partition-ready-lca-step} Let $W''$ be the LCA closure of $W'$.
-    \item\label{partition-ready-last-step} Let $W'''$ be $W''$ plus, for every element of $W''$ that has
-        elements of $W''$ in both its subtrees, the element's both children.
+    \item\label{partition-ready-last-step} Let $W'''$ be $W''$ plus, for every
+        element of $W''$ that has elements of $W''$ in both its children's
+        subtrees, the element's both children.
 \end{enumerate}
 
 \begin{claim}
@@ -819,7 +820,9 @@ of partition readiness won't be satisfied. What we will show is that no other
 new vertices need to be added. Take $v \in W''$ that had descendants in $W''$ in
 both its subtrees, let $v_l$ and $v_r$ be its left and right child,
 respectively. Without loss of generality, suppose $v_l$ was not an element of
-$W''$. Then we claim that it has descendants in $W''$ in only one of its
+$W''$. The only reason we would need to add even more vertices after adding
+$v_l$ would be if $v_l$ had descendants in both its children's subtrees in
+$W'''$. First let's show that it has descendants in $W''$ in at most one of its
 subtrees. Indeed, if it did have descendants from $W''$ in both its subtrees,
 $W''$ wouldn't have been LCA closed -- $v_l$ would have been the LCA of the
 topmost members of $W''$ of its left and right subtrees. Note that newly added