A directed complete graph with equal number of incoming and outgoing edges

Question

In a complete graph with $n$ vertices, every vertex has $n-1$ edges. Assuming $n$ is odd, the number of edges from each vertex is even. If we now give every edge an orientation (making the graph a tournament), is it always possible to arrange the orientations such that every vertex has the same number of incoming and outgoing edges (apparently called a balanced directed graph)?

It is easy to give edges an orientation where the above is not true. E.g. orient all edges to a given vertex as incoming edges:

But it is also relatively easy to orient the edges so the above is true, at least for $n=3, 5, 7, 9$, which is what I've tried so far. An example for $n=5$ is given below:

But is it always possible for any odd $n$?

Answer 1

For odd $n$, the complete graph $K_n$ is a connected graph in which each vertex has even degree. If a (finite) graph $G$ is connected, and if each vertex has even degree, then $G$ has an Euler circuit, meaning that it's possible to walk on the edges of $G$ and return to the starting point in such a way that each edge is traversed exactly once. Define the orientation so that the Euler circuit traverses each edge in the forward direction; then each vertex has equal numbers of incoming and outgoing edges.

More generally, an undirected graph has a balanced orientation if and only if every vertex has even degree.

In the special case of $K_n$ where $n$ is odd, let the vertices be $n$ equally spaced points on a circle, and orient the edge $uv$ in the counterclockwise direction of the shorter arc between $u$ and $v$, as shown in your example for $n=5$.

Answer 2

Clearly this is not possible for any even $n$.

We will construct a graph with the desired property for each odd $n$. Let $n=2k+1$ and let the vertices of the graph be $\{v_1, v_2, ..., v_n\}$. For any pair of vertices $v_i$ and $v_j$ with $i<j$, orient the edge $(v_iv_j)$ toward $v_i$ if and only if$$ j-i\le k $$ Otherwise orient the edge toward $v_j$.

Note that for any vertex $v$, exactly $k$ edges are oriented toward $v$ and exactly $k$ edges are oriented away from $v$.