Santa Claus — 2021-11-20 22:16 (410 days ago) — edit — reply
1\. Graf bude souvislý, protože mezi každými dvěma vrcholy bude existovat cesta:
Pokud tyto vrcholy byly v různých komponentech souvislosti, musí mezi nimi existovat v doplňku hrana, protože v původním grafu mezi nimi nebyla.
Pokud dva vrcholy byly ve stejném komponentu souvislosti, musí mezi nimi existovat cesta délky dva, a to taková, která vede přes jeden jakýkoliv vrchol jakéhokoliv jiného komponentu souvislosti. Protože jsou v nesouvislém grafu alespoň dva komponenty souvislosti, tato cesta existuje.
2\. Obráceně to platit nemusí, protipříklad:
$\text{Graf G: } V(G) = \{A,B,C,D\}$
$E(G) = \{\{A,B\}, \{B,C\}, \{C,D\}\}$
Jedná se o graf souvislý, je to cesta na čtyřech vrcholech.
Jeho doplněk bude mít hrany:
$E(\overline{G}) = \{\{A,C\},\{A,D\} \{B,D\}\}$
Doplňek je taky souvislý: Cesty vedou mezi A a C, A a D a D a B, tranzitivitou lze potom najít cesty mezi zbylými dvojicemi vrcholů:
A→B je jako A→D a D→B
B→C je jako C→A, A→D, D→B
C→D je jako C→A a A→D