Решение. Введём граф, вершинами которого будут чипы, а ребро между вершинами проведём в том и только том случае, если соответствующие чипы соединены проводами.
Будем описывать граф в виде последовательности целых чисел (a1, a2, ..., an), где ai означает степень вершины i. Будем называть последовательность целых чисел (a1, a2, ..., an) реализуемой, если существует граф, описание которого совпадает с (a1, a2, ..., an). В условии спрашивается, реализуема ли последовательность (9, 7, 6, 5, 5, 3, 3, 2, 1, 1).
Заметим следующие два простых факта.
1. Пусть 
тогда если реализуема последовательность (a1, a2, ..., an), то реализуема и последовательность
Для реализации достаточно откинуть вершину с номером i.
2. Пусть 
тогда если реализуема последовательность (a1, a2, ..., an), то реализуема и последовательность
Действительно, если 
то вершина с номером i должна быть соединена со всеми остальными вершинами, поэтому достаточно откинуть её и все выходящие из неё рёбра.
Предположим противное и пусть последовательность (9, 7, 6, 5, 5, 3, 3, 2, 1, 1) реализуема. Пользуясь фактами 1 и 2 последовательно получаем, что тогда реализуемы и последовательности
но последовательность (2, 2), очевидно, не реализуема. Противоречие; значит, наше предположение неверно и последовательность (9, 8, 7, 5, 5, 3, 3, 3, 2, 1) не реализуема.
Ответ: нет, не может.
Приведем другое решение.
Аналогично первому решению введём граф. Заметим, что если (d1, d2, ..., dn) степени вершин некоторого графа без петель и кратных рёбер; то для каждого k выполнено неравенство
Действительно, все рёбра, выходящие из вершин с номерами от 1 до k делятся на два типа:
1) идущие в вершины с номерами от 
до n — таких не больше 
2) идущие в вершины с номерами от 1 до k — таких не больше 
но каждое мы можем посчитать по два раза.
В задаче нас спрашивают, существует ли граф со степенями вершин (9, 7, 6, 5, 5, 3, 3, 2, 1, 1). Предположим, что он существует, и воспользуемся доказанным утверждением для первых 5 вершин:
противоречие.
Ответ: нет, не может.
