Изменения

'''Минимальный (по включению)''' (англ. ''minimal by inclusion'') разрез графа <tex>G</tex> {{- --}} разрез, из которого нельзя выделить разрезы с меньшим количеством ребер.

Так как для любого ребра Теперь докажем, что подграфы <tex>e G(V_1) \in E = Etext{ и } G(V_1, V_2)</tex> граф связны. Рассмотрим отдельно подграф <tex>G − E + e(V_1)</tex> связен,оба графа если он не связный, то имеет как минимум <tex>G(V_1)2</tex> и компоненты связности, назовем их <tex>G(V_2)O_1 \text{ и } O_2</tex> связны, потому что если они не связны, то в каждом есть несколько компонент связности, а возвращая ребро из бонда мы не соединяем эти компоненты, однако целый граф оказывается связным, значит каждый подграф состоит из одной компоненты связности.

<tex>e \in E </tex> можно также представить как <tex>e = (u, v) \text{ при этом } u \in G(V_1), v \in G(V_2)</tex>, то есть <tex>u \in O_1 \mid u \in O_2</tex>, и граф <tex> G - E + e </tex> состоит из <tex>2</tex> компонент {{---}} <tex>(O_1 \cup G(V_2), O_2) \mid (O_2 \cup G(V_2), O_1)</tex>, что противоречит условию связности. Так же доказывается связность <tex>G(V_2)</tex>. <tex>\Leftarrow</tex>. Если оба графа <tex>G(V_1)</tex> и <tex>G(V_2)</tex> — связны, то добавление любого ребра из <tex>E</tex> даст нам связный подграф графа <tex>G</tex>, содержащий все его вершины. Значит, в этом случае разрез <tex>E</tex> минимален по включению. В силу связности <tex>G</tex> этот разрез непуст, то есть, является бондом.

Подграфы <tex>V_1</tex> и <tex>V_2</tex> из предыдущей леммы называются '''торцевыми графами'''(англ. ''end graph'').

Также стоит отметить, что если граф <tex> G </tex> несвязен, то его '''бонд''' определим как бонд какой-либо его компоненты, а всякий перешеек [[Мост,_эквивалентные_определения | мост]] графа образует однореберный бонд. Торцевые графы перешейка моста являются торцевыми графами соответствующего бонда.

Посчитаем <tex> \sum\limits_{n=1}^{\infty} n f_n^{X} </tex>, то есть количество всех исходящих ребер из <tex>X</tex>. По [[Лемма_о_рукопожатиях | лемме о рукопожатиях]] внутри ребер, с обоих сторон прикрепленных к <tex>X</tex> их , будет <tex>2|E(X)|</tex>. Количество ребер, но мы не посчитали ребра прикрепленные прикрепленных и к <tex>X</tex>, и к <tex>Y</tex>. Количество таких ребер, по определению бонда {{---}} количество ребер в бонде <tex>H</tex>, то есть <tex>|E(H)|</tex>. Отсюда:

Аналогичную формулу получаем Полученная формула в правой части не зависит от подграфа, поэтому вычитая вариант для графа <tex> Y </tex>. Вычитая ее из <tex>\textbf{(4)}</tex>, приходим к <tex>\textbf{(1)}</tex>.

[[Файл: Новый гамильтонов_бонд.png|350px|thumb|Рис. 1]]* Сам Гринберг использовал свою теорему для того, чтобы искать негамильтоновы кубические(все вершины имеют степень <tex>3</tex>) полиэдральные графы<ref>[https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%BB%D0%B8%D1%8D%D0%B4%D1%80%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B9_%D0%B3%D1%80%D0%B0%D1%84 полиэдральные графыВикипедия {{---}} Полиэдральный граф] </ref> с высокой циклической реберной связностью.* Теорема Гринберга Циклическая рёберная связность графа {{---}} необходимое условие для планарного графаэто наименьшее число рёбер, которое можно удалить так, чтобы оставшийся граф содержал гамильтонов цикл, основанное на длинах циклов гранейболее чем одну циклическую компоненту.* Теорема Гринберга используется также для поиска планарных гипогамильтоноввых графов путём построения графа, в котором все грани имеют число рёберНапример он нашел граф с <tex>46</tex> вершинами, сравнимых с <tex>225</tex> по модулю гранями и циклической рёберной связностью пять, показанный на рисунке <tex>31</tex>. {|align="center" |[[Файл: Гамильтонов граф.png|300px|center|thumb|Рис. 1]] |[[Файл: Новый гамильтонов_бонд.png|500x300px|thumb|Рис. 2]] |} * Теорему Гринберга можно иногда использовать для доказательства отсутствия гамильтонова бонда в графе. Пусть, например, все вершины связного графа <tex> G </tex>, кроме одной, имеют степени, сравнимые с <tex>2</tex> по модулю <tex>3</tex>. Тогда левая часть формулы <tex>\textbf{(1)}</tex> не делится на <tex>3</tex> и, следовательно, гамильтонова бонда в графе <tex> G </tex> не существует. Рисунок <tex>12</tex> иллюстрирует этот простой пример.* Чтобы планарный граф существовал и содержал гамильтонов цикл, необходимо выполнение теоремы Гринберга.<ref>Grinberg, È. Ja. (1968), "Plane homogeneous graphs of degree three without Hamiltonian circuits", Latvian Math. Yearbook 4 (in Russian), Riga: Izdat. “Zinatne”, pp. 51–58, MR 0238732. English translation by Dainis Zeps, [https://arxiv.org/abs/0908.2563v1 arXiv:0908.2563.]</ref>* Теорема Гринберга используется также для поиска планарных гипогамильтоновых графов<ref>[https://ru.wikipedia.org/wiki/%D0%93%D0%B8%D0%BF%D0%BE%D0%B3%D0%B0%D0%BC%D0%B8%D0%BB%D1%8C%D1%82%D0%BE%D0%BD%D0%BE%D0%B2_%D0%B3%D1%80%D0%B0%D1%84 Википедия {{---}} Гипогамильтонов граф]</ref> путём построения графа, в котором все грани имеют число рёбер, сравнимых с <tex>2</tex> по модулю <tex>3</tex>.