Can two cities be connected by roads going both ways?

lifeisgood03 wrote: Can two cities be connected by roads going both ways? No

Let number of vertices is $n$. $n=2$ case It is trivial. Let $n$ is O.K., then $n+1$ case If every cyclic contains all vertices, we delete some cyclic.We start $v_{1}$, by hypothesis, we can get $v_{1}, \dots , v_{n+1}$.Because every cyclic contains all vertices, $v_{i}$ are pairwise distinct.So we're done. If some cyclic doesn't contain $v_{n+1}$, we delete this cyclic. ...I cannot proceed.

I can just use this logic that it's trivial to prove that you can find a closed path that is "travable" before removing anything, if you remove it, in the worst case scenario you would have for every vertex two cases:2 in and 1 out, or 2 out and 1 in, so you have at least one road In for everyone, so it's always possible to get to a city by some other city, so there must be some path that connects two arbitrary cities.Is what i said correct?

Using the Euler's path would be convenient in my view.

i think there's nothing meaningful to say about eulerian paths in a directed graph, or maybe there's another pretty fact that this community knows and i don't.

If out-bound and in-bound arcs are exactly two at every vertex (and the graph is strongly connected, as it is) such path does exist, and the problem is trivial. But it was said "every city has at least two out-going and two in-coming roads assigned to it, " Very nice problem. I spent some time over it when it appeared, but couldn't manage. Also the Russians don't publish the solutions of St. Peterburg (as they do it for All-Russians) , so we cannot see the official solution.

dgrozev wrote: If out-bound and in-bound arcs are exactly two at every vertex (and the graph is strongly connected, as it is) such path does exist, and the problem is trivial. But it was said "every city has at least two out-going and two in-coming roads assigned to it, " Yeah i tought about it, my mistake, thank you for correcting me, but let me try again one last time.For the case where there are only 2 in and 2 out for everyone, if i remove 1 in and 1 out from every vertex forming a closed cycle, i have 1in&out for everyone, and because the number of vertices is equal to the edges, because for every vertex, there's some edge going in, creating a bijection, they form a closed cycle, which is travable, cuz otherwise there would be 2 roads going out or in from some vertex.If the case 2 in &out isn't valid for everyone, than i can make it valid, by removing some edges.

anantmudgal09 wrote: In a country, some pairs of cities are connected by one-way roads. It turns out that every city has at least two out-going and two in-coming roads assigned to it, and from every city one can travel to any other city by a sequence of roads. Prove that it is possible to delete a cyclic route so that it is still possible to travel from any city to any other city. I hope it works. Let $G$ is the corresponding directed graph. We know $G$ is strongly connected and every vertex of $G$ has indegree and outdegree at least two. We take the longest (multi) cycle $C = v_1 v_2 \dots v_n=v_1$. By that, I mean the cycle may pass through some vertex many times, that's $v_i,i=1,\dots,n$ may not be distinct, but it's prohibited $C$ to pass trough some edge twice. Then, we take some sub-cycle of $C$, say $C' = v_j v_{j+1}\dots v_{j+k}=v_j$ such that all $v_{j+i}\,,\, i=0,1,\dots,k-1$ are distinct. We'll show that after removing the edges of $C'$ , the resulting graph $G_1$ is still strongly connected. Some other notations. By $C''$ we denote the multi cycle $v_{j+k}v_{j+k+1}\dots v_n v_2 v_3\dots v_{j+k}=v_j$. By $V''$ we denote the set of vertices of the multi cycle $C''$. By $V'$ we denote the vertices of $C'$ , which are not in $V''$. To prove that $G_1$ is strongly connected it's enough to show two things: 1) For any vertex $v\in V'$ , there is a path in $G_1$ connecting $v$ to some vertex of $C''$. 2) For any vertex $v\in V'$ there is a path in $G_1$ connecting some vertex of $C''$ to $v$. Let's begin with $1)$. The fact $v\in V'$ means $v$ is a simple node of $C$, because $C'$ has only simple nodes. Thus, following $C$ we visit $v$, then leave it and don't enter it again. Hence, there are two other edges not belonging to $C$ (thus in $G_1$), in-edge and out-edge, that are incident with $v$. We leave $v$ using that out-edge. If we hit the multi cycle $C$ it's ok, otherwise there will be a path, we can follow, that finally hits $C$ in a vertex $w_1$. If $w_1\in V''$ we are done. Otherwise we can again leave $w_1$ (following edges in $G_1$) and then following some other path to hit again $C$ in a vertex $w_2$. If $w_2\in V''$ we are done, else we can do it over again. In that way, we obtain a sequence $v P_1 w_1 P_2 w_2 \dots$ , where $P_i$ is a path between $w_{i-1}$ and $w_i$. Note that $w_1,w_2,\dots$ are distinct. Indeed, each path $P_i$ doesn't have edges lying in the multi cycle $C$, so if for example assume $w_r=w_s$ ,we can enlarge $C$ by adding a loop $w_r P w_s$, where $P$ is a path with edges not in $C$. It would contradict the maximality of $C$. Now, it is clear that finally the sequence $w_1,w_2,\dots$ will hit a vertex in $V''$ and we are done. To show 2) holds, we use the same technique, starting a walk from $v$ but walking against the direction of the edges of $G_1$. The arguments are exactly the same having in mind that convention.

I have another construction, can someone prove it works? Choose to delete the cycle, for which it holds that in the remaining graph (FTSoC suppose it is union of strongly connected components) there is such component with all its edges connecting vertices from the component to the other vertices (not in this component) are being only in one direction (either all such edges point to "outer" vertices, or to the vertices in the component), and this component has minimal possible size over all choices of the cycle to be deleted. I have also proven that there is a directed cycle in this component. Can someone continue this (like what happens when we delete this new cycle, and how we find such component with a smaller size)?

Bump, can someone check the above approach?