Предрамсеевские графы для R(3, 3), R(3, 4), R(4, 4)

[r-aax]

Добрый день.

Думая над числами Рамсея, я задался вопросом: если полный граф с количеством вершин $R(m, k)$, раскрашенный в два цвета (красный и синий), содержит либо полный красный граф порядка $m$, либо полный синий граф порядка $k$ в качестве подграфа, то какими свойствами обладают графы с количеством вершин $R(m, k) - 1$, которые не содержат таких подграфов.

В данной теме я попытаюсь ответить на этот вопрос для некоторых чисел Рамсея ($R(3, 3)$, $R(3, 4)$, $R(4, 4)$).

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

-- Ср июн 05, 2013 09:11:26 --

Базовые определения

В основных определениях мы будем следовать обозначениям из работы Tero Harju Lecture Notes on Graph Theory http://users.utu.fi/harju/graphtheory/graphtheory.pdf.

Пусть $V$ - конечное множество.
Тогда

$$E(V) = \{ \{ u, v \} \ | \ u, v \in V, \ u \ne v \} (1.1)$$

является множеством всех возможных неупорядоченных пар различных элементов из $V$.

Определение 1.1. Пару $G = (V, E)$, где $E \subseteq E(V)$ назовем графом (на множестве $V$). При этом, $V$ - множество вершин данного графа ($V_G$), а $E$ - множество ребер ($E_G$). Таким образом, $G = (V_G, E_G)$.

Пусть $X$ - конечное множество. Обозначим его размер (количество элементов данного множества) через $|X|$. Также в дальнейшем множество $\{1, 2, \dots, n\}$ будем обозначать через $[1, n]$.

Определение 1.2. Для графа $G$ введем обозначения

$$\nu_G = |V_G|, \ \varepsilon_G = |E_G|, (1.2)$$

и будем называть $\nu_G$ порядком графа $G$, а $\varepsilon_G$ - размером графа $G$.

Для ребра $e = uv \in E_G$ вершины $u$ и $v$ являются его концами. Вершины $u$ и $v$, соединенные ребром, называются смежными, или соседними. Ребро инцидентно своим концам. Если два ребра имеют общую вершину, то эти ребра будем называть смежными.

Определение 1.3. Окрестностью вершины $v \in V_G$ назовем множество всех ее соседних вершин.

$$N_G(v) = \{ u \in V_G \ | \ uv \in E_G \} (1.3)$$

Определение 1.4. Степенью вершины $v \in V_G$ будем называть количество ее соседей, или размер ее окрестности.

$$d_G(v) = |N_G(v)| (1.4)$$

Определение 1.5. Два графа $G$ и $H$ называются изоморфными ($G~\cong~H$), если существует взаимно однозначное отображение $\alpha: V_G \leftrightarrow V_H$ такое, что

$$uv \in E_G \Leftrightarrow \alpha(u)\alpha(v) \in E_H (1.5)$$

для всех $u, v \in V_G$.

Определение 1.6. Граф $H$ назовем подграфом графа $G$ ($H \subseteq G$), если $V_H \subseteq V_G$ and $E_H \subseteq E_G$.

Определение 1.7. Граф $H \subseteq G$ покрывает $G$ ($H$ является покрывающим подграфом графа $G$), если $V_H = V_G$.

Определение 1.8. Граф $H \subseteq G$ - индуцированный подграф графа $G$ (индуцированный множеством вершин $V_H$), если $E_H = E_G \cap E(V_H)$. Для любого множества $A \subseteq V_G$ индуцированный подграф обозначается

$$G[A] = (A, E_G \cap E(A)). (1.6)$$

Определение 1.9. Пусть $e_i = u_{i}u_{i+1} \in E_G, \ i \in [1, z]$.
Тогда последовательность

$$W = e_{1}e_{2} \dots e_z, \ W : u_1 \stackrel{z}{\rightarrow} u_{z + 1} (1.7)$$

назовем путем длины $z$ из вершины $u_1$ в вершину $u_{z + 1}$.

Определение 1.10. Если существует путь из вершины $u$ в вершину $v$, обозначим расстояние между ними через

$$d_G(u, v) = \min \{ z \ | \ W : u \stackrel{z}{\rightarrow} v \}. (1.8)$$

Если между вершинами $u$ и $v$ нет пути, то положим $d_G(u, v) = \infty$.

Определение 1.11. Граф $G$ называется связным, если

$$\forall u, v \in V_G \Rightarrow d_G(u, v) < \infty. (1.9)$$

Лемма 1.1. Если $\forall v \in V_G \Rightarrow d_G(v) \ge \frac{\nu_G - 1}{2}$, то граф является связным.

Данное свойство графов хорошо известно, и подробно останавливаться на нем нет необходимости.

-- Ср июн 05, 2013 09:12:32 --

Реберные раскраски

Определение 1.12. Назовем $z$-цветной реберной раскраской графа $G$ отображение $\gamma : E_G \rightarrow [1, z]$ ребер данного графа на множество цветов $z$. Будем обозначать через $G^{\gamma}$ тот факт, что граф $G$ имеет реберную раскраску $\gamma$.

В данной статье мы будем использовать реберную раскраску $\gamma : E_G \rightarrow \{ r, b \}$ ($\{ red, blue \}$), где $red$ - первый цвет (\textit{красный}), а $blue$ - второй цвет (\textit{синий}). Далее в статье, если не будет указано обратное, $\gamma$ будет обозначать именно эту раскраску (в два цвета: красный и синий). Также мы будем использовать две монохромные раскраски в каждый из данных цветов (красный и синий): $\rho : E_G \rightarrow \{ r \}, \ \beta : E_G \rightarrow \{ b \}.$ Так $G^{\rho}$ - красный граф, $G^{\beta}$ - синий граф.

Верхним индексом $r$ мы будем обозначать $red$ (красный) цвет, а верхним индексом $b$ - $blue$ (синий) цвет. Верхний индекс $c$ значит любой (какой-либо) цвет.

Для графа $G = G^{\gamma}$ обозначим через $E_G^c$ множество его вершин цвета $c$.
Далее

$$G^c = (V_G, E_G^c), (1.10)$$

$$\varepsilon_G^c = |E_G^c|, (1.11)$$

$$N_G^c(v) = \{ u \in V_G \ | \ uv \in E_G^c \}, (1.12)$$

$$d_G^c(v) = |N_G^c(v)|. (1.13)$$

Очевидно, для графа $G = G^{\gamma}$ выполняются следующие соотношения:

$$\varepsilon_G = \varepsilon_G^r + \varepsilon_G^b, (1.14)$$

$$\forall v \in V_G \Rightarrow \begin{cases} N_G(v) = N_G^r(v) \oplus N_G^b(v),\\ d_G(v) = d_G^r(v) + d_G^b(v). \end{cases} (1.15)$$

