---
# System prepended metadata

title: Domácí úkol 7.1 - ndoplnek

---

# Domácí úkol 7.1 - ndoplnek
a) Obsahuje-li $G$ úplný bipartitní graf, pak obsahuje všechny hrany vedoucí z partity $A$ do partity $B$; jeho doplněk $G_0$ žádnou z těchto hran obsahovat nebude, a tak nebude existovat cesta $v_1v_2;(v_1\in A, v_2 \in B)$, jelikož z vrcholu $v_2$ existuje cesta pouze do jiných vrcholů z partity $B$.
b) Neobsahuje-li $G$ úplný bipartitní graf, pak musí existovat situace, kdy alespoň jeden vrchol (označme $v_1$) není spojen se všemi (pokud ano, mohl by tvořit samostatnou partitu). Stejně tak ty vrcholy, se kterými není přímo spojen (označme jeden z nich jako $v_2$) nemohou být spojeny se všemi vrcholy (s výjimkou $v_1$), takže vrchol, se kterým není $v_2$ spojen, označíme jako $v_3$. Tím jsme našli trojici vrcholů, které jsou spojeny nejvýše jednou hranou, v doplňku tak budou každé tři vrcholy spojeny alespoň dvěma hranami a $G_0$ bude souvislý. 