# To find a longer path with fixed endvertices in a graph satisfies the following property

Suppose that $$G=(V,E)$$ is a simple graph and $$P=(V_1,E_1)$$ is a path in $$G$$ where $$V_1=\{v_0,v_1,\cdots,v_n\},\ E_1=\{v_0v_1,v_1v_2,\cdots,v_{n-1}v_n\}.$$ I found that if the path $$P$$ satisfies:

For any $$v_i\in V_1$$, there exist $$v_j\in V_1\setminus \{v_i\}$$ and $$u\in V\setminus V_1$$ such that $$uv_i,uv_j\in E$$.

Then you can always find a longer $$v_0$$-$$v_n$$ path in $$G$$.

I have tried to find a counterexample to this for a long time but still cannot find one. So I think maybe the above conjecture is true. Is it true or is there any known result about this? Any ideas are welcome!

• Just take $v_i$ to be one end of the path. – Brendan McKay Jan 2 at 11:05
• The path have the same ends with $P$. – user173856 Jan 2 at 11:23
• Yes, sorry, I missed that aspect. – Brendan McKay Jan 2 at 11:32
• @user173856: Is $G$ oriented or not? – Alex M. Jan 9 at 21:31
• @WlodAA: Yes, I have already revised it. – user173856 yesterday

Disclaimer: this is not a proof but rather some ideas which may or may not help.

If we identify the pairs $$v_i, v_j$$ such that there's $$u$$ with $$v_iuv_j \in E$$ with a segment $$[i, j]$$, we are going to have at least $$\frac{n+1}{2}$$ segments.