NB! Существует разница между обозначениями $G^r$ и $G^{\rho}$ ($G^b$ и $G^{\beta}$). Через $G^r$ мы обозначаем покрывающий подграф графа $G = G^{\gamma}$ который содержит все красные ребра графа $G$, тогда как $G^{\rho}$ -- граф $G$, все ребра которого красные.

Определение 1.13. Два графа с реберной раскраской $G = G^{\gamma}$ и $H = H^{\gamma}$ изоморфны ($G \cong H$) если существует взаимно однозначное отображение $\alpha: V_G \leftrightarrow V_H$, такое что

$$uv \in E_G \Leftrightarrow \begin{cases} \alpha(u)\alpha(v) \in E_H,\\ \gamma(uv) = \gamma(\alpha(u)\alpha(v)) \end{cases} (1.16)$$

для всех $u, v \in V_G$.

Если все ребра какого-либо пути имеют один и тот же цвет, то можно говорить о том, что данный путь имеет этот цвет (монохроматический путь).

Определение 1.14. Если существует путь цвета $c$ из вершины $u$ в вершину $v$, то монохроматическим расстоянием цвета $c$ между вершинами $u$ и $v$ назовем длину кратчайшего пути того же цвета между ними ($d_G^c(u, v)$).

Если между вершинами $u$ и $v$ нет пути цвета $c$, то положим $d_G^c(u, v) = \infty$.

Определение 1.15. Граф $G$ $c$-цветно связен, если

$$\forall u, v \in V_G \Rightarrow d_G^c(u, v) < \infty. (1.17)$$

-- Ср июн 05, 2013 09:13:09 --

Обозначения некоторых графов специального вида

Определение 1.16. Граф $G$ называется полным (обозначается как $K_n$, где $n$ - его порядок), если

$$\forall u, v \in V_G \Rightarrow uv \in E_G. (1.18)$$

Определение 1.17. Пусть $n, z \in \mathbb{N}, \ z < n$, и пусть $1 \le i_1, \dots, i_z \le \left\lfloor \frac{n}{2} \right\rfloor$ - различные натуральные числа. Тогда цикрулярным графом $G = C_n \langle i_1, \dots, i_z \rangle$ назовем граф с набором вершин

$$V_G = \{ v_0, \dots, v_{n - 1} \} (1.19)$$

и набором ребер

$$E_G = \{ v_{\alpha}v_{(\alpha + \beta) \bmod n} \ | \ \alpha = 0, \dots, n - 1 \ and \ \beta = i_1, \dots, i_z \}. (1.20)$$

Определение 1.18. Граф $C_n \langle 1 \rangle = C_n$ назовем циклом.

-- Ср июн 05, 2013 09:13:44 --

Числа Рамсея

Определение 1.19. Числом Рамсея (для случая двухцветной раскраски) $R(m, k)$ называется наименьшее натуральное число $n$ такое, что для любой реберной раскраски $\gamma$ графа $K_n$ выполняется либо $K_m^{\rho} \subseteq K_n^{\gamma}$, либо $K_k^{\beta} \subseteq K_n^{\gamma}$.

Теорема Рамсея показывает, что числа Рамсея $R(m, k)$ существуют для любых натуральных чисел $m$ и $k$. Однако, в настоящее время известно не так много значений чисел Рамсея. Например, все еще не известно точное значение $R(5, 5)$.

Приведем некоторые хорошо известные факты, касающиеся чисел Рамсея:

$$R(m, k) = R(k, m), (1.21)$$

$$R(1, k) = 1, \ R(2, k) = k, (1.22)$$

$$R(m, k) \le R(m - 1, k) + R(m, k - 1). (1.23)$$

-- Ср июн 05, 2013 09:14:16 --

Предрамсеевские графы

Определение 1.19. Предрамсеевским графом для числа Рамсея $R(m, k)$ будем называть такой граф (в совокупности с реберной раскраской) $G = K_n^{\gamma}$ максимального порядка, не содержащий $K_m^{\rho}$ и $K_k^{\beta}$ в качестве подграфов.

Очевидно, если $G$ - предрамсеевский граф для $R(m, k)$, то $\nu_G = R(m, k) - 1$. Возможно, для фиксированного числа Рамсея $R(m, k)$ существует несколько неизоморфных предрамсеевских графов. Обозначим множество попарно неизоморфных предрамсеевских графов для $R(m, k)$ через $\mathfrak{R}(m, k)$.

Лемма 2.1. Если $G \in \mathfrak{R}(m, k)$, то

$$\forall v \in V_G \Rightarrow \begin{cases} d_G^r(v) < R(m - 1, k),\\ d_G^b(v) < R(m, k - 1). \end{cases} (2.1)$$

Без ограничения общности, если $\exists v \in V_G : d_G^r(v) \ge R(m - 1, k)$, тогда $K_{m - 1}^{\rho} \subseteq G[N_G^r(v)]$ или $K_k^{\beta} \subseteq G[N_G^r(v)]$.
Так что $K_m^{\rho} \subseteq G[N_G^r(v) \cup \{ v \} ]$ или $K_k^{\beta} \subseteq G[N_G^r(v)]$. Противоречие. $\blacksquare$

-- Ср июн 05, 2013 09:30:51 --

Предрамсеевские графы для $R(3,3)$

Известно точное значение $R(3, 3)$

$$R(3, 3) = 6, (2.2)$$

так что, если $G \in \mathfrak{R}(3, 3) \Rightarrow \nu_G = 5$.

Лемма 2.2. Если $G \in \rams{3, 3}$, тогда $\forall v \in V_G \Rightarrow d_G^r(v) = d_G^b(v) = 2.$

Из Леммы 2.1

$$\forall v \in V_G \Rightarrow \begin{cases} d_G^r(v) < R(2, 3) = 3,\\ d_G^b(v) < R(3, 2) = 3. \end{cases} (2.3)$$

Также из Формулы 1.15 известно, что

$$d_G^r(v) + d_G^b(v) = d_G(v) = \nu_G - 1 = 4, (2.4)$$

так что

$$d_G^r(v) = d_G^b(v) = 2. (2.5) \ \blacksquare$$

Лемма 2.3. Если $G \in \mathfrak{R}(3, 3)$, тогда $G$ $r$-связен и $b$-связен.

Это следут из Леммы 2.2 и Леммы 1.1. $\blacksquare$

Теорема 2.1.

$$|\mathfrak{R}(3, 3)| = 1. (2.6)$$

Рассмотрим произвольный граф $G \in \mathfrak{R}(3, 3)$. Попытаемся определить его структуру. Из Леммы 2.2 и Леммы 2.3 имеем

$$d_G^r(v) = d_G^b(v) = 2, (2.7) $$

причем граф $r$-связен и $b$-связен. Тогда, красные ребра данного графа образуют красный цикл $C_5^{\rho}$, а синие ребра графа образуют синий цикл $C_5^{\beta}$. То есть существует только один граф из $\mathfrak{R}(3, 3)$, и его структура определена (см. рис. 1). $\blacksquare$


