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!

  • 1
    $\begingroup$ Just take $v_i$ to be one end of the path. $\endgroup$ – Brendan McKay Jan 2 at 11:05
  • $\begingroup$ The path have the same ends with $P$. $\endgroup$ – user173856 Jan 2 at 11:23
  • $\begingroup$ Yes, sorry, I missed that aspect. $\endgroup$ – Brendan McKay Jan 2 at 11:32
  • $\begingroup$ @user173856: Is $G$ oriented or not? $\endgroup$ – Alex M. Jan 9 at 21:31
  • 1
    $\begingroup$ @WlodAA: Yes, I have already revised it. $\endgroup$ – 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<m<n+1 \}+\{u_m; 2k<m<n+1 \}]$;

$C_2=G[\{v_m; l<m<2k\}+\{u_m; l<m<2k\}]$; and

$C_3= G[\{v_m; k<m<l\} +\{u_m; k<m<l\}]$.

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<l\}$ 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<i<l\}$ is in a different component of $G \setminus \{v_l,v_k,v_{n+1}\}$ from every vertex $\{v_i: 0<i<k\}$, so $P$ cannot be extended to cover vertices in both $\{v_i: k<i<l\}$ and $\{v_i: 0<i<k\}$. So $P$ cannot be extended from $v_k$ to cover vertices in both the sets $\{v_i: 0<i<k\}$. $\{v_i: k<i<l\}$. 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$.

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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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