Разделы 
Дополнительно
Задача по математике - 2027
2019-01-23 
В стране несколько городов, некоторые пары городов соединены двусторонними беспосадочными авиалиниями, принадлежащими к авиакомпаниям. Известно, что любые две линии одной авиакомпании имеют общий конец. Докажите, что все города можно разбить на $k + 2$ группы так, что никакие два города из одной группы не соединены авиалинией.
Решение:
Индукция по $k$. Если $k = 0$, утверждение тривиально: авиалиний нет.
Рассмотрим граф, вершины которого соответствуют городам, а ребра - авиалиниям. Пусть $E_1, E_2, \cdots, E_k$ - группы ребер, соответствующие авиалиниям первой, второй, $\cdots, k$-й авиакомпаний. Нетрудно понять, что для любого $i \in {1,\cdots, k}$ группа $E_i$ - либо треугольник, либо «ёж» - несколько ребер с одним концом. Если какая-то группа $E_i$ - ёж с центром в вершине $А$, то удалим $А$ и все выходящие из нее ребра. В оставшемся графе ребра принадлежат $k - 1$ авиакомпании, его вершины мы разобьем на $k + 1$ группу так, чтобы вершины из одной группы не были соединены ребром, а вершина $А$ составит $(k + 2)$-ю группу.
Остается рассмотреть случай, когда все группы $E_1, \cdots, E_k$ - треугольники. Тогда всего в графе $3k$ ребер. Разобьем вершины графа на минимальное возможное количество групп так, что никакие две вершины одной группы не смежны (т. е. не соединены ребром). Пусть это группы $B_1,\cdots, B_n$, причем $n \geq k + 3$. Отметим, что для любых двух групп $B_i$ и $B_j$ существует ребро между вершиной из $B_i$ и вершиной из $B_j$, иначе можно объединить эти две группы в одну. Таким образом, всего в графе хотя бы $\frac{n(n-1)}{2}$ ребер. Отметим, что $\frac{n(n-1)}{2} \geq \frac{(k+3)(k+2}{2} > 3k$ противоречие, завершающее решение задачи.
В стране несколько городов, некоторые пары городов соединены двусторонними беспосадочными авиалиниями, принадлежащими к авиакомпаниям. Известно, что любые две линии одной авиакомпании имеют общий конец. Докажите, что все города можно разбить на $k + 2$ группы так, что никакие два города из одной группы не соединены авиалинией.
Решение:
Индукция по $k$. Если $k = 0$, утверждение тривиально: авиалиний нет.
Рассмотрим граф, вершины которого соответствуют городам, а ребра - авиалиниям. Пусть $E_1, E_2, \cdots, E_k$ - группы ребер, соответствующие авиалиниям первой, второй, $\cdots, k$-й авиакомпаний. Нетрудно понять, что для любого $i \in {1,\cdots, k}$ группа $E_i$ - либо треугольник, либо «ёж» - несколько ребер с одним концом. Если какая-то группа $E_i$ - ёж с центром в вершине $А$, то удалим $А$ и все выходящие из нее ребра. В оставшемся графе ребра принадлежат $k - 1$ авиакомпании, его вершины мы разобьем на $k + 1$ группу так, чтобы вершины из одной группы не были соединены ребром, а вершина $А$ составит $(k + 2)$-ю группу.
Остается рассмотреть случай, когда все группы $E_1, \cdots, E_k$ - треугольники. Тогда всего в графе $3k$ ребер. Разобьем вершины графа на минимальное возможное количество групп так, что никакие две вершины одной группы не смежны (т. е. не соединены ребром). Пусть это группы $B_1,\cdots, B_n$, причем $n \geq k + 3$. Отметим, что для любых двух групп $B_i$ и $B_j$ существует ребро между вершиной из $B_i$ и вершиной из $B_j$, иначе можно объединить эти две группы в одну. Таким образом, всего в графе хотя бы $\frac{n(n-1)}{2}$ ребер. Отметим, что $\frac{n(n-1)}{2} \geq \frac{(k+3)(k+2}{2} > 3k$ противоречие, завершающее решение задачи.