Рис. 1. Предрамсеевский граф для $R(3, 3)$.

Заметим, что красные и синие подграфы графа $G \in \mathfrak{R}(3, 3)$ являются циркулярными (параметры циркулярных графов указаны в соответствии с рис. 1):

$$\begin{cases} G^r = C_5^{\rho} \langle 1 \rangle,\\ G^b = C_5^{\beta} \langle 2 \rangle. \end{cases} (2.8)$$

[r-aax]

Предрамсеевские графы для $R(3, 4)$

Известно точное значение $R(3, 4)$

$$R(3, 4) = 9, (2.9)$$

так что, если $G \in \mathfrak{R}(3, 4) \Rightarrow \nu_G = 8$.

Лемма 2.4. Если $G \in \mathfrak{R}(3, 4)$, тогда

$$\forall v \in V_G \Rightarrow \begin{cases} 2 \le d_G^r(v) \le 3,\\ 4 \le d_G^b(v) \le 5. \end{cases} (2.10)$$

Из Леммы 2.1 имеем

$$\forall v \in V_G \Rightarrow \begin{cases} d_G^r(v) < R(2, 4) = 4,\\ d_G^b(v) < R(3, 3) = 6. \end{cases} (2.11)$$

Также, из Формулы 1.15 получаем

$$d_G^r(v) + d_G^b(v) = d_G(v) = \nu_G - 1 = 7, (2.12)$$

то есть

$$2 \le d_G^r(v) \le 3, \ 4 \le d_G^b(v) \le 5. (2.13) \ \blacksquare$$

Лемма 2.5. Если $G \in \mathfrak{R}(3, 4)$, тогда $G$ $r$-связен и $b$-связен.

Из Леммы 2.4 и Леммы 1.1 следует, что $G$ $b$-связен. Предположим, что $G$ не $r$-связен. Тогда можно выделить две компоненты $H \subseteq G$ и $F \subseteq G$ без красных ребер между ними. Так как для каждой вершины $d_G^r(v) \ge 2$, то количество вершин в каждой компоненте больше $2$. Так как каждая компонента не содержит красных треугольников, то количество вершин в каждой компоненте больше $3$. Так как $\nu_H + \nu_F = 8$, то $\nu_H = \nu_F = 4$. В результате получаем, что $H^r = C_4^{\rho}, \ F^r = C_4^{\rho}$. Очевидно, что такой граф содержит $K_4^{\beta}$ (см. рис. 2). Противоречие. Граф $r$-связен. $\blacksquare$


Рис. 2. $H^r = C_4^{\rho}, \ F^r = C_4^{\rho}$.

Лемма 2.6. Если $G \in \mathfrak{R}(3, 4)$, тогда $\exists v \in V_G \Rightarrow d_G^r(v) = 3$. То есть, в графе найдется вершина с красной степенью, равной $3$.

Допустим, что в графе нет вершины с красной степенью, равной $3$. Тогда, из Леммы 2.4 следует, что красные степени всех вершин равны $2$. Но тогда из $r$-связности графа следует, что $G^r = C_8^{\rho}$, в котором точно найдется $K_4^{\beta}$ в качестве подграфа (см. рис. 3). Противоречие. $\blacksquare$


Рис. 3. Случай, когда красные степени всех вершин равны $2$.

Лемма 2.7. Если $G \in \mathfrak{R}(3, 4)$, тогда $\exists u, v \in V_G \Rightarrow u \ne v, \ uv \in E_G^r, \ d_G^r(u) = d_G^r(v) = 3$. То есть, в графе найдутся две вершины, соединенные красным ребром, красные степени которых равны $3$.

Допустим, утверждение леммы ложно. По Лемме 2.6 найдется вершина $v \in V_G$ с красной степенью, равной $3$. Рассмотрим эту вершину. По предположению леммы, все соседи данной вершины имеют красные степени, равные $2$. Так как в графе нет красных треугольников, то никакие два из этих соседей не соединены красным ребром. Кроме вершины $v$ каждая соседняя с ней вершина соединена красным ребром только с одной вершиной. То есть, в графе $G$ найдется по крайней мере $\nu_G - 1 - 3 - 3 = 1$ вершина, не соединенная красным ребром ни с одним из соседей $v$. Таким образом в графе нашелся подграф $K_4^{\beta}$, вершинами которого являеются соседи вершины $v$ и одна из вершин, не соединенная ни с одной из них красным ребром (см. рис. 4). $\blacksquare$


Рис. 4. Случай, когда нет двух вершин с красной степенью $3$, соединенных красным ребром.

Лемма 2.8. Если $G \in \mathfrak{R}(3, 4)$, тогда в нем найдется красный цикл $C_4^{\rho}$, в котором две соседние вершины имеют красную степень, равную $3$

Рассмотрим произвольный граф $G \in \mathfrak{R}(3, 4)$. Рассмотрим две его вершины с красной степенью, равной $3$, соединенные красным ребром (такие найдутся по Лемме 2.7). Пусть это вершины $v$ и $u$. Кроме друг друга каждая из этих вершин соединена красными ребрами еще с двумя вершинами графа $G$. Пусть $N_G^r(v) = \{ u, a, b \}, \ N_G^r(u) = \{ v, c, d \}$. Ввиду отсутствия в графе $G$ красных треугольников все вершины $a, b, c, d$ различны. Так как вершины $a, b, c, d$ не образуют $K_4^{\beta}$, то среди них найдутся две, соединенные красным ребром. То есть в графе $G$ найдется красный цикл $C_4^{\rho}$ в котором две соседние вершины имеют красную степень $3$ (см. рис. 5). $\blacksquare$


Рис. 5. Красный цикл $C_4^{\rho}$, в котором две соседние вершины имеют красную степень $3$.

Лемма 2.9. Если $G \in \mathfrak{R}(3, 4)$, тогда в нем найдется красный цикл $C_4^{\rho}$, в котором две противоположные вершины имеют красную степень, равную $3$.

Предположим, утверждение леммы ложно. Рассмотрим красный цикл $C_4^{\rho}$, в котором две соседние вершины имеют красную степень, равную $3$ (такая конструкция найдется по Лемме 2.8). Вершины рассматриваемой части графа обозначим $a, b, c, d, e, f$, при этом $a, b, c, d$ образуют цикл, $d_G^r(c) = d_G^r(d) = 3$ (обозначения приведены на рис. 6).


Рис. 6. Поиск красных ребер среди соединяющих вершины $v, a, c, f$.

Рассмотрим вершины $v, a, c, f$, они не образуют $K_4^{\beta}$. Так как граф $G$ не содержит красных треугольников, и $d_G^r(c) = 3$, то среди ребер, соединяющих данные вершины, красными могут быть только $vf$ или $va$. По предположению леммы $\gamma(va) = b$, то есть $\gamma(vf) = r$ (см. рис. 6).

