Gráfelmélet. Igaz-e, hogy G vagy a komplementere biztosan összefüggő?

Igen.

Ha a G gráf nem összefüggő, akkor vegyük az egyik összefüggő komponensét, mindegy, melyiket. Ennek a pontjai az A ponthalmaz. Az összes többi pontot nevezzük B halmaznak. (B-ben több komponens is lehet, nem baj.) E két halmaznak az uniója kiadja a gráf összes pontját.

A és B pontjai között nem megy él, ez tiszta, hisz A-ból "kifelé" nem megy egy él sem. Egyik A beli pontból sem megy egyik B belibe sem. (Persze ezek nem irányított élek, csak egyszerűbb olyan szóhasználattal fogalmazni.)

Ez azt jelenti, hogy a komplementer gráfban benne kell legyen minden egyes A beli pontból minden egyes B belibe menő él. (Lehet még a komplementerben több él is, nem baj.) A komplementernek ezt a részhalmazát (ami az A és B közötti éleket tartalmazza) nevezzük K gráfnak.

Na most nézzük az egyik A beli pontot: p∈A. Ebből megy a K gráfban él mindegyik B beli pontba, azok mindegyikéből viszont mindegyik A belibe is. Vagyis p össze van kötve mindegyik B beli, és max 2 hosszú úton mindegyik A beli ponttal is. Ami azt jelenti, hogy a K gráf összefüggő.

K-ban benne van az összes pont, tehát G komplementere csak további éleket tartalmazhat K élein kívül még, de attól az csak még inkább összefüggő lesz (vagyis némelyik út rövidebb lehet).