Tételek gráfokra

  • Minden legalább két csúccsal rendelkező egyszerű gráfban van két azonos fokszámú csúcs.
  • A pontok fokszámainak összege az élek számának kétszerese, ezáltal páros szám. Bizonyítható, mert minden él pontosan két végpontjával meghatározható. Az előbbiek miatt a páratlan fokú tagok száma mindenképpen páros.
  • Egy n pontú teljes gráf éleinek száma n*(n-1)/2.
  • Ebből n*(n-1) a fokszámok összege.
  • Bármely n csúcsú fának n-1 éle van.
  • A fa bármelyik két csúcsa közt pontosan egy út vehető fel.
  • Zárt Euler-vonalat akkor és csak akkor tartalmazhat az összefüggő gráf, ha minden foka páros.
  • Nyílt Euler-vonalat akkor és csak akkor tartalmazhat az összefüggő gráf, ha pontosan kettő páratlan fokú csúcsa van.

Vélemény, hozzászólás?

Az email címet nem tesszük közzé. A kötelező mezőket * karakterrel jelöljük.