The 'subways' are making a false implication that there are "subway lines". I wonder why they used it. Graph formulation: Let $G$ be a simple graph with at least three vertices and a path of length $L$. Prove that if $G$ is 2-connected, there exists a cycle of length at least $\sqrt{2L}$.

drkim wrote: The 'subways' are making a false implication that there are "subway lines". I wonder why they used it. Graph formulation: Let $G$ be a simple graph with at least three vertices and a path of length $L$. Prove that if $G$ is 2-connected, there exists a cycle of length at least $\sqrt{2L}$. It seems that KMO likes to take graph problems into long word problems

Let the route of length $L$ pass through subway stations $A=(a_1,a_2,...a_L)$. By condition 1, if $1<j<L$, then there must be $(r,s)$, such that $r<j<s$, and $a_r,a_s$ are connected by a route that doesn't pass through any other element of $A$. Define $f(j)=(r,s)$ such that $|r-s|$ is maximal. Suppose that $v$ is the maximal path length, and $L=kv+a$. Then we must clearly have $f(j) \le v$. Now define $i_1,i_2,...i_m$ and $j_1,j_2,...j_n$ as follows. Let $i_1=1, f(2)=(i_1,i_2),f(i_2)=(j_1,j_2),f(j_2)=(i_3,i_4),f(i_4)=(j_3,j_4),...$ until one of the $i$ or $j$ equals $L$. Note that $i_{2k}$ and $i_{2k+1}$ are not necessarily distinct. Now consider $f(i_{2k})=(j_{2k-1},j_{2k})$. If $j_{2k-1} \le i_{2k-1}$, then we have $j_{2k-1}\le i_{2k-1}<i_{2k}<j_{2k}$ and so $|j_{2k}-j_{2k-1}|>|i_{2k}-i_{2k-1}|$, which is impossible since it contradicts the maximality definition of $f(j_{2k-2})$. We can see that this also prohibits the route from $i_{2k-1}$ to $i_{2k}$ which excludes $A$ and the similar route from $j_{2k-1}$ to $j_{2k}$ from intersecting outside of $A$. We can now construct our path. (I'll use $x$ instead of $a_x$ here to make the notation easier to write.) Start at $i_1$. Go to $i_2$ avoiding $A$. Then travel within $A$ to $i_3$, avoid $A$ to $i_4$, travel within $A$ to $i_5$, etc. When we reach $i_m$ travel within $A$ to $j_n$ and work backwards in a similar manner until we get to $j_1$ and and finally travel within $A$ to return to $i_1$. As we've seen this path does not intersect with itself within $A$. And neither does it outside of $A$. (That too would violate the maximality of $f$). Now let's count the number of points in the path. In the first case, assume that $i_m=L, a>0$. Since $|i_{k+1}-i_k| \le v$, then $m \ge k+2$, and $n \ge k+1$, so the path has length aleast $2k+3 \le v$. Then $L \le (k+1)v \le v^2/2$, and we're done. If $a=0$, we get similarly $2k+1 \le v$ and $L =kv \le v^2/2$. The other cases involve $j_n=L$ and work out pretty much the same way.

