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?
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.
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$
For a (directed) graph $G$ by $V(G)$ denote the set of its vertices and by $E(G)$ the set of its edges. For each vertex $v$ of $G$ let $$N’(v)=\{u\in V(G):(u,v)\in E(G)\}$$ be the set of vertices $u$ of $G$ such that $v$ can be directly reached from $u$.
Then the natural graph theory formalization of the problem is that in any directed graph $G$ such that each two distinct vertices $v$, $u$ of $G$ are connected either by an edge $(v,u)$ or by and edge $(u,v)$ there exists a vertex $v$ such that $$V(G)=\{v\}\cup\{N’(v)\}\cup\bigcup\{N’(u):u\in N’(v)\}.$$
Prove this claim by induction with respect to the number $n\ge 1$ of vertices. For $n=1$ the claim is trivial. Assume that the claim is already proven for $n$. Let $G$ be a graph on $n+1$ vertices satisfying the claim condition. Pick any vertex $w$ of $G$. By the induction hypothesis, there exists a vertex $v$ of $G\setminus\{w\}$ such that $V(G) \setminus \{w\}\subset V’$, where $$V’=\{v\}\cup\{N’(v)\}\cup\bigcup\{N’(u):u\in N’(v)\}.$$ If $w\in V’$ then we are done. Otherwise $\{v\}\cup N’(v)\subset N’(w)$, so $$V(G) \setminus \{w\}\subset V’=\{v\}\cup\{N’(v)\}\cup\bigcup\{N’(u):u\in N’(v)\}\subset N’(w)\cup \bigcup\{N’(u):u\in N’(v)\}.$$ Then $$V(G)\subset\{w\}\cup N’(w)\cup\bigcup\{N’(u):u\in N’(v)\}.$$
