Graph theory question (on Tournaments)

266 Views Asked by At

For a simple digraph, with a complete underlying graph (or a Tournament):

$\text{in-degree}(v) + \text{out-degree}(v) = n-1$.

Hence show that

$\displaystyle\sum_{v \in V} (\text{indeg}(v))^{2} = \displaystyle\sum_{v \in V} (\text{outdeg}(v))^{2}$

My brain has turned to mush after many failed attempts. :p Any help appreciated!

2

There are 2 best solutions below

0
On

Hint: show that the sum of in degrees equal to the sum of out degrees.

This is a common problem in double counting.

0
On

Hint: let $A$ be the adjacency matrix of the graph. What can you say about $\mathrm{tr}\, AA^T$? Recall the cyclic property of the trace, $\mathrm{tr}\,AB=\mathrm{tr}\,BA,$ which follows immediately from the definition of trace.

Added: The answer above is no good. My apologies for possibly leading you astray. The argument above only gets you the fact that $$ \sum_v \text{in-degree}(v)=\sum_v\text{out-degree}(v), $$ but that is fairly obvious anyway and isn't needed to solve your problem. I would recommend the following instead: $$ \begin{aligned} \sum_v (\text{in-degree}(v))^2&=\sum_v ((n-1)-\text{out-degree}(v))^2\\ &=n(n-1)^2-2(n-1)\sum_v\text{out-degree}(v)+\sum_v (\text{out-degree}(v))^2. \end{aligned} $$ Now do the edge-counting for a complete graph to show that the first two terms cancel.