78
правок
Изменения
→Базовые определения: пояснение к оказательству леммы, цифры в tex
Для удобства примем <tex>E = E(V_1, V_2)</tex>.
<tex>\Rightarrow</tex>. Пусть <tex>E</tex> {{---}} бонд. Докажем, что для любого ребра <tex>e \in E</tex> граф <tex>G - E + e</tex> связен. Действительно, пусть этот граф несвязен и имеет, скажем, компоненты связности <tex>U_1</tex> и <tex>U_2</tex>. Тогда <tex>E \supsetneq E(U_1, U_2)</tex>, а из связности графа <tex>G</tex> следует, что <tex>E(U_1, U_2) \neq \varnothing</tex>. Противоречие с минимальностью <tex>E</tex>.
Так как для любого ребра <tex>e \in E = E(V_1, V_2)</tex> граф <tex>G − E + e</tex> связен,
оба графа <tex>G(V_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> этот разрез непуст, то есть, является бондом.
