Introduction to Graph Theory · Problem 4.13

Digraphs and multidigraphs — Darij Grinberg

Mathematics — Graph Theory · tournaments-3-cycles-counting

Problem

Let

D = (V, A)

be a tournament. Set

n = |V|

and

m = \sum_{v \in V} \binom{\deg^-(v)}{2}

. (a) Show that

m = \sum_{v \in V} \binom{\deg^+(v)}{2}

. (b) Show that the number of 3-cycles in

D

3\left(\binom{n}{3} - m\right)