Santa Claus — 2021-11-29 13:35 (402 days ago) — edit — reply
$\implies$
Graf je nesouvislý $\implies$
Graf obsahuje alespoň dvě komponenty souvislosti.
Komponenty souvislostí můžeme rozdělit do dvou neprázdných množin $A, B$ $\implies$
$\forall a \in A, b \in B:( a, b$ jsou z jiných komponent souvislosti $\implies$ není cesta mezi $ab \implies ab \notin E(G))$ $\implies$
$\forall a \in A, b \in B: ab \in E(H)$ $\implies$
$A, B$ tvoří partity úplného bipartitního podgrafu grafu $H$.
$\impliedby$
Graf obsahuje úplný bipartitní podgraf $\implies$
Vrcholy grafu lze rozdělit do dvou neprázdných množin $X, Y$ (parity), t. ž. $\forall x \in X, y \in Y: xy \in E(G)$ $\implies$
$\forall x \in X, y \in Y: xy \notin E(H)$ $\underset{sporem}{\implies}$
$\forall x \in X, y \in Y:$ mezi $x, y$ nevede cesta. $\implies$
$X, Y$ jsou komponentami souvislosti v nesouvislém grafu.
Pomocný důkaz toho, že když mezi žádnými dvěma vrcholy $x \in X,y \in Y,$ není hrana, kde $X \cup Y =V$ v grafu $G(V, E)$, nevede mezi žádnými dvěma vrcholy $x \in X,y \in Y$ cesta.
Sporem: Kdyby mezi $x,y$ vedla cesta, byla by ve tvaru $x, e_1, v_1, e_2, ..., y$. Alespoň jedna z hran by musela být mezi vrcholy z množiny $X$ a $Y$, jinak by každá hrana vedla do vrcholu z $X$ a cesta by nikdy nemohla skončit v $y$. To je ale spor, protože mezi žádnými dvěma vrcholy z $X$ a $Y$ cesta nevede.