What is the maximal path of a tree?

Question

Could anyone explain obviously what the maximal path is ? Is it necessary for a tree that has two maximal paths that share no common vertex ?

Answer 1

It depends what you mean by maximal. Usually maximal is different from maximum in the following sense: a maximal path can mean a path that cannot be made any longer; in other words, at each end there is a vertex all of whose neighbours are already on the path.

Note that under this definition, a maximal path is not necessarily a path of maximum length. Here is one such example ($A-B-C$):

  A
  |
o—B—o—o—o—o—o
  |
  C

Answer 2

I will assume that you meant a connected tree. Also, I am using maximal to mean "of maximal length," which may not be what you meant.

A path in a tree is a sequence of vertices, with no repeats, where successive vertices in the sequence are adjacent. If a path $P$ is at least as long as any other path, then that path is maximal. It is possible for there to be more than one maximal path. For example, in this tree,

     C
    /
A--B
    \
     D

both of the paths $A,B,C$ and $A,B,D$ are maximal, since they are of length $3$, and there are no paths of length $4$ or greater.

Note that these two paths share a common vertex. This is always true: any two maximal paths will share a common vertex.

Why? Suppose you had two disjoint paths, $P_1=v_1,v_2\dots,v_n$ and $P_2=w_1,w_2\dots, w_n$. Consider the pair $v_i,w_j$ for which the distance between $v_i$ and $w_j$ is minimal (here, distance means the length of the shortest path connecting them). Then there is a path $v_i,p_1,p_2,\dots,p_k,w_j$ which connects $v_i$ and $w_j$. None of the intermediate vertices $p_1,\dots,p_k$ can be in $P_1$ or the $P_2$, because of the minimality when we chose $v_i$ and $w_j$. This implies that $P_1$ and $P_2$ weren't maximal, since at least one of the following paths are longer: $$ v_1,\dots,v_i,p_1,\dots,p_kw_j,\dots,w_n $$ $$ w_1,\dots,w_j,p_k,\dots,p_1,v_i,\dots,v_n $$ We have shown that disjoint paths are not maximal, which means that any two maximal paths intersect.

Answer 3

I think it is possible for that a tree that has two maximal paths that share no common vertex .

      o
      |
      o
      |
o     o         o
 \    |        /
  o - o - o - o
 /        |    \
o         o     o
          |
          o
          |
          o

As shown above, the graph of a tree has two maximal paths that share no common vertex. The length of the maximal paths is 5.