If $G$ is a tree with $k$ leaves, then $G$ is the union of $k/2$ pairwise intersecting paths.

Question

Suppose $G$ is a tree with $k$ leaves. Prove that $G$ is the union of paths $P_1, \ldots, P_{\lceil k/2 \rceil}$ s.t. $P_i \cap P_j \ne \emptyset\ \forall i \neq j$ (Ando-Kaneko-Gervacio [1996]).

The proof in the original paper is very dry. I came up with the following solution but I am not sure if it is complete. Am I missing something here?

(Prove by construction ) idea : Step 1 Get $k$ paths s.t union of those paths will be G. Step 2 Merge Paths to get the needed result $\lceil k/2 \rceil$

1. Pick any vertex that is not a leaf ( w.l.g. call it $v$) in $G$ run BFS remembering a paths to the leafs.
2. Each path has a common starting vertex v. Taking advantage of it. Merge in pair wise manner all paths. if $k$ is even you, after merging we get $k/2$ paths , if $k$ is odd we get $\lceil k/2 \rceil$ paths.

Answer 1

You can run into trouble when you merge paths. Suppose the leaves are $w_1, w_2, \dots, w_k$, so you start with $k$ paths: $(v, \dots, w_i)$ for $i = 1,2, \dots, k$. Merging these paths can be problematic for two reasons:

1. It may be the case that if we try to merge $(v, \dots, w_1)$ and $(v, \dots, w_2)$ into one path that goes $(w_1, \dots, v, \dots, w_2)$, we don't actually get a simple path as a result. This happens whenever we merge two paths that take the same edge out of $v$, and is sometimes guaranteed to happen no matter how we pair up the paths to merge. (For example, if the same edge out of $v$ leads to more than half the leaves.)
2. We can fix this by "simplifying" the paths after we merge them, deleting redundant edges. But then you can't be sure that the paths remain pairwise intersecting: originally, your only guarantee of that was that they all pass through $v$, and after simplifying, the paths might no longer pass through $v$.

---

It might help you understand the original proof better to realize that if the leaves of a tree $T$ are $w_1, w_2, \dots, w_k$, we can specify a collection of $\left\lceil \frac k2\right\rceil$ paths that cover $T$ by pairing up the leaves and connecting each pair by a path. (If $k$ is odd, one leaf gets used twice.) There is no further freedom in choosing the paths, and each leaf must be the endpoint of a path or else it remains uncovered.

So all that remains is to choose how to pair the leaves. And the claim that drives the proof is this: if the paths $(w_1, \dots, w_2)$ and $(w_3, \dots, w_4)$ are disjoint, then the paths $(w_1, \dots, w_3)$ and $(w_2, \dots, w_4)$ are not disjoint and have a greater total length.