---
# System prepended metadata

title: Domácí úkol 7.3 - isvc

---

# Domácí úkol 7.3 - isvc
Ke každému vrcholu z $C$ si lze představit jak reálnou, tak fiktivní hranu z $E$, množinu takových hran označme jako $F$. Přitom reálnou hranou rozumějme hranu $uv$ tak, že $u \land v\in C$, a fiktivní tak, že $u \veebar v \in C$. Důsledkem toho platí, že $F = E$.
Zjistěme, které vrcholy leží ve $V$ a neleží v $C$, podobně tak s hranami:
$\{V,E\}-\{C,F\}=\{U,\emptyset\}$. Dostali jsme množinu vrcholů a prázdnou množinu hran. Vznikl nám tak graf bez hran, což znamená, že $U$ je nezávislá množina.
Pokud by $C$ nebylo vrcholové pokrytí (implikace nepravda $\Rightarrow$ nepravda), pak by některá z hran neležela v množině $F$, a rozdíl $E-F$ by tak nebyl prázdnou množinou; některé vrcholy z $U$ by tak byly spojeny hranou a nemohlo by se jednat o nezávislou množinu.