Kezdőoldal » Közoktatás, tanfolyamok » Házifeladat kérdések » Hogyan mutassam meg, hogy ha...

Hogyan mutassam meg, hogy ha egy gráf minden pontja legalább másodfokú, akkor a gráfban van kör?

Figyelt kérdés

2014. febr. 15. 17:55
 1/1 anonim ***** válasza:
Nagyon egyszerű: tudjuk, hogy ha egy n csúcs gráfban nincs kör, akkor annak legfeljebb n-1 éle lehet. Minen csúcs foka legalább 2, akkor a fokszám összeg legalább 2n, és tudjuk, hogy a fokszámösszeg fele az élszám, tehát legalább n éle van. Mivel az n-1<n, és a körmentes gráfnak legfeljebb n-1 éle lehet, ezért biztosan lesz benne kör.
2014. febr. 15. 18:00
Hasznos számodra ez a válasz?

Kapcsolódó kérdések:





Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)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!