Аналогично, рассматривая вершины $v, b, e, d$, получим $\gamma(ve) = r$. Далее, рассматривая вместо вершины $v$ вершину $u$, получим $\gamma(uf) = \gamma(ue) = r$. Таким образом, имеем красный цикл, образованный вершинами $u, f, v, e$, причем $d_G^r(e) = d_G^r(f) = 3$ (см. рис. 7). Противоречие. $\blacksquare$


Рис. 7. Поиск красного цикла, в котором две противоположные вершины имеют степень, равную $3$.

Лемма 2.10. Если $G \in \mathfrak{R}(3, 4)$, он содержит $C_8^{\rho}$ в качестве подграфа.

Рассмотрим красный цикл $C_4^{\rho}$ в котором две противоположные вершины имеют степень, равную $3$ (такая конструкция найдется по Лемме 2.9). Обозначим вершины, образующие цикл, $a, b, c, d$, пусть $d_G^r(a) = d_G^r(c) = 3$. Обозначим вершины, смежные с вершинами $a$ и $c$ по красным ребрам и не принадлежащие красному циклу $a, b, c, d$ через $e$ и $f$ соответственно. Так как вершины $e, b, f, d$ не образуют $K_4^{\beta}$ и $G$ не содержит красных треугольников, то $\gamma(ef) = r$ (см. рис. 8).


Рис. 8. Поиск красных ребер среди соединяющих вершины $e, b, f, d$.

Далее рассмотрим вершины $g, h$, не отображенные на рис. 8}. Рассмотрим вершины $g, d, b, f$. Так как они не образуют $K_4^{\beta}$, то хотя бы две из них соединены красным ребром. Так как $G$ не содержит красных треугольников, то $\gamma(db) = \gamma(bf) = \gamma(fd) = b$. Следовательно, хотя бы одно одно из ребер $gd, gb, gf$ красное (см. рис. 9).


Рис. 9. Поиск красных ребер среди соединяющих вершины $g, d, b, f$.

Рассуждая аналогично, можно заключить что хотя бы одно из ребер $ge, gb, gd$ красное. Если предположить, что $\gamma(gb) = \gamma(gd) = b$, то получим $\gamma(gf) = \gamma(ge) = r$, то есть будет иметь красный треугольник $g, e, f$. Следовательно, хотя бы одно из ребер $gb, gd$ красное. Без ограничения общности, будем считать, что $\gamma(gd) = r$.

Теперь рассмотрим вместо вершины $g$ вершину $h$. Для нее проведем аналогичные рассуждения, и получим, что хотя бы одно из ребер $hb, hd$ должно быть красным. Однако $\gamma(da) = \gamma(dc) = \gamma(dg) = r$, то есть других красных ребер из вершины $d$ выходить не может. Таким образом, $\gamma(hb) = r$.

Аналогично цвету ребра $ef$ получим, что $\gamma(gh) = r$ (см. рис. 10). Нетрудно видеть, что в нашем графе последовательность вершин $a, e, f, c, d, g, h, b$ образует красный цикл длины $8$. $\blacksquare$


Рис. 10. Красный цикл $C_8^{\rho}$ в графе $G$.

Теорема 2.2.

$$|\mathfrak{R}(3, 4)| = 3. (2.14)$$

Рассмотрим произвольный граф $G \in \mathfrak{R}(3, 4)$. По Лемме 2.10 он содержит красный цикл длины $8$. Обозначим вершины, образующие цикл через $a, b, c, d, e, f, g, h$ в порядке обхода цикла. Так как вершины $a, c, e, g$ не образуют $K_4^{\beta}$, и граф не содержит красных треугольников, то одно из ребер $ae, cg$ должно быть красным. Без ограничения общности, считаем, что $\gamma(ae) = r$. Аналогично, рассматривая вершины $b, d, f, h$, получим, что $\gamma(bf) = r$ (см. рис. 11).


Рис. 11. Красная часть графа $G \in \mathfrak{R}(3, 4)$, для которого $\varepsilon_G^r = 10$

Полученный граф не содержит ни $K_3^{\rho}$, ни $K_4^{\beta}$, то есть является предрамсеевским графом, для которого $\varepsilon_G^r = 10$. Так как все построения выполнялись без ограничения общности, то полученный граф является единственным (с точностью до изоморфизма) предрамсеевским графом c $\varepsilon_G^r = 10$ для числа Рамсея $R(3, 4)$.

Для получения предрамсеевского графа с $\varepsilon_G^r = 11$ нужно покрасить в красный цвет одно из ребер, окрашивание которого не приведет к возникновению красного треугольника. Всего таких ребер $4$: $ch, cg, dh, dg$, - то есть, производя окраску каждого из этих ребер, мы получим $4$ предрамсеевских графа с $\varepsilon_G^r = 11$. Все эти $4$ графа попарно изоморфны.

Без ограничения общности будем считать, что для предрамсеевского графа, для которого выполняется $\varepsilon_G^r = 11$, $\gamma(cg) = r$ (см. рис. 12}).


Рис. 12. Красная часть графа $G \in \mathfrak{R}(3, 4)$, для которого $\varepsilon_G^r = 11$.

Для получения предрамсеевского графа с $\varepsilon_G^r = 12$ нужно покрасить в красный цвет единственное ребро, окрашивание которого не приведет к возникновению красного треугольника. Это ребро $dh$ (см. рис. 13).


Рис. 13. Красная часть графа $G \in \mathfrak{R}(3, 4)$, для которого $\varepsilon_G^r = 12$.

Таким образом, по построению без ограничения общности мы получили $3$ попарно неизоморфных предрамсеевских графа для числа Рамсея $R(3, 4)$. $\blacksquare$\\

Заметим, что для графа $G \in \mathfrak{R}(3, 4)$ верно следующее:

$$10 \le \varepsilon_G^r \le 12, (2.15)$$

$$16 \le \varepsilon_G^b \le 18, (2.16)$$

$$\varepsilon_G^r = \nu_G + \frac{\left| \{ v \ | \ v \in V_G, d_G^r(v) = 3 \} \right|}{2}. (2.17)$$

Отдельно отметим граф $G \in \mathfrak{R}(3, 4)$, для которого значение $\varepsilon_G^r$ максимально ($12$). Его красный и синий подграфы являются циркулярными графами (см. рис. 14}):

$$\begin{cases} G^r = C_8^{\rho} \langle 1, 4 \rangle,\\ G^b = C_8^{\beta} \langle 2, 3 \rangle. \end{cases} (2.18)$$

Рис. 14. Все ребра графа $G \in \mathfrak{R}(3, 4)$, с максимальным значением $\varepsilon_G^r$.

[r-aax]

Предрамсеевские графы для $R(4, 4)$ (часть 1)

Известно точное значение числа Рамсея $R(4, 4)$

$$R(4, 4) = 18, (2.19)$$

то есть, если $G \in \mathfrak{R}(4, 4) \Rightarrow \nu_G = 17$.

