14
$\begingroup$

If a graph $G$ is connected and has no path with a length greater than $k$, prove that every two paths in $G$ of length $k$ have at least one vertex in common.

I think that that common vertex should be in the middle of both the paths. Because if this is not the case then we can have a path of length $>k$. Am I right?

$\endgroup$
  • 2
    $\begingroup$ Counterexample for a directed graph that is not strongly connected: vertices $A,B,C,D$, edges $A \to C$,$A \to D$,$B \to D$, the paths $A \to C$ and $B \to D$ have no common vertex. $\endgroup$ – sdcvvc Jul 4 '12 at 21:09
  • $\begingroup$ @sdcvvc, you could provide it as answer. $\endgroup$ – user742 Jul 4 '12 at 21:24
  • 2
    $\begingroup$ @sdcvvc I guess the question is restricted to undirected graphs. $\endgroup$ – Raphael Jul 5 '12 at 8:20
  • $\begingroup$ Can you confirm (or infirm) that $G$ is an undirected graph and you are only considering simple (= cycle-free) paths? $\endgroup$ – Gilles Jul 5 '12 at 23:03
  • $\begingroup$ @Gilles Yes the graph is undirected and path is walk in which contain distinct edges and vertices. $\endgroup$ – Saurabh Jul 6 '12 at 4:40
20
$\begingroup$

EDIT Updated slightly to make explicit that $P'$ may only be of length one.

Assume for contradiction that $P_{1} = \langle v_{0},\ldots,v_{k}\rangle$ and $P_{2} = \langle u_{0},\ldots,u_{k}\rangle$ are two paths in $G$ of length $k$ with no shared vertices.

As $G$ is connected, there is a path $P'$ connecting $v_{i}$ to $u_{j}$ for some $i,j \in [1,k]$ such that $P'$ shares no vertices with $P_{1} \cup P_{2}$ other than $v_{i}$ and $u_{j}$. Say $P' = \langle v_{i},x_{0},\ldots,x_{b},u_{j}\rangle$ (note that there may be no $x_{i}$ vertices, i.e., $b$ may be $0$ - the notation is a bit deficient though).

Without loss of generality we may assume that $i,j \geq \lceil\frac{k}{2}\rceil$ (we can always reverse the numbering). Then we can construct a new path $P^{*} = \langle v_{0},\ldots,v_{i},x_{1},\ldots,x_{b},u_{j},\ldots,u_{1}\rangle$ (by going along $P_{1}$ to $v_{i}$, then across the bridge formed by $P'$ to $u_{j}$, then along $P_{2}$ to $u_{0}$).

Obviously $P^{*}$ has length at least $k+1$, but this contradicts the assumption that $G$ has no paths of length greater than $k$.

So then any two paths of length $k$ must intersect at at least one vertex and your observation that it must be in the middle (if there's only one) follows as you reasoned.

$\endgroup$
  • $\begingroup$ I think you need $j \leq \lfloor\frac{k}{2}\rfloor$, otherwise the new path is not necessarily longer. Note that $b=0$ is possible. $\endgroup$ – Raphael Jul 5 '12 at 8:27
  • 1
    $\begingroup$ @Raphael Yes, I didn't explicitly state it (and used slightly misleading notation), but $b$ can quite happily be $0$, the bridge always adds at least one edge though, even if the only vertices in $P'$ are $v_{i}$ and $u_{j}$. On the first point, note that I've constructed the path from $v_{0} \rightarrow v_{i} \rightarrow u_{j}\rightarrow \mathbf{u_{0}}$, so $j \geq \lceil\frac{k}{2}\rceil$ is right. If it went to $u_{k}$ then $j \leq \lfloor\frac{k}{2}\rfloor$ would be the right condition. $\endgroup$ – Luke Mathieson Jul 5 '12 at 10:54
1
$\begingroup$

You are right that the common vertex must occur in the middle of both paths.

However that intuition will not solve the actual problem you're trying to solve.

Instead try to demonstrate that, given any point in the path, the path segment from (and including) that point to one of the ends of the original path must have strictly greater than half as many nodes as the full path.

Once you have shown that, you will be able to both solve the problem that you were asked and verify your conjecture.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.