Let G = (V, E) be a tree, and let M be the greatest possible number of vertices in a path that is a subgraph of G. Show that any two paths with M vertices in G must have at least one vertex in common.
We will prove this by the method of contradiction. Let us assume that there are two paths with M vertices and and no two vertices in and are common, that is, for any i and j in [1,M].
SInce G is a tree, it is connected, there is a path between and for some i and j in [1,M] and shares no vertex with apart from and . Let us assume that . Here, n can be zero too.
Let us assume that i and j are both greater than or equal to M/2. We can assume this, because if it is not true we can reverse the ordering of the path. Then we can have a path . This moves from to along , then, then moves from to along and finally from to along .
is found to have vertices more than . However, this contradicts the fact given about . Hence, and must have at least one common vertex.
Get Answers For Free
Most questions answered within 1 hours.