Question on graph theory regarding roads connecting a pair of cities 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?

Considering the way the question was put, the answer is “no”, since the roads are one-way. But I suppose you need help with the problem, so there’s my proof below.

I’ll proceed with a proof that is, basically, an inductive algorithm. In graph theory this is very common, so take a moment to understand what I did. 
Take the $n=2$ vertices. Then it holds trivially. Suppose by induction that it holds for all $n \leq n’$. For each vertex $v_i$, take the graph $G_i$ obtained by removing it and its edges. By hypothesis, $G_i$ has at least one vertex $v’_i$ with such property. If $v_i$ has only incoming edges, we’re done; it’s also done if $v_i \to v_j \to v’_i$ or $v_i \to v’_i$. We’ll proceed to prove that there must be such $v_i$ (in an algorithm, you can just test case by case; here we prove it exists).  
Suppose now that the cases above do not hold and fix some $i$. Then $v’_i \to v_i$. Take all the vertices $w \to v’_i$. Then $w \to v_i$ by hypothesis.  Take all the vertices $w’$ reaching $v’_i$ with necessarily and exactly 2 steps. But then $w’ \to w_j \to v_i$. Since every vertex (but $v_i$) of the initial graph is of one of the two types, we have that all the vertices of the graph reach $v_i$ in 2 or fewer steps, as we wanted. $\blacksquare$
