Graphs, at-most-one-intermediate paths and induction

Question

Consider a graph with $n\geq2$ vertices, where for every two different vertices ($u,v\in V, u\neq v$) either $(u,v)\in E$ or $(v,u)\in E$. Using mathematical induction, prove that there is a vertice $k\in V$ that can be reached with at most 1 intermediate vertice from every other vertice. (that is, either directly or through exactly one intermediate vertice)

Using induction on the number of vertices in the graph, the base case $n=2$ is trivial and then, on the inductive step, I randomly picked one vertice $u\in V$ and applied the inductive hypothesis for the rest of the vertices in the graph, obtaining the vertice $k_u\in V -\{u\}$. Then, either $(u, k_u)\in E$ in which case the inductive step is finished, or $(k_u, u)\in E$.

Then, I took more cases, but they always stuck at some point. How can this second case be continued? Or should the induction procedure be based on another basis? Seems that no matter how many cases I take, there will still be one that cannot be covered...

Answer 1

Call a vertex $k$ with this property a co-king. (I made up this word because the opposite notion, a vertex from which we can reach any other vertex in at most $2$ steps, is commonly called a king. Proving this problem for kings is actually equivalent.)

When you take away a vertex $u$ and find a co-king $k_u$ in $G-u$, you know that the vertices in $V - \{u\}$ can be partitioned into three groups:

• $\{k_u\}$, a group consisting only of the co-king you found;
• $N_1$, the set of all vertices $v$ such that $(v, k_u)$ is an edge.
• $N_2$, the set of all other vertices. Necessarily, for every vertex $w \in N_2$, there is a vertex $v \in N_1$ such that $(w,v)$ is an edge, because we can reach $k_u$ from all of $V - \{u\}$ in at most two steps.

You're right that if $(u, k_u)$ is an edge, then $k_u$ is a co-king for all of $G$, and the induction step is complete. In this case, we can add $u$ to $N_1$.

Even if $(u, k_u)$ is not an edge, if there's a vertex $v \in N_1$ such that $(u, v)$ is an edge, we still know that $k_u$ is a co-king for all of $G$. In this case, we can add $u$ to $N_2$, because we can reach $k_u$ from it in $2$ steps.

So in the final case, $(u,k_u)$ is not an edge, and for every $v \in N_1$, $(u,v)$ is not an edge. Then $k_u$ cannot be a co-king for all of $G$: it takes at least three steps to reach $k_u$ from $u$, and maybe it's impossible entirely.

However, in this last case, we can actually show that $u$ is a co-king for $G$. Can you see why?