---
# System prepended metadata

title: Domácí úkol 5.4 - party

---

# Domácí úkol 5.4 - party
Pokud si potřesení rukami znázorníme grafem, pak ze zadání by měly všechny vrcholy (kromě pana Nováka) mít různý stupeň. Jelikož nejvyšším stupněm může být $6$* (na párty je $8$* lidí a nikdo nezdravil sebe ani partnera), pak nejnižším stupněm bude $0$* .
Jak bude tento graf vypadat? Označme vrcholy $0-6$* (podle stupňů) a $N$ (jako pan Novák). Spojíme-li pak $6$* se všemi vrcholy kromě $0$, pak vrchol $1$ již bude "nasycený", takže vrchol $5$* bude spojen se všemi kromě jedničky, atd. Vrcholy s čísly nejvýše $3$* pak nebudou již spojeny s vrcholem $N$.
Z toho vyplývá, že $6$* musí být partnerem $0$ (jelikož se nezdravili), takže $5$* musí být partnerem $1$ (nula je již zabrána) atd., takže $N$ je partnerem $3$* . Paní Nováková, stejně jako pan Novák, se tedy zdravila se třemi lidmi.
## Obecně (označeno hvězdičkou):
$8 = 2n$
$6 = 2n-2$
$5 = 2n-3$, 
$3 = (2n-2)/2 = n-1$
