Weboldalunk cookie-kat használhat, hogy megjegyezze a belépési adatokat, egyedi beállításokat, továbbá statisztikai célokra és hogy a személyes érdeklődéshez igazítsa hirdetéseit. További információ
Kezdőoldal » Közoktatás, tanfolyamok » Házifeladat kérdések » Bizonyítsuk be, hogy minden 6...

Bizonyítsuk be, hogy minden 6 pontú egyszerű gráfban van két azonos fokszámú pont!?

Figyelt kérdés

2016. máj. 9. 20:17
 1/3 anonim ***** válasza:

Egy hatpontú egyszerű gráfban a legmagasabb fokszám maximum 5 lehet. 0-tól 5-ig pontosan 6 db egész szám van, ezért csak úgy lehetséges, hogy a gráf minden pontjának más legyen a fokszáma, ha van olyan pont, aminek 0 a fokszáma, és van olyan is, aminek 5. Ez viszont nem lehetséges, hiszen ha egy pontnak 5 a fokszáma, akkor onnan az összes többi pontba megy él, vagyis semelyik pontnak se lehet 0 a fokszáma.


Ugyanez a bizonyítás működik tetszőlegesen sok pontú eyyszerű gráfokra is.

2016. máj. 9. 20:41
Hasznos számodra ez a válasz?
 2/3 anonim ***** válasza:
Ha a fokszámok 0,1,2,3,4,5 akkor a fokszámok összege 15 de ugyanakkor a fokszámok összege az élek számának duplája és a 15 nem páros szám. Ez nem működik minden N-re az elsővel ellentétben (csak azokra amik 4-gyel osztva 2 v 3 maradékot adnak).
2016. máj. 10. 15:44
Hasznos számodra ez a válasz?
 3/3 anonim ***** válasza:
Első vagyok, javítom magam: csak a legalább kétpontú egyszerű gráfokra.
2016. máj. 10. 15:58
Hasznos számodra ez a válasz?

Kapcsolódó kérdések:





Minden jog fenntartva © 2020, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | WebMinute Kft. | Facebook | Kapcsolat: info@gyakorikerdesek.hu

A weboldalon megjelenő anyagok nem minősülnek szerkesztői tartalomnak, előzetes ellenőrzésen nem esnek át, az üzemeltető véleményét nem tükrözik.
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!