Given a complete graph $G$ on $n$ vertices and we assign direction to edges. Suppose that for any set of four vertices, it is not true that there is a vertex among the four with only in-edges and the edges between the rest of the three vertices form a directed triangle. Show that $$ S(G):=\sum_{i \in V(G)}(out(i)-in(i))^3 \geq 0$$

where $out(v)$ and $in(v)$ are the out degree and in degree of $v$ respectively.

Solution attempt:

if $|G|=4$, then the claim is true.

We look at case for $|G|>4$. For node $i \neq j$, let $\epsilon_{i,j}=1$ if there is an edge from $i$ to $j$ and $\epsilon_{i,j}=-1$ if there is an edge from $j$ to $i$. So $(out(i)-in(i))^3 =(\sum_{j\neq i}\epsilon_{i,j})^3=\sum_{j_1,j_2,j_3 \neq i}\epsilon_{i,j_1}\epsilon_{i,j_2}\epsilon_{i,j_3}$.

So $S(G) = \sum_{i \notin \{j_1,j_2,j_3\}}\epsilon_{i,j_1}\epsilon_{i,j_2}\epsilon_{i,j_3}$



You must log in to answer this question.

Browse other questions tagged .