---
# System prepended metadata

title: Domácí úkol 5.1 - doplnek

---

# Domácí úkol 5.1 - doplnek
1) Je-li graf nesouvislý, pak je rozdělen na několik souvislých částí. Ke každým dvěma spojeným vrcholům pak můžeme najít alespoň jeden třetí vrchol, který není spojený ani s jedním (vždy bude v druhé souvislé části) - v doplňku pak dané dva vrcholy nebudou spojené přímo, ale bude mezi nimi existovat cesta právě přes tento třetí vrchol.

2) Implikace v prvním důkazu nevylučuje obrácený případ - tedy může existovat souvislý graf, kde ke každým dvěma spojeným vrcholům existuje třetí nespojený, a tak doplněk grafu bude opět souvislý graf (např. cesta).