Trees and spans of edge labels Let $T$ be a rooted tree with $m$ leaves. Label every edge with a label of the form $x_i$ or $-x_i$, for some letter $x_i$. For each leaf in the tree, consider the formal linear combination $v$ obtained by summing the labels in the edges from the root to the leaf. What can we say about the dimension of the space $V$ spanned by such $v$?
If all $x_i$'s are distinct, then clearly $\dim V = m$. Say that each $x_i$ appears at most $k$ times. Can one then say that $\dim V \geq m/k - r$, where $r$ is the maximal number of disjoint paths in the tree such that (a) no inner node of any path is an ancestor of any vertex in any other path, (b) in every path, there is a letter appearing at least twice?
 A: The following is a (partial self-)answer both in the positive and in the negative
direction.
Lemma A.
Assume that there are at least $n$ distinct non-zero values of $v$, i.e., $n$
leaves whose corresponding $v$'s are all non-zero and distinct. Then
$\dim V \geq n/k$.
This Lemma follows from Lemma B below; just prune leaves whose $v$ appears
as the $v$ of some other leaf until no such repetitions are left, and orient
all edges of $T$ away from the root, thus making $T$ into a directed graph.
(Actually, let me denote $v$ by $u$ from some on, so that there is no confusion with the use of $v$ to denote a vertex.)
In a directed graph whose edges have labels of the form $\pm x$, we associate
a formal linear combination of letters $u(\phi)$ to a (directed) path $\phi$ in the obvious way: edges traversed against their orientation in a path are counted with their signs flipped.
Lemma B. Let $\Gamma$ be a connected, oriented graph where every edge has a label of the form $x$ or $-x$ for some letter $x$. Assume that every
letter appears in at most $k$ labels. Let $S$ be a set
of $n$ vertices in $\Gamma$. Assume that, for every pair of distinct
elements $v, v'\in S$, any path $\phi$ from
$v$ to $v'$ satisfies $u(\phi)\ne 0$.
Then the space $V$ spanned by all such paths has dimension $\geq (n-1)/k$.
Proof of Lemma B.- Let $v, v'$ be any two distinct elements of $S$. Let $\phi_1$ be a path from $v$ to $v'$. Choose any edge $e$ in $\phi_1$, and say that its label is $x$ or $-x$. Now remove from $\Gamma$ every edge with the label $x$ or $-x$. We obtain a graph with at most $k+1$ connected components (some of them possibly consisting of a single vertex). Choose any connected component containing at least two distinct elements of $S$, and iterate: let $\phi_2$ be a path from one to the other, etc.
After $r$ steps, we have a graph with $\leq r k + 1$ connected components. We stop when there is no connected component containing at least two elements of $S$; that
can happen only if $r k + 1 \geq n$, i.e., only if $k\geq (n-1)/r$. We have paths $\phi_1,\phi_2,\dotsc,\phi_r$ such that, for every $1\leq i\leq r$, there is a letter $x$ appearing in  $u(\phi_i)$ but absent from $u(\phi_{i'})$ for all $i<i'\leq r$. Hence the span
$\langle u(\phi_1),u(\phi_2),\dotsc,u(\phi_r)\rangle$ is $r$-dimensional.
End of Proof of Lemma B.

Now, the problem in applying Lemma A to my original question resides simply in that there may not be many distinct non-zero values of $v$. In fact, it could be that $v$ is the same for all the leaves for a tree with $2^m$ leaves and height
$2 m$, and yet $k=2$. (For instance, for $m=2$, let $T$ be a tree with paths from the root to the leaves given by abcd, abdc, cdab, cdba, with branching in the natural way: the edges containing to the root are labelled a and c, those edges lead to edges b and d, those fork out into c and d and into a and b, respctively, etc.) It may be that $r$ is always large for such examples, but it might not be; perhaps someone wants to construct a counterexample to my original question with low $r$?
