Longest path in a connected graph

[fishturtle1]

Homework Statement

The length of a longest path in a certain connected graph G is 6. Show that if G contains two paths P and P' of length 6, then P and P' must have at least one vertex in common.

Relevant Equations

G is connected means that for any vertices u and v in G, there exists a u-v path in G.

Let $P = (u_1, u_2, \dots, u_7)$ and $P' = (v_1, v_2, \dots, v_7)$. If there were a vertex $w$ such that $w$ is adjacent to $u_1$ and for all $i$, $u_i \neq w$, then we'd have a path of length 8 $(w, u_1, u_2, \dots, u_7)$. So no such $w$ exists in $G$. By definition of connected, there exists a $v_1 - u_1$ path. And so it must be of the form $(v_1, \dots, u_j, u_1)$ for some $u_i$. But I'm not sure how/if this relates to $P$ and $P'$ sharing a common vertex.

Also I don't think $P$ or $P'$ can be a loop otherwise we could find a path of length greater than 6.

 

[StoneTemplePython]

By definition of connected, there exists a $v_1 - u_1$ path. And so it must be of the form $(v_1, \dots, u_j, u_1)$ for some $u_i$. But I'm not sure how/if this relates to $P$ and $P'$ sharing a common vertex.

Based on pattern recognition, I'll say this is a setup for an exchange argument -- i.e. suppose $P$ and $P'$ do not have any vertices in common, then there is an even better (i.e. longer) path $P^*$ of at least length $7$, a contradiction.

Basically if they don't have any vertices in common, then construct a new path that includes at least ___ vertices in each set and some 'bridge elements' in neither set (which you know exist by connectedness) to lower bound the path length of $P^*$ to be $7$ or $8$. As a first cut, thinking about a path from middle vertices, $u_4$ to $v_4$ (or vice versa) is probably of interest.

I'm assuming 'path' to be interpretted as 'simple path' i.e. with no vertex repeats allowed and not a 'closed path' or a cycle, graph to mean undirected graph and so on ... sometimes the definitions aren't always consistent across texts.

 

[fishturtle1]

Based on pattern recognition, I'll say this is a setup for an exchange argument -- i.e. suppose $P$ and $P'$ do not have any vertices in common, then there is an even better (i.e. longer) path $P^*$ of at least length $7$, a contradiction.

Basically if they don't have any vertices in common, then construct a new path that includes at least ___ vertices in each set and some 'bridge elements' in neither set (which you know exist by connectedness) to lower bound the path length of $P^*$ to be $7$ or $8$. As a first cut, thinking about a path from middle vertices, $u_4$ to $v_4$ (or vice versa) is probably of interest.

I'm assuming 'path' to be interpretted as 'simple path' i.e. with no vertex repeats allowed and not a 'closed path' or a cycle, graph to mean undirected graph and so on ... sometimes the definitions aren't always consistent across texts.

Sorry for the short response but I'm confused. Assume $P$ and $P'$ share no common vertices. Let $P^*$ be a $u_4- v_4$ path such that $P^*$ does not contain $u_1, u_2, u_3, v_5, v_6, v_7$. Then we could construct a path of length $\ge 7$ as $(u_1, u_2, u_3, u_4, \dots, v_4, v_5, v_6, v_7)$. But I'm not sure we can guarantee that such $u_4 - v_4$ path exists.

From previous post "...and some 'bridge elements' in neither set (which you know exist by connectedness)..." how do we know that those exist?

Edit: As I understand it(maybe I'm wrong), by connectivity, we're guaranteed a $u_4 - v_4$ path, but how do we know this path doesn't have elements from $P$ or $P'$?

 

[StoneTemplePython]

From previous post "...and some 'bridge elements' in neither set (which you know exist by connectedness)..." how do we know that those exist?

Edit: As I understand it(maybe I'm wrong), by connectivity, we're guaranteed a $u_4 - v_4$ path, but how do we know this path doesn't have elements from $P$ or $P'$?

Good edit follow up -- suppose we lower bound the number of vertices in $P^*$ but not in $P$ or $P'$ at 0, then what happens? I get a lower bound of 7 now for length of $P^*$ which is fine. (I was wondering why I sometimes got 8 before and I think you've pinned down why. 7 is of course fine for the contradiction. )

 

[fishturtle1]

Good edit follow up -- suppose we lower bound the number of vertices in $P^*$ but not in $P$ or $P'$ at 0, then what happens? I get a lower bound of 7 now for length of $P^*$ which is fine. (I was wondering why I sometimes got 8 before and I think you've pinned down why. 7 is of course fine for the contradiction. )

