I have the following question with me from "Problem Solving Strategies" by Arthur Engel, given as an example in page 44
"Every road in Sikinia is one-way. Every pair of cities is connected exactly by one direct road. Show that there exists a city which can be reached from every city directly or via at most one another city"
Isn't the statement that is required to be proved obvious from the given condition, if I connect any two cities, then obviously I can reach that city by the road right?
Best Answer
This is an extrema principal problem in the book I think: Consider the city $v$ with maximum incoming roads. The claim is that that $v$ is the right one. Why? Consider a city $u$ that does not have a directed road to $v$. And for all the cities $a$ that has a road into $v$, the road between $u$ and $a$ is from $a$ to $u$, well that says $u$ is actually the city with the most number of road that goes in, contradicting the choice of $v$. Hence, there is a city $a$, that has a road into $v$, such that the road between $u$ and $a$ is from $u$ to $a$ and then as the road between $a$ and $v$ is from $a$ into $v$, we can get from $u$ to $v$ using at most two road.