In a tree, is there always a sink where every longest path ends in?

538 Views Asked by At

Let $T$ be an undirected tree. Can we always find a leaf vertex $s$ such that every longest path of $T$ has its other endpoint in $s$? It's easy to see that every longest path passes through the center of $T$. However, it is of course not true that there is a longest path between any two arbitary leaves.

Here's an example, where every longest path ends in $6$.

example

Maybe this could be shown by contradiction. So one could suppose there is no such "sink" leaf $s$. Then there is longest path starting at $v$, not ending in $s$. Can this be extended to a proof? Is there a simpler argument?

2

There are 2 best solutions below

0
On

What if you removed 6 from your graph? Can you find two longest paths that have no common endpoint?

2
On

It seems you're asking does every longest path have leaf nodes as endpoints? The answer is yes.

If not, an endpoint $x$ of a longest path $P$ has two neighbours $u$ and $v$. If $u$ is not in the path $P$, then we can add $u$ to $P$ to make a longer path (and similarly for $v$). Thus $u$ and $v$ both belong to $P$. But this gives a cycle, contradicting that the graph is a tree.

This is illustrated below:

enter image description here