Dodana krawędź

[mol_ksiazkowy]

Niech \(\displaystyle{ G}\) będzie grafem, w którym jedynie wierzchołki \(\displaystyle{ u, v}\) mają stopień nieparzysty. \(\displaystyle{ G^{\prime} }\) to graf \(\displaystyle{ G}\), z dodaną krawędzią \(\displaystyle{ uv}\). Udowodnić, że jeśli \(\displaystyle{ G^{\prime}}\) jest spójny to \(\displaystyle{ G}\) także.

[arek1357]

Zakładając, że graf \(\displaystyle{ G}\) jest niespójny nie możemy od niego żądać aby jego spójna składowa nie zawierała punktów \(\displaystyle{ p \wedge q}\) bo wtedy równierz \(\displaystyle{ G'}\) byłby niespójny.
Jeżeli natomiast punkty \(\displaystyle{ p \wedge q}\) znajdą się w osobnych spójnych składowych to też sprzeczność bo w takiej składowej istniałby tylko
jeden wierzchołek o stopniu nieparzystym to sprzeczność ze względu na:

\(\displaystyle{ \sum_{}^{} p_{i}=2E}\) lewa strona byłaby liczbą nieparzystą bo tylko jeden wierzchołek byłby nieparzysty, a więc \(\displaystyle{ p, q}\) muszą być w jednej składowej spójnej...

NNo tako to jako...