Keresés

Keresendő kifejezés:

Toplista

Toplista
  • betöltés...

Segítség!

Ahhoz, hogy mások kérdéseit és válaszait megtekinthesd, nem kell beregisztrálnod, azonban saját kérdés kiírásához ez szükséges!

Ebben tudna valaki segíteni?

48
Bizonyítsuk be, hogy egy legalább 2 pontú egyszerű gráfban mindig található két olyan pont, amelyek fokszáma ugyanannyi.
Igaz marad-e az állítás, ha nem egyszerű gráfokat is tekintünk?
Jelenleg 1 felhasználó nézi ezt a kérdést.
0
Középiskola / Matematika

Válaszok

1
Egy csúcsból (egyszerű gráf esetén) n elemű halmaznál n-1 élt húzhatunk be,

Ha felsorolunk n db számot 1 és n-1 között, akkor biztosan lesz két egyező szám.

Nem egyszerű gráf esetén nem igaz (ábra, fokszámok feltüntetve).
1