Математика,возможно связано с графами В клубе состоят 10 джентльменов, некоторые из них знакомы между собой. Оказалось, что любую четвёрку джентльменов можно разбить на две пары так, чтобы в каждой паре джентльмены были знакомы между собой. Найдите наименьшее возможное количество пар знакомых в этом клубе.

Предыдущий
вопрос Следующий
вопрос

Пусть у нас есть N джентльменов и M пар, где каждая пара представляет собой знакомые между собой джентльмены.

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

Возьмем две произвольные пары: (a, b) и (c, d). Если они не пересекаются, то у нас есть 4 знакомых джентльмена, а также 2 джентльмена, не знакомых ни с кем из первых 4. Теперь возьмем джентльмена из одной из пар, скажем a, и четвертого джентльмена e. Если джентльмен a знаком с еще одним из джентльменов той пары (допустим, b), то e должен быть знаком с двумя джентльменами из первой пары, но тогда один из этих джентльменов не будет знаком с b, что противоречит условию. Следовательно, джентльмен a должен быть знаком только с dжентльменом (назовем его f) из второй пары, но тогда он будет знаком также с двумя джентльменами из первой пары, что противоречит условию.

Таким образом, две произвольные пары джентльменов должны пересекаться. Представим это графически, где вершины представляют джентльменов, а ребра - знакомство между ними. Два подграфа с взаимосвязанными вершинами должны иметь хотя бы одно общее ребро.

Из теоремы Турана для шести вершин и пяти связанных ребер следует, что наименьшее возможное количество ребер в графе из 6 вершин, где каждые 4 вершины образуют полный подграф, равно 5. Мы можем добавить к этим 5 ребрам еще 4 ребра для связи последних 4 вершин со всеми предыдущими.

Итак, наименьшее возможное количество пар знакомых в этом клубе составляет 9.