Лемма 2.11. Если $G \in \mathfrak{R}(4, 4)$, тогда $\forall v \in V_G \Rightarrow d_G^r(v) = d_G^b(v) = 8$.

По Лемме 2.1

$$\forall v \in V_G \Rightarrow \begin{cases} d_G^r(v) < R(3, 4) = 9,\\ d_G^b(v) < R(4, 3) = 9. \end{cases} (2.10)$$

Также из уравнения 1.15 мы знаем, что

$$d_G^r(v) + d_G^b(v) = d_G(v) = \nu_G - 1 = 16, (2.21)$$

то есть

$$d_G^r(v) = d_G^b(v) = 8. (2.22) \ \blacksquare$$

Лемма 2.12. Если $G \in \mathfrak{R}(4, 4)$, то $\varepsilon_G^r = 68$.

$\varepsilon_G^r = \frac{\nu_G^r \cdot d_G^r}{2} = \frac{17 \cdot 8}{2} = 68$. $\blacksquare$

Лемма 2.13. Если $G \in \mathfrak{R}(4, 4)$, то

$$\forall v \in V_G \Rightarrow \begin{cases} G[N_G^r(v)] \in \mathfrak{R}(3, 4),\\ G[N_G^b(v)] \in \mathfrak{R}(4, 3). \end{cases} (2.23)$$

Рассмотрим произвольную вершину $v \in V_G$. Из Леммы 2.11 имеем $d_G^r(v) = 8$, также окрестность $N_G^r(v)$ не содержит $K_3^{\rho}, K_4^{\beta}$. Это означает, что данная окрестность индуцирует подграф, являющийся предрамсеевским графом для числа Рамсея $R(3, 4)$. Для синей окрестности рассуждения аналогичны. $\blacksquare$

Лемма 2.14. Если $G \in \mathfrak{R}(4, 4)$, то

$$\forall v \in V_G \Rightarrow \begin{cases} G[N_G^r(v)]^r = C_8^{\rho} \langle 1, 4 \rangle,\\ G[N_G^b(v)]^b = C_8^{\beta} \langle 1, 4 \rangle. \end{cases} (2.24)$$

Фиксируем произвольную вершину $v \in V_G$. Обозначим $H = G[N_G^r(v)], \ F = G[N_G^b(v)]$. Рассмотрим красную окрестность вершины $v$. Из Леммы 2.13 и Теоремы 2.2 имеем только три возможные различные структуры для графа $H$.

Рассмотрим вершину $u \in V_H$. Нам известно, что $d_G^r(u) = 8$. Обозначим через $d_{inner}^r(u)$ количество красных соседей вершины $u$ в графе $H$ ($d_{inner}^r(u) = d_H^r(u)$), а через $d_{trans}^r(u)$ - количество остальных красных соседей (кроме вершины $v$). Тогда

$$d_G^r(u) = d_{inner}^r(u) + d_{trans}^r(u) + 1. (2.25)$$

Также пусть $k = | \{ w \ | \ w \in V_H, \ d_H^r(w) = 3 \} |$. Теперь мы можем посчитать количество красных ребер в графе $G$.

$$\varepsilon_G^r = d_G^r(v) + \varepsilon_F^r + \varepsilon_H^r + \sum_{u \in V_H}d_{trans}^r(u). (2.26)$$

Используя Лемму 2.12 и Теорему 2.2, получим

$$68 = 8 + \varepsilon_F^r + (8 + \frac{k}{2}) + (k \cdot 4 + (8 - k) \cdot 5), (2.27)$$

откуда

$$k = 2\varepsilon_F^r - 24. (2.28)$$

Из формулы 2.16 следует, что $\varepsilon_F^r \ge 16$, то есть $k \ge 2 \cdot 16 - 24 = 8$, то есть $k = 8$. Другими словами, $\forall u \in V_H \Rightarrow d_H^r(u) = 3$, или $H^r = C_8^{\rho} \langle 1, 4 \rangle$. Для синей окрестности рассуждения аналогичны (см. рис. 15). $\blacksquare$


Рис. 15. Красная и синяя окрестности вершины в графе $G \in \mathfrak{R}(4, 4)$.

Определение 2.2. Общей окрестностью двух вершин $u, v \in G$ назовем множество их общих соседей. Общая окрестность данного цвета определяется аналогично.

$$\begin{align} N_G(\{u, v\}) = N_G(u) \cap N_G(v),\notag\\ N_G^c(\{u, v\}) = N_G^c(u) \cap N_G^c(v). \end{align} (2.29)$$

Определение 2.3. Общая степень двух вершин $u, v \in G$ это размер их общей окрестности. Общая степень данного цвета определяется аналогично.

$$\begin{align} d_G(\{u, v\}) = |N_G(\{u, v\})|,\notag\\ d_G^c(\{u, v\}) = |N_G^c(\{u, v\})|. \end{align} (2.30)$$

NB! Важно не путать $d_G(u, v)$ - расстояние между вершинами $u$ и $v$ и $d_G(\{u, v\})$ - общую степень двух вершин. Во втором случае $\{u, v\}$ представляет собой множество, состоящее из двух вершин. Общая степень может быть определена для произвольного множества вершин $X$ и обозначена через $d_G(X)$, но в данной статье можно ограничиться общей степенью пары вершин.

Лемма 2.15. Если $G \in \mathfrak{R}(4, 4)$, то

$$\forall u, v \in V_G \Rightarrow d_G^r(\{u, v\}) = \begin{cases} 3, \gamma(uv) = r;\\ 4, \gamma(uv) = b.} \end{cases} (2.31)$$

Выполняется также аналогичное соотношение для синих общий окрестностей.

$$\forall u, v \in V_G \Rightarrow d_G^b(\{u, v\}) = \begin{cases} 3, \gamma(uv) = b;\\ 4, \gamma(uv) = r.} \end{cases} (2.32)$$

Данные формулы означают, что в графе $G$ красные соседи имеют $3$ общих красных соседа и $4$ общих синих соседа, а синие соседи имеют $3$ общих синих соседа и $4$ общих красных соседа.

Зафиксируем произвольную вершину $v \in V_G$. Обозначим $H = G[N_G^r(v)]$, $F = G[N_G^b(v)]$. Если $u \in V_H$, тогда $u$ и $v$ имеют $3$ общих красных соседа, так как в графе $H$ вершина $u$ имеет $3$ красных соседа (см. рис. 16}).


Рис. 16. В графе из $\mathfrak{R}(4, 4)$ красные соседи имеют трех общих красных соседей.

Если $u \in V_F$, тогда $u$ и $v$ имеют $4$ общих красных соседа, так как вершина $u$ имеет $4$ красных соседа в $F$ (выделено на рис. 17}), а значит - и $4$ красных соседа в $H$. Доказательство для синих соседей аналогично. $\blacksquare$


Рис. 17. В графе из $\mathfrak{R}(4, 4)$ синие соседи имеют четырех общих красных соседей.

