Let $G = (V,E)$ be a directed graph on $n$ vertices, $V = \{1, \ldots,n\}$, such that for every pair of distinct vertices $i, j \in V$, exactly one of the two possible directed edges $(i, j)$ or $(j, i)$ is in the edge set $E$ (but not both). Prove that there must exist a permutation $(A_1, \ldots, A_n)$ of the vertices $V =\{1, \ldots,n\}$,such that for all $i\in \{1, \ldots,n−1\}, (A_i,A_{i+1})\in E$.
I can think of how it is true but got stuck on proving it. Could anyone please help?
We show it by induction on the number of vertices in the graph $G$.
Base case: when there is only two vertices, the claim is true. Assume now that for graph with $n$ vertices, the claim is true, we have to show that a graph on $n+1$ vertices, the claim is true.
So let $G$ be a graph on $n+1$ vertices $\{v_1,...,v_{n+1}$}. let's look at the vertex $v_{n+1}$,
Case 1:suppose it is adjacent only to outgoing edges. Then by induction hypothesis, the graph induced by vertices $\{v_1,...,v_n\}$ has a directed path, says, $v_1,...,v_n$. Well now, $v_{n+1},v_1,...,v_n$ is a directed path in $G$.
Case2: Suppose $v_{n+1}$ is adjacent to only ingoing edges, then by induction hypothesis, the graph induced by vertices $\{v_1,...,v_n\}$ has a directed path, says, $v_1,...,v_n$. Well now, $v_1,...,v_n,v_{n+1}$ is a directed path in $G$.
Case3: Suppose it is not case 1 nor case 2, then again by induction hypothesis, the graph induced by vertices $\{v_1,...,v_n\}$ has a directed path, says, $v_1,...,v_n$. Suppose we have edge $(v_1,v_{n+1})$ and for all $i$, we have edges $(v_iv_{n+1})$ and $(v_{i+1}v_{n+1})$ for $1\leq i \leq n-1$, we are back to case 2. So there must be $1 \leq i \leq n-1$ such that $(v_i,v_{n+1})$ and $(v_{n+1},v_{i+1})$ are edges in the graph. Well, $v_1,...,v_i,v_{n+1},v_{i+1},...,v_n$ is a hamiltonian directed path! done