Я предполагаю, что у нас может быть Ω (n ^ 2) поперечных ребер. У кого-нибудь есть идеи, как это доказать?
Да. Возьмите турнир acycli c по n вершинам (n вершин, n выбирайте 2 дуги, без циклов). Root Обход в вершине с out-градусами n-1 и посещение узлов с out-градусами 0, 1, 2, ..., n-2 по порядку. Каждое не-дерево ar c является крестом ar c.