# A directed complete graph with equal number of incoming and outgoing edges [duplicate]

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$$?

## marked as duplicate by Chris Godsil, Misha Lavrov, José Carlos Santos, Namaste, Don ThousandNov 9 '18 at 16:53

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

## 2 Answers

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$$.

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, 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$$.