сумму всех возможных сумм, то есть чисел от 3 до 15: она равна 107
Чуть-чуть не совсем, так что не так всё просто.
Действительно, неверно, она равна 117. Тогда запрещена сумма 9.
Суммы, которые мы должны получить: 3..8, 9..15
3 получается одним способом: 1 + 2, 4 тоже одним способом: 1 + 3. То есть с вершиной 1 должны быть смежны вершины 2 и 3. 5 это либо 1 + 4, либо 3 + 2. ребро (3, 2) мы уже не можем поставить. Поэтому ставим на вершине смежной с 1 4. Таки образом получили что с вершиной 1 смежны 2, 3, 4. Теперь пытаемся получить 6: это либо 1 + 5, либо 2 + 4. Но таких ребер мы уже не можем провести. Значит все 12 сумм получить не получится