Maximum edge cover by paths defined by 3 vertices in a tree

31 Views Asked by At

Let's consider a tree $T$. $P(u, v)$ represents a path between $u$ and $v$ (set of edges).

My task is to find $a$, $b$ and $c$ such that the set:

$$\left\{ e \in E: e \in P(a, b) \cup P(a,c) \cup P(b,c) \right\}$$

is maximal.

My hypotheses: The set is maximal when the paths created by these vertices represent a tree's diameter and its longest branch (i.e., the longest path that starts at one of the vertices of the diameter and goes "out" of it).

A simple observation is that these vertices are endpoints (a leaf or a root), with the exclusion of one that can lie on the path of the first two if all edges are covered. Otherwise, paths can be extended, so the set is not maximal.

My attempt:

Let's assume that there is a maximal set that does not solely contain the tree's diameter and its longest branch.

Without loss of generality, let us consider the path between $a$ and $b$.

As we consider the maximal set, we choose $c$ as the appropriate vertex.

It can be shown that if $P(a, c)$ or $P(b, c)$ is a diameter or a branch of a diameter (length 0 included), there is a contradiction.

But what if $P(a ,c)$ and $P(b,c)$ are neither a diameter nor a branch of a diameter? I was unable to come to conclusions. I suspect there is a counterexample.