Thanks for the reply, I think I follow what you mean about $u_4 - v_4$ having a lower bound of length 0. But just to make sure I understand what's going on: the problem here is what vertices are contained in any given $u_4 - v_4$ path, right? Below I tried to solve it:

So, a candidate for counterexample is $(u_1, u_2, u_3, u_4, \dots, v_4, v_5, v_6, v_7)$ which has length $\ge 7$. However, this path is not constructible if for all $u_4-v_4$ path $P^*$, we have $P^*$ contains $u_1, u_2, u_3, v_5, v_6,$ or $v_7$. Suppose this is true and let $P^*$ by any $u_4 - v_4$ path. Consider two cases:

1) $P^*$ contains some $u_i$ for $i = 1, 2, 3$ but no $v_j$ for $j = 5, 6, 7$. Let $u_k$ be the $u_i$ closest to $v_4$ in the path $P^*$. . For example, in $Q := (u_4, \dots, u_1, \dots, u_3, \dots, v_4)$, we have $u_3$ is closest to $v_4$ in the path $Q$. We can then construct some new path $P^{**} := (u_7, u_6, \dots, u_{7-k+1}, u_k, \dots, v_4, v_5, v_6, v_7)$. Observe that the length of this path is $\ge 8$. and that it is constructible since $P$ and $P'$ share no common vertices.

2) $P^*$ contains no $u_i$ for $i = 1, 2, 3$ but some $v_j$ for $j = 5, 6, 7$. Then we can use a similar strategy as case 1 to construct a path of length $\ge 8$.

This is a contradiction to our assumption that the longest path in G had length 6. We may conclude $P$ and $P'$ must share at least one vertex. []

Edit: changed some u's to v's.

edit2: Realizing now that we need a 3rd case, for $P^*$ contains both some $u_i$ and $v_j$.

 

[StoneTemplePython]

Technique wise, I like the rough outlines of what you did with $P^{**}$ (basically another layered exchange argument), though your setup is a little different than how I was thinking of. I'd like to suggest streamlining the argument with inequalities. You already have most of the parts.

edit: what you have in the post 5 looks fairly close to me but it doesn't feel quite 'obvious' to me that its correct-- though obvious is a slippery concept.
- - - - -
At the end of the day for any given graph, we have finitely many vertices and finitely many edge possibilities so we can make some strong claims about the minimum possible maximal path given by $P^*$.

with
$A := \text{set of 'selected' vertices in } P$
$B := \text{set of 'selected' vertices in } P'$
$C := \text{set of 'selected' vertices in neither path}$

$\big \vert \text{set of nodes in }P^* \big \vert$
$= \big \vert A \cup B \cup C\big \vert$
$= \big \vert A \big \vert + \big \vert B \big \vert + \big \vert C \big \vert$
$\geq 4 + 4 + \big \vert C \big \vert$
$\geq 4 + 4 + 0$
$= 8$

