Given a complete graph of $n$ vertices. Each edge $ab$ is given a direction (either $a\rightarrow b$ or $b\rightarrow a$). Is it possible that these two conditions are satisfied simultaneously?
(i) There is no cycle.
(ii) The vertices cannot be labeled $a_1,\ldots,a_n$ in such a way that $a_i\rightarrow a_j$ if and only if $i<j$.
On
No
Because you can enumerate vertices in a such way. Take first vertex and pull graph in one line so that the edges looked to one side. Vertices will be labeled by the order on this line.
How to pull graph G in one line.
(1) Find vertex X without incoming edges. Take arbitrary vertex of G and go back. This motion must stop (on vertex X) because G have no cycles.
(2) Starting from X go forward (induction on subgraph $G\setminus X$) and you will enumerate all vertices because G have no cycles.
On
No. If there are no cycles, then you can find such enumeration. It is called a topological sorting. Here is a reference: http://en.wikipedia.org/wiki/Topological_sorting. Here is the algorithm: For i=1,...,n do: - Find a vertice that has no in-edges. - Enumerate it as i - remove it from the graph
If there are no cycles then you can find a vertice with no incoming edges. To find it, you do the following: Pick a vertex v0 from the graph. If it has an incoming edge, (v1,v0), then go to v1, and check if it has an incoming edge. Keep doing it until you reach a vertex with no incoming edges. Note that you cannot return to the same vertex twice, since there are no loops. Thus this should stop, and you will find such vertex.
Here's a more rigorous proof. Suppose you have such a directed complete graph. I'll say that a vertex $a < b$ if there is an edge $a\rightarrow b$.
Claim: If there are no cycles, then there exists a "minimum" vertex $v$, in the sense that every edge goes out of $v$.
Proof of claim: We proceed by induction. This is certainly true for directed complete graphs (DCG) of size 2. Suppose we know the claim for any DCG of size $n$. Any DCG of size $n+1$ (call it $G'$) is obtained from a DCG of size $n$ (call it $G$) by adding a new vertex $v$, and choosing edges from $v$ to every vertex of $G$. Let $w$ be the minimum vertex of $G$. If there is an edge $w\rightarrow v$, then of course $w$ is the minimum vertex for $G'$. If instead you have a edge $v\rightarrow w$, then for any vertex $w'\in G$, we already have edges $w\rightarrow w'$, and so the edge connecting $v$ and $w'$ must go $v\rightarrow w'$ (otherwise you'd get a cycle $v\rightarrow w\rightarrow w'\rightarrow v$). This shows that $v$ is the minimum vertex for $G'$.
This shows that every DCG with no cycles has a minimum. Thus, let $G$ be a DCG with size $n$. Then it has a minimum vertex, so label it $v_1$. The remaining $n-1$ vertices form a DCG with size $n-1$. It must also have a minimum vertex, so label it $v_2$. The remaining $n-2$ vertices form a DCG with size $n-2$...etc.
This procedure naturally gives you a labeling as described in (ii).