Now we can argue similarly to the Vitali covering lemma. We have a collection of segments, covering $$1, \ldots, n$$ (let's assume we count starting from $$1$$ rather then from $$0$$). We can find two families of segments $$\{ I \}$$ and $$\{ J \}$$ such that

1. Segments in each family are either disjoint or nested
2. There are disjoint subfamilies $$\tilde I$$ and $$\tilde J$$ such that each segment intersect at most two neighbouring.

Now at least one of the families has measure at least $$\frac{n+1}{2}$$. Assume wlog that $$| \cup I_j | \geq | \cup J_j |$$

If we order the segments in $$\tilde I$$ and $$\tilde J$$ so that $$J_k$$ intersects exactly two neighbours say $$I_{l-1}$$ and $$I_{l}$$ and $$|J_k \cap I_{l-1}| + |J_k \cap I_{l}| = |J_k|$$, then it would suffice to walk trough the nested segments in $$I_{l-1}$$, then "jump" using $$J_k$$ to $$I_l$$ and walk through the nested family in $$I_l$$.

The scheme above assumes that all $$u$$'s are distinct.

The graph $$G$$ below is a counterexample.

Construct $$G$$ as follows:

1. Letting $$n$$ be quite large, $$V_1 = \{v_0,v_1,\ldots, v_{n+1}\}$$ and $$E_1= \{v_iv_{i+1}; i=0,\ldots, n\}$$ as stated in the problem.

2. Let $$k$$ be an integer about $$\frac{n}{3}$$ and let $$l=\frac{n}{2}$$. So $$2k=\frac{2n}{3}$$ and $$2k-l=\frac{n}{6}$$.

3. Then $$V \setminus V_1$$ $$=\{u_0,\ldots, u_{l-1},u_{l+1},\ldots, u_{2k-1},u_{2k+1} \ldots, u_{n}\}$$. $$= \{u_j; \ j \in \{0,\ldots, n\}\setminus \{l,2k\} \}$$

4. Then the edges in $$G \setminus E_1$$ are:

(a) $$v_0u_0$$ and $$u_0v_{l}$$; $$v_ku_k$$ and $$u_kv_{2k}$$;

(b) $$v_iu_i$$ and $$u_iv_{n+1}$$ for $$i=1,2,\ldots, l-1$$;

(c) $$v_mu_m$$ and $$u_mv_l$$ for $$m=n, n-1,n-2, \ldots, 2k+1,2k-1,\ldots, l+2$$;

(d) $$v_{2k}u_{l+1}$$ and $$u_{l+1}v_{l+1}$$.

Here is a sketch of the proof that there is no path $$P$$ in $$G$$ starting at $$v_0$$ and ending at $$v_{n+1}$$ that is longer than $$E_1$$.

Claim 1: (i) Any path $$P$$ in $$G$$ not starting nor ending at any vertex in $$V \setminus V_1$$ can take only $$O(1)$$ of the vertices in $$V \setminus V_1$$. (ii) Any path $$P$$ of length at least $$n-2$$ from $$v_0$$ to $$v_{n+1}$$ must cover almost all of $$V_1$$ i.e., at most $$O(1)$$ vertices in $$V_1$$ are not in $$P$$.

To see (i) of Claim 1, note that every $$u_j$$ has degree 2 and so if a path $$P$$ contains $$u_j$$ and doesn't end at $$u_j$$ then $$P$$ must contain both edges incident to $$u_j$$. But every $$u_j$$ is adjacent to at least one of $$v_l, v_k,v_{2k}$$, or $$v_{n+1}$$.

So in light of (i) of Claim 1, if there is a path $$P$$ from $$v_0$$ to $$v_{n+1}$$ of length $$\ell$$ then $$P$$ must contain $$\ell-O(1)$$ vertices in $$V_1$$. If $$\ell \ge n-O(1)$$ then almost all of $$V_1$$ must be in $$P$$.

Claim 2: The longest path in $$G' \doteq G \setminus \{v_k,v_{2k},v_{n+1}\}$$ has length no larger than $$\max\{n-2k + (2k-l), n-2k + (l-k)\}$$ $$=\max\{\frac{n}{3}+\frac{n}{6}, \frac{n}{3}+\frac{n}{6}\} = \frac{n}{2}$$.

Indeed, the components of $$G \setminus \{v_k,v_{2k},v_l,v_{n+1}\}$$ [i.e., take the graph with the vertex $$v_l$$ removed from $$G'$$] are

$$C_1= G[\{v_m; 2k;

$$C_2=G[\{v_m; l; and

$$C_3= G[\{v_m; k.

One of these components $$C_1$$ has no path of length greater than $$n-2k=\frac{n}{3}$$; $$C_2$$ has no path of length greater than $$2k-l=\frac{n}{6}$$ and $$C_3$$ has no path of length greater than $$l-k=\frac{n}{6}$$. So this means that the length of the longest path in $$G'$$ is no more than the length of the longest path in $$C_p$$ plus the length of the longest path in $$C_{p'}$$ for some distinct $$p, p' \in \{1,2,3\}$$ where $$C_1,C_2,C_3$$ are as above. From this Claim 2 follows.

Remainder Of The Proof: So let $$P$$ be a path from $$v_0$$ to $$v_{n+1}$$, and let $$e$$ be the first edge in $$P$$ that is not in $$E_1$$. [Order the edges in $$P$$ from the starting point $$v_0$$ of $$P$$ to the finishing point $$v_{n+1}$$ of $$P$$.]

Case 1: $$e=v_ku_k$$. Then $$e$$ is the $$k+1$$-th edge in $$P$$, and the first $$k$$ edges of $$P$$ form the path $$v_0v_1\ldots v_k$$, and the $$(k+2)$$nd edge in $$P$$ is $$u_kv_{2k}$$. Thus as both $$v_k$$ and $$v_{2k}$$ are vertices that are in the first $$k+2$$ edges of $$P$$, the length of $$P$$ can be no more than $$k+2$$ plus the length of the longest path in $$G' = G \setminus \{v_k,v_{2k},v_{n+1}\}$$ plus 1. Thus from Claim 2 $$P$$ can be no longer than $$k+2+\frac{n}{2}+1=\frac{5n}{6}+3 < n$$.

Case 2: $$e=v_{l+1}u_{l+1}$$. Then $$e$$ is the $$(l+2)$$nd edge in $$P$$ and the first $$l+1$$ edges of $$P$$ form the path $$v_0v_1\ldots v_lv_{l+1}$$, and the $$(l+3)$$rd edge in $$P$$ is $$u_{l+1}v_{2k}$$. So $$v_{2k},v_l$$ and $$v_{l+1}$$ are vertices that appear in the first $$l+3$$ edges of $$P$$. However, note that $$G \setminus \{v_{2k},v_{l+1},v_{l}\}$$ has more than one connected component, and furthermore, every vertex in the set $$V_{11}=\{v_{2k-1},v_{2k-2},\ldots, v_{l+2}\}$$ in a different component from every vertex in the set $$V_{12}=\{v_{2k+1},\ldots, v_{n}\}$$. So the remaining edges of $$P$$ will miss at least either every vertex in $$V_{11}$$ or every vertex in $$V_{12}$$. Furthermore, neither $$V_{11}$$ nor $$V_{12}$$ intersects the first $$l+3$$ edges of $$P$$, so either $$P \cap V_{11}$$ or $$P \cap V_{12}$$ must be empty. As each of $$V_{11}$$ and $$V_{12}$$ have at least $$\frac{n}{6}$$ vertices, so this and Claim 1 implies that $$P$$ will not have length $$n$$.

Case 3: $$e=v_lu_m$$ for some $$m < 2k$$. Then $$e$$ is the $$(l+1)$$st edge in $$P$$ and the first $$l+1$$ edges of $$P$$ form the path $$v_0v_1\ldots v_lu_m$$ and the $$(l+2)$$nd edge in $$P$$ is $$u_mv_{m}$$. However, note that the only way $$P$$ can be extended to reach $$v_{n+1}$$ is if the rest of $$P$$ is $$v_mv_{m+1}\ldots v_{n+1}$$. [Indeed, note that $$v_k$$ and $$v_{l}$$, and $$v_m$$ are in the first $$l+2$$ edges in $$P$$, and so the remaining edges of $$P$$ are all (a) in a single component of $$G \setminus \{v_k,v_l,v_m\}$$ that has a vertex $$v'$$ adjacent to $$v_m$$ that isn't in the first $$l+2$$ edges of $$P$$, and (b) form a path starting at $$v'$$ and ending at $$v_{n+1}$$. The only such vertex $$v'$$ is $$v_{m+1}$$, and furthermore, one can see that the component of $$G \setminus \{v_k,v_l,v_m\}$$ containing $$v_{m+1}$$ is a tree, and so the path $$v_{m+1} \ldots v_{n+1}$$ is the only path from $$v'=v_m$$ to $$v_{n+1}$$ and so these must be the remaining edges of $$P$$.] As $$m > l+2$$ this implies that $$P$$ will not have length longer than that of $$v_0v_1\ldots v_{n+1}$$.

Case 4: $$e=v_lu_m$$ for some $$m > 2k$$. Can be finished in a similar fashion as Case 3.

Case 5: $$e=v_0u_0$$ which is the first edge in $$P$$. Then $$v_0u_0$$ is the first edge in $$P$$, and the 2nd edge in $$P$$ is $$u_0v_l$$. We divide into two subcases.

The first subcase of Case 5 is that the next vertex in $$P \cap V_1$$ after $$v_l$$ is in the set $$\{v_m: m > l\}$$. Then, by Claim 1 it follows that $$P$$ must contain almost every vertex in $$\{v_i: i as well, and so as every path in $$G \setminus \{v_{n+1}\}$$ from $$\{v_m: m > l\}$$ and $$\{v_i: i< l\}$$ must pass through $$\{v_l,v_{2k}\}$$, it follows that $$P$$ must enter back into $$\{v_i: i< l\}$$ via the edges $$v_{2k}u_kv_k$$, and then $$P$$ must cover almost every vertex in $$\{v_i: i< l\}$$. But this is impossible as every vertex in $$\{v_i: k is in a different component of $$G \setminus \{v_l,v_k,v_{n+1}\}$$ from every vertex $$\{v_i: 0, so $$P$$ cannot be extended to cover vertices in both $$\{v_i: k and $$\{v_i: 0. So $$P$$ cannot be extended from $$v_k$$ to cover vertices in both the sets $$\{v_i: 0. $$\{v_i: k. Each of these sets has $$\frac{n}{6}$$ vertices. So by Claim 1 $$P$$ cannot have length $$n$$.

The 2nd subcase of Case 5 is that the next vertex in $$P \cap V_1$$ is in the set $$\{v_i: i< l\}$$. One can finish using the same line of reasoning as in the above subcase.

*Case 6: $$e=v_iu_i$$; $$i=1,\ldots, l-1$$; $$i \not = k$$. Then $$e$$ is the $$i+1$$-th edge in $$P$$, and the $$i+2$$th edge in $$P$$ is $$u_iv_{n+1}$$, which implies that $$P$$ has length $$i+2 \le l+1 < n$$.

• I see $v_{l+2}$ adjacent to $u_{l+2}$ in (c), but there is no $u_{l+2}$. – Brendan McKay yesterday
• Sorry was a typo on my part I editted that – Mike yesterday
• @BrendanMcKay made some more edits – Mike 20 hours ago