Максимальное количество путей длины 2 в графе с N узлами

Question

Каково максимальное количество уникальных путей длины 2 в графе с n узлами?

Answer 1

Я думаю, что это просто сумма степеней, выбирающих два по всем узлам со степенью больше единицы:

Answer 2

путь длины 2 от u до v есть u-> u0-> v (где u0 - другая вершина в графе). в клике вы можете выбрать для каждого из n-2 (все, кроме u, v) значение u0.
так что у вас есть n-2 пути между каждыми двумя узлами - длиной 2.
так что в целом вы можете выбрать, какие вы и v: choose(2,n) = n!/((n-2)!), и для каждого из них у вас есть n-2 возможностей, итого: n!*(n-2)/((n-2)!)= n!/((n-3)!)=n*(n-1)*(n-2)