===== №105 =====

** Конкурсная задача ММ105 ** (6 баллов)

Математик C загадал некий граф и сообщил математику A степени всех вершин,
а математику B - количество вершин и число связных компонент этого графа.
Дальше, как водится, состоялся обмен мнениями.\\
A: Знание степеней всех вершин графа не позволяет мне однозначно определить, 
какой граф был загадан.\\
B: Зато я теперь в состоянии сделать это.

Сколько ребер было в загаданном графе?   

Примечание:\\
Рассматриваются классические графы (неориентированные, без петель и кратных
ребер).

**Решение**

Приведу (немного подредактированное) решение Виктора Филимоненкова.

Пусть k - число компонент связности графа, n - число вершин, сообщенные В, а m -
искомое число ребер. Напомню, что в любом графе справедливо соотношение
n-k ≤ m ≤ C<sup>2</sup><sub>n-k+1</sub> (*). 
Напомню, также, что K<sub>n</sub> - это полный n-вершинный граф.

1. n-k < 4. Действительно, иначе одна из компонент связности может содержать
5 вершин. Среди связных пятивершинных графов есть два неизоморфных графа с одним
набором степеней вершин, это 1, 2, 2, 2, 3 (цикл длины 4 с "хвостом" длины 1 и
цикл длины 3 с "хвостом" длины 2). Значит, В в этом случае не может исключить, 
что одна из компонент связности - один из таких пятивершинных графов, и его 
знаний количеств вершин и компонент связности не хватит для того, чтобы определить,
какая именно эта компонента связности.

2. Коротким простым перебором легко убедиться, что при n-k < 3 граф однозначно
восстанавливается по степеням вершин.

3. При n-k = 3 на основании (*) возможны следующие наборы ненулелвых степеней вершин 
(кроме них, в графе может присутствовать произвольное количество изолированных вершин):\\
1) 1,1,1,1,1,1 - 1 граф;\\
2) 1,1,1,1,2 - 1 граф;\\
3) 1,1,2,2,2 - 2 графа (3.a граф с компонентами K<sub>3</sub> и K<sub>2</sub>, 3.б - цепь);\\
4) 1,1,1,3 - 1 граф;\\
5) 1,1,2,2 - 1 граф;\\
6) 1,2,2,3 - 1 граф;\\
7) 2,2,2,2 - 1 граф;\\
8) 2,2,3,3 - 1 граф;\\
9) 3,3,3,3 - 1 граф.\\
Таким образом, только в случае 3 A имел право на свою реплику. Отметим, что 
граф из пункта граф 3.б соответствует соотношению n-k = 4, а этом случае, как было 
показано, B не может однозначно определить заганный граф. Поэтому был загадан 
граф из пункта 3.a, имеющий (как, впрочем, и граф из 3.б) 4 ребра.

Ответ: 4 ребра.

**Обсуждение**

Отмечу, что условие задачи не позволяет однозначно восстановить загаданный граф. 
Ведь, кроме компонент K<sub>3</sub> и K<sub>2</sub>, в графе может содержаться несколько компонент K<sub>1</sub>.

**Награды**

За правильное решение задачи ММ105 Виктор Филимоненков, Кирилл Веденский и Анатолий 
Казмерчук получают по 6 призовых баллов, а Николай Дерюгин (почему-то сразу же 
положивший n = 5) - 3 балла.

**Эстетическая оценка задачи - 4.3 балла**
----