drkim wrote: Graph formulation: Let $G$ be a simple graph with at least three vertices and a path $P$ of length $L$. Prove that if $G$ is 2-connected, there exists a cycle of length at least $\sqrt{2L}$. I prefer it that way. Let $a$ and $b$ be the end vertices the path $P$. Since $G$ is 2-connected there is a cycle $C$ through $a,b$. Denote by $m$ the length of $C$. If $m\geq \sqrt{2L}$ we are done, so assume $m<\sqrt{2L}$ Consider how the path $P$ intersects $C$. There will be two vertices $a',b'$ of $P$ lying on the cycle $C$, so that the segment of the path between $a'$ and $b'$ does not intersect $C$ and has length at least $\frac{L}{m}$. Consider the cycle $C'=a'Pb'Ca'$, where $b'Ca'$ is the bigger arc of the cycle connecting $a'$ and $b'$. The length of $C'$ is at least \[ \frac{L}{m}+\frac{m}{2}.\]As a function of $m$, for $m\in[3,\sqrt{2L}]$ it attains its minimum when $m=\sqrt{2L}$, and in that case the length of $C$ would be at least $\sqrt{2L}$. Comment: In the R. Diestel's book "Graph theory" there is an exercise,(Chapter 1/exercise 3): Let $G$ be a graph containing a cycle $C$, and assume that $G$ contains a path of length at least $k$ between two vertices of $C$. Show that $G$ contains a cycle of length at least $\sqrt{k}$. Is this best possible? Isn't it similar to the above problem. The "cycle $C$ " had been removed and and instead of it, it was imposed $G$ to be 2-connected, which of course implied the existence of such a cycle. Now, the question is: what is the biggest possible constant $c$, such that we can state the existence of a cycle with length at least $c\cdot\sqrt{k}$. As shown above for $c=\sqrt{2}$ it's true. A couple of years ago I was challenged by a friend to prove it still holds for $c=2$ (an easy counterexample shows for $c>2$ it's not true). I think it's a tough problem, or at least I hadn't managed it. He wrote some article about it but I don't know if $c=2$ is still an open problem.

I heard that Junghun Ju the perfect scorer of this exam solved $ 2 \sqrt{L} $ in the exam.

<dgrozev> wrote: Let $a$ and $b$ be the end vertices the path $P$. Since $G$ is 2-connected there is a cycle $C$ through $a,b$. ..... the segment of the path between $a'$ and $b'$ does not intersect $C$ and has length at least $\frac{L}{m}$. Why? Can you elaborate those?

toto1234567890 wrote: I heard that Junghun Ju the perfect scorer of this exam solved $ 2 \sqrt{L} $ in the exam. I've heard that someone had heard that the Earth is flat. dgrozev wrote: ..(an easy counterexample shows for $c>2$ it's not true) I've been asked, through a PM, to provide such an example and I decided to provide it here, in the original thread. The following construction is not mine. Let's remind the problem. Find the greatest absolute constant $c$ for which the following claim is true (for any $k$). Let $G$ be a graph containing a cycle $C$, and assume that $G$ contains a path of length at least $k$ between two vertices of $C$. Show that $G$ contains a cycle of length at least $c\cdot\sqrt{k}$. The above posts show the claim is true for $c=\sqrt{2}$. I believe that the claim is also true for $c=2$, but I can't prove it. Here is an counterexample why the claim is false when $c>2$. Let $k=m^2$. Consider a cycle with $2m$ vertices $A_1,A_2,\dots,A_{2m}$. Consider the pairs of vertices: $(A_1,A_{2m});(A_{2m},A_2);(A_2,A_{2m-1}) ; \dots ; (A_m,A_{m+1})$. Between the vertices in every pair put new vertices, and connect them to form a path (with the paired vertices as its end vertices) with length correspondingly $1, 2, \dots, m-1; m; m-1, \dots, 2, 1$. Then total path length is $\sum_{i=1}^m i +\sum_{i=1}^{m-1} i=m^2=k $ and it's easily checked the maximal cycle length is $2m=2\sqrt{k}$.

TIL that the following proposition is true, which implies the claim mentioned above is true for $c=2$: Quote: Let $G$ be a $2$-connected simple graph and let $\ell$ be the maximum length of circuits in $G$. Then $G$ contains no path of length $\Big\lfloor \frac{\ell^2}{4}\Big\rfloor +1$.

Can you share that paper?

Whenever there is $\sqrt{n}$ always think of double counting or maximality. I will show if (i) fails then (ii) holds. Claim 1: There exist a cycle between any two vertices $u,v$. Proof: Condition (i) suggests the remova of any vertex does not disconnect the graph. Let $P=u\rightarrow x_1\rightarrow x_2\rightarrow \cdots \rightarrow x_t\rightarrow v$ be a path from $u$ to $v$ There is another path from $u$ to $v$ that doesn't use $x_1$, say $u\rightarrow y_1\rightarrow \cdots \rightarrow y_m\rightarrow x_k \rightarrow \cdots \rightarrow v$, where $k$ is the smallest integer that satisfies $x_k$ from $P$. Then there is another path from $y_m$ to $v$ that doesn't use $x_k$. If it uses any of the previously encountered vertices from $x$ to $y_{k-1}$ (namely $y_1,\cdots,y_{k-1}$) then I go back to this vertex. Then from whichever vertex, I construct another path from this vertex to $v$. This process eventually ends, creating a path from $u$ to $v$ that doesn't use any other vertex from $P$. Now we are ready to solve the problem. It is actually better to consider two disjoint paths instead of a cycle Let $Q=v_1\rightarrow v_2\rightarrow \cdots v_{l+1}$ be the path of length $l$. For convenience, let $M=\lfloor \sqrt{2l} \rfloor$. Let $S$ be the set of edges that are not in this path. If $S$ connects $v_i$ with $v_{i+k}$ where $k\ge M-1$, then there is a cycle going from $v_i\rightarrow v_{i+1}\rightarrow \cdots \rightarrow v_{i+k}$ then going back to $v_i$ with $S$. Otherwise, to go from $v_1$ to $v_{l+1}$, there are two disjoint paths. Let $S_1$ be the set of vertices in the first path that is also in $Q$ that are not $v_1$ or $v_{l+1}$ and $S_2$ be the set of vertices in the second path also in $Q$ that are not $v_1$ or $v_{l+1}$. We know $S_1\cap S_2=\emptyset$, $|S_i|\ge \frac{L}{\lfloor \sqrt{2L} \rfloor}$. Therefore, the length of this cycle is at least $\frac{2L}{\lfloor \sqrt{2L} \rfloor}$, as needed.

