Matematické Fórum
Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
#1 03. 02. 2022 01:16
Teorie grafů
Dobrý den, potřeboval bych pomoct s následujícím důkazem:
Dokažte, že jestli graf G neobsahuje K3 jako podgraf, tak platí |V(G)| ≥ δ(G) + Δ(G).
K3 ... je kompletní graf o třech vrcholech
|V(G)| ... je počet vrcholů grafu G
δ(G) ... je minimální stupeň grafu G
Δ(G) ... je maximální stupeň grafu G
Offline
#2 03. 02. 2022 12:11
Re: Teorie grafů
Já bych začal úvahou nad vrcholem který má maximální stupeň, a našel si všechny jeho "sousedy" ... kolik jich je?
Pak si vzal libovolného jeho "souseda" a k němu si našel všechny jeho "sousedy". Kolik jich je? Kolik z nich sousedí i s prvním zkoumaným vrcholem?
pak už bys to měl vidět.
Jen upozorňuju, že aby to bylo korektní tak je potřeba projít hraniční situace (tedy že Δ(G) je 0 nebo 1), to by ale neměl být problém.
Dva jsou tisíckrát jeden.
Offline