Dowód grafy 2

[matinf]

Udowodnić, że przynajmniej jeden z grafów G, lub jego dopełnienie jest spójny.


Jeśli G jest spójny to teza jest jasna.

Jeśli G nie jest spójny to rozważamy jego dopełnienie G'.

Obecnie w grafie G mamy "wyspy", tzn co najmniej dwa spójne kawałki. Pomiędzy wyspami oczywiście nie ma krawędzi.

Spróbuję pokazać, że dopełnienie jest już spójne.

Po pierwsze: W wyniku dopełnienia żadna ze spójnych nie zostanie rozspójniona:
Dlaczego ?
Rozważmy dwa dowolne wierzchołki \(\displaystyle{ u}\) i \(\displaystyle{ v}\)
Niech one należą do tej samej spójnej składowej. Wówczas w wyniku dopełnienia przestają być połączone w obrębie swojej wyspy. Nie mniej jednak rozważmy wierzchołek \(\displaystyle{ w}\) pochodzący z dowolnej innej wyspy.
Wówczas obydwa wierzchołki zostaną z nim połączone, a więc spójność wierzchołków pochodzących z tej samej wyspy zostaje zachowana.
Oczywiście połączone zostaną również wysp - dlaczego ?
No, jasne - nie było krawędzi - w dopełnieniu są krawędzie - tak będzie pomiędzy KAŻDĄ parą wysp.

A więc to również działa.


Jaki ten dowód ?

[Kartezjusz]

Tak, tylko to działa dla grafów skończonych.
Rozważmy graf o wierzchołkach ze zbioru \(\displaystyle{ \mathbb{Q} ^{2}}\)zawarty w \(\displaystyle{ \mathbb{R} ^{2}}\) stopnia zerowego. czy dopełnienie będzie spójne?

[matinf]

Innych grafów nie zakładam. Ale chętnie bym zrozumiał co masz na ten temat do powiedzenia.

[Kartezjusz]

By to zrozumieć przypomnij sobie definicję grafu.1. To pozwoli grafy stawiać wszędzie
Co wiesz z topologii o zbiorze\(\displaystyle{ \mathbb{Q} ^{2}}\) ?