Matematické Fórum

Mauz · 28. 01. 2016 20:54

Pro která n existuje graf s n vrcholy, jejichž stupně jsou navzájem různé?
[určitě pro n=1; poté už pro žádný konečný graf, na nekonečné grafy se podle mého otázka nevztahuje; jaké je však odůvodnění?]

Díky

check_drummer · 29. 01. 2016 00:04

↑ Mauz:
Ahoj, zkus porovnat vrcholy s nejmenším a největším stupněm...

Mauz · 29. 01. 2016 15:21

No jasně,

pro libovolné n vrcholů, pokud neuvažujeme smyčky, musí mít každý vrchol stupeň z množiny {0,1,..,n-1}, tak že má každý jiný prvek, což vede ke sporu, protože vrchol se stupněm (n-1) musí být spojen s dalšími (n-1) vrcholy hranou, což je ve sporu s faktem, že graf obsahuje vrchol stupně 0 (takže není s žádným jiným spojený hranou).

Díky

Matematické Fórum

#1 28. 01. 2016 20:54

Vzajemne ruzne stupne vrcholu grafu

#2 29. 01. 2016 00:04

Re: Vzajemne ruzne stupne vrcholu grafu

#3 29. 01. 2016 15:21

Re: Vzajemne ruzne stupne vrcholu grafu

Zápatí