1)Havel-Hakimi algorithm
2) Hypothesis(my): sequence n/2 n/2 ... 3 3 2 2 1 1 0 0
realizable for each n
P.S. In timus there is a problem about full search:
monkey aplly full search on keyboard. When it create theorem.

Edited by author 09.10.2010 22:30

Iosif inf-10 : Sən harda oxuyursan?

я так понял нужно построить такой граф чтобы любые три вершины имели разную степень.

а в условии сказано что решение можно вывести любое.

У меня всегда есть ответ))
Пусть кол-во друзей четно. Пусть мы уже добавили 2k друзей и их валентности 112233...kk.
Давайте соединять 2 новые вершины с уже добавленными, начиная с тех, у кого большая валентность. Получим у новых вершин валентность 11, а у старых 1122..(k-1)(k-1)(k+1)(k+1). Продолжаем процесс пока не получим у новых mm, а у старых 112233...(m-1)(m-1)(m+1)(m+1)..(k+1)(k+1). Если получили, что на каком-то шаге у новых mm, а у старых 1122..(m)(m)(m+2)(m+2)..(k+1)(k+1), то соединяем новые между собой. Если n нечетно, последнюю вершину оставляем одной. Кол-во дуг в графе (n/2) * ((n/2) + 1) / 2.

thank you
but my program solution for N=5 (Accepted)
6
1 2
1 3
2 3
2 4
3 4
3 5