drkim wrote: Graph formulation: Let $G$ be a simple graph with at least three vertices and a path of length $L$. Prove that if $G$ is 2-connected, there exists a cycle of length at least $\sqrt{2L}$. This bound is strict. Define a path $P = a_1 \rightarrow a_2 \rightarrow \dots\rightarrow a_{L+1}.$ Consider any two vertices $a_i,a_j$ where $a_i$ and $a_j$ are connected by a path not using any vertex in $P$ between the two endpoints. Then for all such $i,j$ we have $|i-j| < \lfloor \sqrt{2L} \rfloor - 1,$ or we have our cycle of length $\ge \lfloor \sqrt{2L} \rfloor.$ Otherwise, consider two disjoint paths going from $a_1$ to $a_{L+1}.$ Each of these paths must share at least $$\frac{L}{\lfloor \sqrt{2L} \rfloor -2} +1 > \frac{L}{\lfloor \sqrt{2L} \rfloor} + 1$$vertices (including the end points) with $P.$ Otherwise, we have points $a_i,a_j$ of the form outlined above where $|i-j| \ge \lfloor \sqrt{2L} \rfloor - 1$ through a simple pigeonhole argument. So the union of these paths is a cycle more than $$2\left( \frac{L}{\lfloor \sqrt{2L} \rfloor} + 1 \right) - 2 = \frac{2L}{\lfloor \sqrt{2L} \rfloor} \ge \sqrt{2L}$$long (we subtract by two since $a_1, a_{L+1}$ are counted twice). $\square$

Let $P=v_0\to \cdots \to v_L$ be a path of length $L$. Restrict the first condition to $A,B,C \in P$; I will show that one of the conditions still holds. Suppose that neither of them do. The first condition evidently implies that for any $k$, there exist $i<k<j$ such that $v_i$ and $v_j$ are connected by a path vertex-disjoint from $P$ (other than at $v_i$ and $v_j$).On the other hand, if this fact is true then the first condition clearly holds as well. Let the start and end of a path disjoint from $P$ be the vertices $v_i$ and $v_j$ with $i<j$, and let the signature of a path be the set of vertices $\{v_{i+1},\ldots,v_{j-1}\}$. We make the following "circular optimizations" that won't increase the size of any cycle (here a "path" is disjoint from $P$, other than at the starting and ending vertices): If two paths from $v_a$ to $v_b$ and $v_c$ to $v_d$ aren't disjoint, then delete some edges/vertices and replace it with a path from $v_{\min(a,b)}$ to $v_{\max(b,d)}$. Henceforth assume paths are disjoint, except possibly at endpoints. If one path's signature is fully contained in another, delete it. If multiple paths start in the interior of the same path's signature, delete all but the one that ends last. Likewise, if multiple paths end in the interior of the same path's signature, delete all but the one that starts first. The result is that every path has at most one other path starting in its signature and at most one other path ending in its signature. On the other hand, using the first condition implies that $v_0$ and $v_L$ both have paths through them, and that every path other than the first has exactly one path starting in its signature. Thus we may order the paths $p_1,\ldots,p_k$, where $p_1$ is the (unique) path through $v_0$ and $p_{i+1}$ is the unique path starting in the signature of $p_i$ (and ends outside it, as well as the end of $p_i$); note that $p_k$ passes through $v_L$. Now consider the following cycle. Start at $v_0$. Go to the end of $p_1$ along it, and then to the start of $p_3$ along $P$. Then go to the end of $p_3$ along it, and then to the start of $p_5$ along $P$. Repeat until we run out of paths. If we're at $v_L$, then go to the end of $p_{k-1}$. Go to the start of $p_{k-1}$, then to the end of $p_{k-3}$ along $P$, and repeat. Otherwise, go to $v_L$. Then go to the start of $p_k$, then to the end of $p_{k-2}$ along $P$, and repeat. When we run out of paths, go back to $v_0$ along $P$. Due to our previous modifications, it is clear that this is actually a cycle: moving from the end of $p_i$ to the start of $p_{i+2}$ (likewise the start of $p_i$ to the end of $p_{i-2}$) along $P$ takes place entirely within the signature of $p_{i+1}$, but outside the signatures of $p_i$ and $p_{i+2}$. It is finally time to look at the second condition. Our cycle can be naturally separated into two paths: the first half where we go from $v_0$ to $v_L$, and the second where we go from $v_L$ to $v_0$. If the second condition is false, then if a path is from $v_i$ to $v_j$ we have $j-i\leq \sqrt{2L}$. It thus follows that we need at least $L/\sqrt{2L}=\sqrt{L/2}$ edges in the first path. Likewise we need at least $\sqrt{L/2}$ edges in the second path, for a total of at least $\sqrt{2L}$ edges (hence vertices) in total: contradiction. $\blacksquare$

ThE-dArK-lOrD wrote: TIL that the following proposition is true, which implies the claim mentioned above is true for $c=2$: Quote: Let $G$ be a $2$-connected simple graph and let $\ell$ be the maximum length of circuits in $G$. Then $G$ contains no path of length $\Big\lfloor \frac{\ell^2}{4}\Big\rfloor +1$. This problem is from famous book by Lovász, <Combinatorial Problems and Exercises>. See chapter 10, problem 29(p76).