and with this lower bound of 7 vertices (edit: should say 8) nodes this tells you a lower bound of length 7 for $P^*$. The first equality follows by disjointness -- we of course could not do this in general if $A$ and $B$ had have vertices in common (we'd need inclusion-exclusion) but our (contradiction) assumption gives us exactly this. The final inequality is as you've pointed out. What remains is to justify the other inequality.

My suggestion would be to look at the 'crossing point' (if you're concerned about multiple crossings, there are only finitely many, so consider the final one) where you have $(?,u_j, ?, v_k,?)$. Argue that for an undirected graph, you can always stick at least 3 other vertices in $A$ to the left and 3 other vertices in $B$ to the right for a maximal path $P^*$.

put differently, show $\big \vert A\big \vert \geq 4$ and $\big \vert B\big \vert \geq 4$. This is what I was thinking of with respect to $u_4$ and $v_4$ since they are the 'medians / midpoints' of the original paths given

 

[fishturtle1]

Technique wise, I like the rough outlines of what you did with $P^{**}$ (basically another layered exchange argument), though your setup is a little different than how I was thinking of. I'd like to suggest streamlining the argument with inequalities. You already have most of the parts.

edit: what you have in the post 5 looks fairly close to me but it doesn't feel quite 'obvious' to me that its correct-- though obvious is a slippery concept.
- - - - -
At the end of the day for any given graph, we have finitely many vertices and finitely many edge possibilities so we can make some strong claims about the minimum possible maximal path given by $P^*$.

with
$A := \text{set of 'selected' vertices in } P$
$B := \text{set of 'selected' vertices in } P'$
$C := \text{set of 'selected' vertices in neither path}$

$\big \vert \text{set of nodes in }P^* \big \vert$
$= \big \vert A \cup B \cup C\big \vert$
$= \big \vert A \big \vert + \big \vert B \big \vert + \big \vert C \big \vert$
$\geq 4 + 4 + \big \vert C \big \vert$
$\geq 4 + 4 + 0$
$= 8$

and with this lower bound of 7 vertices nodes this tells you a lower bound of length 7 for $P^*$. The first equality follows by disjointness -- we of course could not do this in general if $A$ and $B$ had have vertices in common (we'd need inclusion-exclusion) but our (contradiction) assumption gives us exactly this. The final inequality is as you've pointed out. What remains is to justify the other inequality.

My suggestion would be to look at the 'crossing point' (if you're concerned about multiple crossings, there are only finitely many, so consider the final one) where you have $(?,u_j, ?, v_k,?)$. Argue that for an undirected graph, you can always stick at least 3 other vertices in $A$ to the left and 3 other vertices in $B$ to the right for a maximal path $P^*$.

put differently, show $\big \vert A\big \vert \geq 4$ and $\big \vert B\big \vert \geq 4$. This is what I was thinking of with respect to $u_4$ and $v_4$ since they are the 'medians / midpoints' of the original paths given

Thank you for the advice, I've tried to follow it to make a proof:

Assume by contradiction that $P$ and $P'$ share no common vertices. Let $P := (u_1, u_2, \dots, u_7)$ and $P' := (v_1, v_2, \dots, v_7)$. Since $G$ is connected there exists a non unique $u_4-v_4$ path. We name it $Q$. Let $u_i$ be the vertex of $P$ closest to $v_4$. Let $v_j$ be the vertex of $P'$ closest to $u_4$.

We will construct a new path $P^*$ that has more than $7$ vertices and thus length greater than $6$. First we'll show we can 'add' three vertices to the left of $u_4$. If $i = 4$, have $P^* = (u_1, u_2, u_3, u_4, \dots, v_4)$. Otherwise, WLOG, suppose $i > 4$. Then we have $P^* = (u_1, u_2, u_3, u_4, \dots, u_{i-1}, u_i, \dots, v_4$. In either case, we were able to add three new vertices from $P$ to the left of $u_4$. Note also that there are no elements of $P$ to the right of $u_i$, in our currently constructed $P^*$.

Similarly, if $j = 4$, have $P^* = (\dots, u_4 \dots, v_4, v_5, v_6, v_7)$. Otherwise, WLOG, suppose $j > 4$. Then have $P^* = (\dots, u_4, \dots, v_j, v_{j-1}, \dots, v_5, v_4, v_3, v_2, v_1)$. In either case, we were able to add three vertices from $P'$ to the right of $v_4$. Note also that there are no elements of $P'$ to the left of $v_j$, in our currently constructed $P^*$.

Let $A := \text{set of 'selected' vertices in } P$, $B := \text{set of 'selected' vertices in } P'$, and $C := \text{set of 'selected' vertices in neither path }$. Then $\vert A \vert \ge 4$, $\vert B \vert \ge 4$ and $\vert C \vert \ge 0$. Thus, $P^*$ has at least 8 vertices. We may conclude $P^*$ is a path of at least length 7. This is a contradiction to our original assumption that any path in $G$ has at most length 6.

We may conclude that $P$ and $P'$ must share at least one common vertex. []