Далее везде мы будет формулировать утверждения, касающиеся только красных окрестностей. Утверждения, касающиеся синих окрестностей, доказываются аналогично. Также мы будем считать, что $v$ это фиксированная вершина графа $G$. Для этой фиксированной вершины будем без дополнительных упоминаний считать $H = G[N_G^r(v)], \ F = G[N_G^b(v)]$.

Лемма 2.16. Если $G \in \mathfrak{R}(4, 4)$, то

$$\begin{align} \forall u, w \in V_H : \gamma(uw) = r \Rightarrow |N_G^r(\{u, w\}) \cap V_F| = 2,\notag\\ \forall u, w \in V_F : \gamma(uw) = b \Rightarrow |N_G^r(\{u, w\}) \cap V_H| = 2. \end{align} (2.33)$$

Если $u, w \in V_H$, и $\gamma(uw) = r$, тогда $u, w$ имеют трех общих красных соседей в $G$, один из них - $v$ (отмечено на рис. 18}).


Рис. 18. Красные соседи из $H$ имеют двух общих красных соседей в $F$.

Также эти вершины не имеют общих красных соседей в $H$ (иначе это привело бы к красному треугольнику в $H$), то есть они имеют двух общих красных соседей в $F$.

Если $u, w \in V_F$, и $\gamma(uw) = b$, тогда $u, w$ имеют четырех общих красных соседей в $G$ и два из них - в $F$ (отмечено на рис. 19}), то есть другие два - в $H$. $\blacksquare$


Рис. 19. Синие соседи из $F$ имеют двух общих красных соседей в $H$.

Теперь рассмотрим две вершины $u, w \in V_H : \gamma(uw) = r$. Допустим они имеют $2$ общих красных соседей в $F$ (обозначим их $q$ и $t$). Очевидно, $\gamma(qt) = b$. То есть, мы можем говорить о функции $\sigma : E_H^r \rightarrow E_F^b$ (см. рис. 20).


Рис. 20. Функция $\sigma$.

Лемма 2.17. Если $G \in \mathfrak{R}(4, 4)$, то

$$\forall e, f \in E_H^r : e \ne f \Rightarrow \sigma(e) \ne \sigma(f). (2.34)$$

Пусть $\sigma(e) = \sigma(f)$, и $q, t$ - концы данного ребра, $\gamma(qt) = b$. Тогда все концы ребер $e, f$ являются общими красными соседями для $q, t$ (см. рис. 21}).


Рис. 21. Взаимная однозначность отображения $\sigma$.

Но из Леммы 2.16 известно, что $|N_G^r(\{q, t\}) \cap V_H| = 2$. То есть $e = f$. Противоречие. $\blacksquare$

Так как $|E_H^r| = |E_F^b|$, то из Леммы 2.17 следует, что $\sigma$ является взаимно однозначной функцией ($\sigma : E_H^r \leftrightarrow E_F^b$).

Из Леммы 2.14 мы знаем, что $G[N_G^b(v)]^b = C_8^{\beta} \langle 1, 4 \rangle$. Также, очевидно, что $C_8 \langle 1, 4 \rangle \cong C_8 \langle 3, 4 \rangle$. Так что красную и синюю окрестности вершины $v$ можно представить следующим образом (см. рис. 22}):

$$\begin{cases} H^r = C_8^{\rho} \langle 3, 4 \rangle, \ H^b = C_8^{\beta} \langle 1, 2 \rangle,\\ F^r = C_8^{\rho} \langle 1, 2 \rangle, \ F^b = C_8^{\beta} \langle 3, 4 \rangle. \end{cases} (2.35)$$

Рис. 22. Красная и синяя окрестности вершины в графе $G \in \mathfrak{R}(4, 4)$.

Заметим, что мы можем рассматривать граф $C_n \langle m, k \rangle$ как объединение двух других графов ($C_n \langle m \rangle, C_n \langle k \rangle$). Условно данное объединение запишем в следующем виде: $C_n \langle m, k \rangle = C_n \langle m \rangle \cup C_n \langle k \rangle$. Теперь мы можем применить данную формулу к красной части графа $F$:

$$F^r = C_8^{\rho} \langle 1, 2 \rangle = C_8^{\rho} \cup C_8^{\rho} \langle 2 \rangle. (2.36)$$

Теперь мы можем заметить, что $F^r$ состоит из одного длинного цикла (длины $8$) и двух коротких циклов ($C_8 \langle 2 \rangle$ представляет собой два цикла длины $4$). Если какое-то ребро $e \in E_F$ принадлежит циклу $C_8^{\rho} = C_8^{\rho} \langle 1 \rangle$, будем писать $e \in E_F^{r \langle 1 \rangle}$. И если $e \in E_F$ принадлежит одному из циклов $C_8^{\rho} \langle 2 \rangle$, будем писать $e \in E_F^{r \langle 2 \rangle}$. Для синих ребер будем придерживаться аналогичных соглашений.

Лемма 2.18. Если $G \in \mathfrak{R}(4, 4)$, то

$$\begin{align} \forall u, w \in V_F : uw \in E_F^{r \langle 2 \rangle} \Rightarrow |N_G^r(\{u, w\}) \cap V_H| = 2,\notag\\ \forall u, w \in V_H : uw \in E_H^{b \langle 2 \rangle} \Rightarrow |N_G^r(\{u, w\}) \cap V_F| = 2. \end{align} (2.37)$$

Если $u, w \in V_F$ и $uw \in E_F^{r \langle 2 \rangle}$, тогда $u, w$ имеют трех общих красных соседей в $G$. Так как один из этих общих красных соседей находится в $F$ (отмечено на рис. 23}), то остальные два располагаются в $H$.


Рис. 23. Красные соседи из $F$ по ребру из $E_F^{r \langle 2 \rangle}$ имеют двух общих красных соседей в $H$.}

Если $u, w \in V_H$ и $uw \in E_H^{b \langle 2 \rangle}$, тогда $u, w$ имеют четырех общих соседей в $G$. Один из этих общих красных соседей находится в $H$, а второй - это $v$ (отмечено на рис. 24}), то есть остается два общих красных соседа в $F$. $\blacksquare$


Рис. 24. Синие соседи из $H$ по ребру из $E_H^{b \langle 2 \rangle}$ имеют двух общих красных соседей в $F$.

Теперь рассмотрим две вершины $u, w \in V_F : uw \in E_F^{r \langle 2 \rangle}$. Пусть они имеют двух общих красных соседей в $H$ (это вершины $q$ и $t$). Очевидно, что $\gamma(qt) = b$. Так что мы можем говорить о функции $\tau : E_F^{r \langle 2 \rangle} \rightarrow E_H^b$. Сформулируем лемму для ребер из $E_F^{r \langle 1 \rangle}$ и $E_H^{b \langle 1 \rangle}$.

Лемма 2.19. Если $G \in \mathfrak{R}(4, 4)$, тогда

