Ha G összefüggő, akkor ez igaz. Ha nem összefüggő, akkor van néhány komponense, amik között nem fut él. G komplementerében ezek között a komponensek között minden él be lesz húzva. Tehát ha két olyan csúcsot veszünk, amik eredetileg nem egy komponensben voltak, most össze lesznek kötve. Ha két olyan csúcsot veszünk, amik eredetileg egy komponensben voltak, akkor az egyikből a komplementerben el tudunk menni egy másik komponens egy csúcsába és onnan vissza a másik ponthoz, hiszen minden eredetileg nem egy komponensben lévő csúcs között most fut él. Tehát ekkor G komplementere összefüggő.