Введём граф, вер­ши­на­ми ко­то­ро­го будут чипы, а ребро между вер­ши­на­ми про­ведём в том и толь­ко том слу­чае, если со­от­вет­ству­ю­щие чипы со­еди­не­ны про­во­да­ми.

Будем опи­сы­вать граф в виде по­сле­до­ва­тель­но­сти целых чисел (a₁, a₂, ..., a_n), где a_i озна­ча­ет сте­пень вер­ши­ны i. Будем на­зы­вать по­сле­до­ва­тель­ность целых чисел (a₁, a₂, ..., a_n) ре­а­ли­зу­е­мой, если су­ще­ству­ет граф, опи­са­ние ко­то­ро­го сов­па­да­ет с (a₁, a₂, ..., a_n). В усло­вии спра­ши­ва­ет­ся, ре­а­ли­зу­е­ма ли по­сле­до­ва­тель­ность (9, 8, 7, 5, 5, 3, 3, 3, 2, 1).

За­ме­тим сле­ду­ю­щие два про­стых факта.

1.  Пусть тогда если ре­а­ли­зу­е­ма по­сле­до­ва­тель­ность (a₁, a₂, ..., a_n), то ре­а­ли­зу­е­ма и по­сле­до­ва­тель­ность

Для ре­а­ли­за­ции до­ста­точ­но от­ки­нуть вер­ши­ну с но­ме­ром i.

2.  Пусть тогда если ре­а­ли­зу­е­ма по­сле­до­ва­тель­ность (a₁, a₂, ..., a_n), то ре­а­ли­зу­е­ма и по­сле­до­ва­тель­ность

Дей­стви­тель­но, если то вер­ши­на с но­ме­ром i долж­на быть со­еди­не­на со всеми осталь­ны­ми вер­ши­на­ми, по­это­му до­ста­точ­но от­ки­нуть её и все вы­хо­дя­щие из неё рёбра.

Пред­по­ло­жим про­тив­ное и пусть по­сле­до­ва­тель­ность (9, 8, 7, 5, 5, 3, 3, 3, 2, 1) ре­а­ли­зу­е­ма. Поль­зу­ясь фак­та­ми 1 и 2 по­сле­до­ва­тель­но по­лу­ча­ем, что тогда ре­а­ли­зу­е­мы и по­сле­до­ва­тель­но­сти

но по­сле­до­ва­тель­ность (2, 2), оче­вид­но, не ре­а­ли­зу­е­ма. Про­ти­во­ре­чие; зна­чит, наше пред­по­ло­же­ние не­вер­но и по­сле­до­ва­тель­ность (9, 8, 7, 5, 5, 3, 3, 3, 2, 1) не ре­а­ли­зу­е­ма.

Ответ: нет, не может.

При­ве­дем дру­гое ре­ше­ние.

Ана­ло­гич­но пер­во­му ре­ше­нию введём граф. За­ме­тим, что если (d₁, d₂, ..., d_n) сте­пе­ни вер­шин не­ко­то­ро­го графа без пе­тель и крат­ных рёбер; то для каж­до­го k вы­пол­не­но не­ра­вен­ство

Дей­стви­тель­но, все рёбра, вы­хо­дя­щие из вер­шин с но­ме­ра­ми от 1 до k де­лят­ся на два типа:

1)  иду­щие в вер­ши­ны с но­ме­ра­ми от до n  — таких не боль­ше

2)  иду­щие в вер­ши­ны с но­ме­ра­ми от 1 до k  — таких не боль­ше но каж­дое мы можем по­счи­тать по два раза.

В за­да­че нас спра­ши­ва­ют, су­ще­ству­ет ли граф со сте­пе­ня­ми вер­шин (9, 8, 7, 5, 5, 3, 3, 3, 2, 1). Пред­по­ло­жим, что он су­ще­ству­ет, и вос­поль­зу­ем­ся до­ка­зан­ным утвер­жде­ни­ем для пер­вых 5 вер­шин:

про­ти­во­ре­чие.