$$\begin{align} \forall u, w \in V_F : uw \in E_F^{r \langle 1 \rangle} \Rightarrow |N_G^r(\{u, w\}) \cap V_H| = 1,\notag\\ \forall u, w \in V_H : uw \in E_H^{b \langle 1 \rangle} \Rightarrow |N_G^r(\{u, w\}) \cap V_F| = 1. \end{align} (2.38)$$

Если $u, w \in V_F$ и $uw \in E_F^{r \langle 1 \rangle}$, тогда $u, w$ имеют трех общих красных соседей в $G$. Так как два из этих общих красных соседей находятся в $F$ (отмечено на рис. 25}), то оставшийся располагается в $H$.


Рис. 25. Красные соседи из $F$ по ребру из $E_F^{r \langle 1 \rangle}$ имеют одного общего красного соседа в $H$.

Если $u, w \in V_H$ и $uw \in E_H^{b \langle 1 \rangle}$, тогда $u, w$ имеют четырех общих красных соседей в $G$. Два из этих общих красных соседей находятся в $H$, а третий - это $v$ (отмечено на рис. 26), таким образом остается один общий красный сосед в $F$. $\blacksquare$


Рис. 26. Синие соседи из $H$ по ребру из $E_H^{r \langle 1 \rangle}$ имеют одного общего красного соседа в $F$.

Лемма 2.20. Если $G \in \mathfrak{R}(4, 4)$, то $\tau$ является функцией из $E_F^{r \langle 2 \rangle}$ в $E_H^{b \langle 2 \rangle}$.

Рассмотрим две вершины $u, w \in V_F : uw \in E_F^{r \langle 2 \rangle}$. Пусть $q, t \in V_H, \ qt = \tau(uw), \ \gamma(qt) = b$. Предположим, что $qt \notin E_H^{b \langle 2 \rangle}$. Тогда из Леммы 2.19 $|N_G^r(q, t) \cap V_F| = 1$, но мы знаем, что $u, w \in V_F$ и $u, w \in N_G^r(q, t)$. Противоречие. $\blacksquare$

Лемма 2.21. Если $G \in \mathfrak{R}(4, 4)$, тогда

$$\forall e, f \in E_F^{r \langle 2 \rangle} : e \ne f \Rightarrow \tau(e) \ne \tau(f). (2.39)$$

Доказательство данной леммы проводится аналогично доказательству Леммы 2.17. $\blacksquare$

Так как $|E_F^{r \langle 2 \rangle}| = |E_H^{b \langle 2 \rangle}|$, то из Леммы 2.21 следует, что $\tau$ является взаимно однозначной функцией ($\tau : E_F^{r \langle 2 \rangle} \leftrightarrow E_H^{b \langle 2 \rangle}$).

Лемма 2.22. Для графа $G \in \mathfrak{R}(4, 4)$ выполняется следующее свойство: если $e, f \in E_F^{r \langle 2 \rangle}$ смежные, то $\tau(e), \tau(f)$ также смежные.

Рассмотрим два смежных ребра $xy, yz \in E_F^{r \langle 2 \rangle}$. Предположим $\tau(xy) = uw, \ \tau(yz) = ps$, и все вершины $u, w, p, s$ из $H$ различны. Также рассмотрим две вершины $t, q \in V_F : xt, ty, yq, qz \in E_F^{r \langle 1 \rangle}$ (см. рис. 27).


Рис. 27. Функция $\tau$ переводит смежные ребра из $E_F^{r \langle 2 \rangle}$ в смежные ребра из $E_H^{b \langle 2 \rangle}$ (построение $1$).

По построению графа $F$ мы знаем, что ребра $xt, ty, yq, qz, xy, tq, yz$ красные, ребра $xz, xq, tz$ синие. Так как $\tau(xy) = uw, \ \tau(yz) = ps$, то ребра $xu, xw, yu, yw, yp, ys, zp, zs$ красные, а ребра $uw, ps$ синие (см. рис. 28}).


Рис. 28. Функция $\tau$ переводит смежные ребра из $E_F^{r \langle 2 \rangle}$ в смежные ребра из $E_H^{b \langle 2 \rangle}$ (построение $2$).

Так как $\gamma(xy) = r$, то $d_G^r(\{x, y\}) = 3$. Мы знаем, что $u, w, t \in N_G^r(\{x, y\})$, то есть $p, s \notin N_G^r(\{x, y\})$. Также, так как ребра $yp, ys$ красные, то ребра $xp, xs$ синие (см. рис. 29}). По аналогии ребра $zu, zw$ синие.


Рис. 29. Функция $\tau$ переводит смежные ребра из $E_F^{r \langle 2 \rangle}$ в смежные ребра из $E_H^{b \langle 2 \rangle}$ (построение $3$).

Только одно ребро в графе $G[ \{ t, x, u, y \} ]$ может быть синим. Это ребро $ut$, следовательно оно синее. По аналогии $\gamma(wt) = b$. Мы получили, что $G[ \{ t, u, w, z\} ] = K_4^{\beta}$ (см. рис. 30). Противоречие. $\blacksquare$


Рис. 30. Функция $\tau$ переводит смежные ребра из $E_F^{r \langle 2 \rangle}$ в смежные ребра из $E_H^{b \langle 2 \rangle}$ (построение $4$).

[r-aax]

Предрамсеевские графы для $R(4, 4)$ (часть 2)

Из Леммы 2.22 получаем, что каждый короткий красный цикл (длины $4$) из $E_F^{r \langle 2 \rangle}$ отображается с помощью функции $\tau$ в короткий синий цикл из $E_H^{b \langle 2 \rangle}$. Теперь мы можем построить промежуточный граф $G$. Обозначим вершины графа $H$ через $u_i$, а вершины графа $F$ через $w_i$ для $i \in [0, 7]$. Расположим вершины $u_i$ и $w_i$ на двух концентрических окружностях, в их общем центре расположим вершину $v$. Вершины $u_i$ расположим на окружности меньшего радиуса так, чтобы они образовывали правильный восьмиугольник. Аналогично, $w_i$ расположим на окружности большего радиуса так, чтобы они образовывали правильный восьмиугольник.

Теперь изобразим все красные ребра графа $H$:

$$E_H^r = \{ u_{i}u_{(i + 1) \bmod 8} \ | \ i \in [0, 7] \} \cup \{ u_{i}u_{i + 4} \ | \ i \in [0, 3] \}. (2.40)$$

Теперь изобразим красные ребра из $E_F^{r \langle 2 \rangle}$:

$$E_F^{r \langle 2 \rangle } = \{ w_{i}w_{(i + 2) \bmod 8} \ | \ i \in [0, 7] \}. (2.41)$$

Далее изобразим все красные ребра между $E_F^{r \langle 2 \rangle}$ и $E_H^{b \langle 2 \rangle }$, которые связаны с функцией $\tau$ (обозначим данные ребра через $E^r(\tau)$):

