2
$\begingroup$

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:

enter image description here

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:

enter image description here

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

$\endgroup$

marked as duplicate by Chris Godsil, Misha Lavrov, José Carlos Santos, Namaste, Don Thousand Nov 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
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.