Вариант с пятиугольниками, пожалуй, не напрашивается: будет слабовато с симметричностью замощения.
В вариант шестиугольниками — конечно, годится; предположу, что автор даже пробовал, но не получил достаточно красивых картинок.
Задача 7:
Выберем самую большую клику в графе. Допустим, её размер 9 или меньше (и покажем противоречивость допущения). Тогда каждая из оставшихся вершин, которых как минимум 21, не имеет ребра с хотя бы одной вершиной из этой клики (иначе она вошла бы в клику). Принцип Дирихле: в клике есть вершина (A), которая не имеет рёбер с тремя вершинами (B,C,D) вне клики. Никакая пятёрка вершин, содержащая A и не связанные с ней B,C,D, не может составить цикл. Следовательно, размер максимальной клики больше 9.
В вариант шестиугольниками — конечно, годится; предположу, что автор даже пробовал, но не получил достаточно красивых картинок.
Выберем самую большую клику в графе. Допустим, её размер 9 или меньше (и покажем противоречивость допущения). Тогда каждая из оставшихся вершин, которых как минимум 21, не имеет ребра с хотя бы одной вершиной из этой клики (иначе она вошла бы в клику). Принцип Дирихле: в клике есть вершина (A), которая не имеет рёбер с тремя вершинами (B,C,D) вне клики. Никакая пятёрка вершин, содержащая A и не связанные с ней B,C,D, не может составить цикл. Следовательно, размер максимальной клики больше 9.