$$E^r(\tau) = \{ u_{i}w_{i}, u_{i}w_{(i + 2) \bmod 8}, u_{i}w_{(i - 2) \bmod 8} \ | \ i \in [0, 7] \}. (2.42)$$

Итак, на данный момент мы изобразили большую часть красных ребер графа $G$ (см. рис. 31):

$$d^r(v) + |E_H^r| + |E_F^{r \langle 2 \rangle}| + |E^r(\tau)| = 8 + 12 + 8 + 24 = 52. (2.43)$$

Рис. 31. $52$ красных ребра графа из $\mathfrak{R}(4, 4)$.

Нам известно, что $\varepsilon_G^r = 68$, так что $16$ красных ребер все еще не хватает.

Рассмотрим вершину $w_0$. Нам известно, что ребра $w_{0}u_0, w_{0}u_2, w_{0}u_6$ красные. В графе $H$ $G[ \{ u_1, u_4, u_7\} ] = K_3^{\beta}$, так что одно из ребер $w_{0}u_1, w_{0}u_4, w_{0}u_7$ красное (см. рис. 32}).


Рис. 32. Восстановление красных ребер, соединяющих $H$ с $F$ (построение $1$).

Если $\gamma(w_{0}u_4) = r$, то $G[ \{ w_0, w_2, u_0, u_4\} ] = K_4^{\rho}$, так что $\gamma(w_{0}u_4) = b$. Без ограничения общности пусть $\gamma(w_{0}u_1) = r$.

Аналогично, мы можем утверждать, что одно из ребер $w_{2}u_1, w_{2}u_3$ красное. Если $\gamma(w_{2}u_1) = r$, то $G[ \{ w_0, w_2, u_0, u_1\} ] = K_4^{\rho}$ (см. рис. 33), так что $\gamma(w_{2}u_1) =b, \gamma(w_{2}u_3) = r$.


Рис. 33. Восстановление красных ребер, соединяющих $H$ с $F$ (построение $2$).

Таким образом, мы обнаружили, что ребра $\{ w_{i}u_{i + 1} \ | \ i = 0, 2, 4, 6\}$ красные (см. рис. 34).


Рис. 34. Восстановление красных ребер, соединяющих $H$ с $F$ (построение $3$).

По аналогии мы можем сказать, что ребра $\{ w_{i}u_{(i + 1) \bmod 8} \ | \ i = 1, 3, 5, 7 \}$ крансные или ребра $\{ w_{i}u_{i - 1} \ | \ i = 1, 3, 5, 7 \}$ красные. Если ребра $\{ w_{i}u_{i - 1} \ | \ i = 1, 3, 5, 7 \}$ красные, тогда из графа $G[ \{ u_1, w_2, w_5, u_6\} ]$ получим, что $\gamma(w_{2}w_5) = r$, но из графа $G[ \{ u_4, u_3, w_2, w_5\} ]$ видно, что $\gamma(w_{2}w_5) = b$ (см. рис. 35).


Рис. 35. Восстановление красных ребер, соединяющих $H$ с $F$ (построение $4$).

Таким образом, мы пришли к противоречию. То есть, ребра $\{ w_{i}u_{(i + 1) \bmod 8} \ | \ i = 1, 3, 5, 7 \}$ красные, и мы можем объединить данные ребра с теми, для которых уже установлен красный цвет: ребра $\{ w_{i}u_{(i + 1) \bmod 8} \ | \ i \in [0, 7] \}$ красные (см. рис. 36).


Рис. 36. Восстановление красных ребер, соединяющих $H$ с $F$ (построение $5$).

Все ребра графа $G[ \{ w_0, w_1, u_1, u_2\} ]$ кроме ребра $w_{0}w_1$ красные, значит $\gamma(w_{0}w_1) = b$ (см. рис. 37).


Рис. 37. Восстановление красных ребер, соединяющих $H$ с $F$ (построение $6$).

Вообще все ребра $\{ w_{i}w_{(i + 1) \bmod 8}\} \ | \ i \in [0, 7] \}$ синие, а также мы знаем, что ребра $\{ w_{i}w_{i + 4} \ | \ i \in [0, 3] \}$ также синие. То есть остальные ребра графа $F$ красные (см. рис. 38):

$$E_F^r = \{ w_{i}w_{(i + 2) \bmod 8}, w_{i}w_{(i + 3) \bmod 8} \ | \ i \in [0, 7] \}. (2.44)$$

Рис. 38. Восстановление красных ребер, соединяющих $H$ с $F$ (построение $7$).

Таким образом, мы полностью построили граф $G$.

Теорема 2.3.

$$|\mathfrak{R}(4, 4)| = 1. (2.45)$$

Утверждение данной теоремы напрямую следует из построения. Граф $G \in \mathfrak{R}(4, 4)$ однозначно построен без ограничения общности и его структура определена. $\blacksquare$

Рассмотрим граф $G$, для которого выполняются следующие условия:

$$\begin{cases} G^r = C_{17}^{\rho} \langle 1, 2, 4, 8 \rangle,\\ G^b = C_{17}^{\beta} \langle 3, 5, 6, 7 \rangle. \end{cases} (2.46)$$

Красные ребра этого графа изображены на рис. 39, а на рис. 40 представлены и красные, и синие ребра данного графа. Можно заметить, что данный граф не содержит $K_4^{\rho}$ и $K_4^{\beta}$ в качестве подграфов. Таким образом, этот граф принадлежит множеству $\mathfrak{R}(4, 4)$ и, в силу Теоремы 2.3, является единственным.


Рис. 39. Все красные ребра графа из $\mathfrak{R}(4, 4)$


Рис. 40. Все ребра графа из $\mathfrak{R}(4, 4)$

Заключение

Подводя итог, можно заметить, что для чисел Рамсея $R(3, 3)$, $R(3, 4)$, $R(4, 4)$ существует только по одному предрамсеевскому графу с максимальным показателем $\varepsilon_G^r$. Более того, каждый такой предрамсеевский граф является циркулярным, что оставляет надежду найти подобные высокоорганизованные структуры и в множествах предрамсеевских графов для чисел Рамсея более высокого порядка:

$$G \in \mathfrak{R}(3, 3) \Rightarrow \begin{cases} G^r = C_5^{\rho} \langle 1 \rangle,\\ G^b = C_5^{\beta} \langle 2 \rangle. \end{cases} (3.1)$$

$$G \in \{ \mathfrak{R}(3, 4) \ | \ \max{\varepsilon_G^r} \} \Rightarrow \begin{cases} G^r = C_8^{\rho} \langle 1, 4 \rangle,\\ G^b = C_8^{\beta} \langle 2, 3 \rangle. \end{cases} (3.2)$$

$$G \in \mathfrak{R}(4, 4) \Rightarrow \begin{cases} G^r = C_{17}^{\rho} \langle 1, 2, 4, 8 \rangle,\\ G^b = C_{17}^{\beta} \langle 3, 5, 6, 7 \rangle. \end{cases} (3.3)$$