The city is built on islands, some of which are connected by bridges (not more than one bridge between two islands). The bridge can only go in one direction, but from any island to any other you can get in no more than two bridges. One bridge was closed for repairs, but each island can still be reached by each. Prove that for any pair of islands you can get from one to another by no more than three bridges.
Some of my thinking, just 3 steps:
- Lets we have way from $A$ to $C$ of 2 bridges where $e1(A, B)=1, e2(B, C)=1$ and we delete $e2$ bridge. In that case we lose way between $A$ and $C$, and all ways from some islands which used $B$ like a transfer bridge. We know that anyway we can come from $A$ to $C$. Let some $D$ in the last step on that way and $e3(D, C)=1$. By the task we know that not more than 2 bridges between $A$ and $D$, so the way between $A$ and $C$ through the $D$ take not more than 3 bridges now, the same we can say for others which used $B$ like transfer island, now they also can going through the $D$. Second moment, that we lose all ways from $B$ to other through the $C$, and if for all of them we will use the same transfer point like $D$ anyway we will have not more than 3 bridges ways.
- Lets we have way from $A$ to $C$ of 2 bridges where $e1(A, B)=1, e2(B, C)=1$ and we delete $e1$ bridge. Right now we miss way from $A$ to $C$ and ways from some islands to B through the $A$. Lets chose some $F$ island where $e4(A, F)=1$, it directly exist because for any island we have at least 2 outcome bridges. So then from $F$ to $C$ where are anyway not more than 2 bridges and condition of 3 bridges from $A$ to $C$ is working. For the islands which used $e1$ like transfer lets chose something like $D$ from step number 1.
- Lets we have way from $A$ to $C$ of 1 bridge $e1(A, C)=1$ and we delete it. Then we missed way from $A$ to $C$ and ways from others through the $A$ like a transfer point. Let check helping $D$ island like in step number 1 for all of them. Second type of losing ways is from $A$ to other through the $C$. Let check some point like $D$ for each of them and get OK again.
If someone have any idea please help.
We can obtain a solution if we simplify your arguments as follows. Let $A$ and $C$ be any two distinct islands. Then initially there is a path from $A$ to $C$ of length at most $2$. So if the closed bridge doesn’t start at $A$ or ends at $C$ then it doesn’t belong to the path and we can use it. If the closed bridge starts at $A$ then pick any island $B$ (distinct from $A$ and $C$) which still can be reached from $A$ via one bridge. Such an island $B$ exists because otherwise $A$ would be disconnected from the other islands. There exists a path $p’$ of length at most two from $B$ to $C$. Since the direction on the bridge $AB$ is from $A$ to $B$, $A$ does not belong to $p’$, so $A-p’$ is a path from $A$ to $C$ of length at most three. The case when the closed bridge ends at $C$ is considered similarly.