Theorem - Havel-Hakimi-Theorem

• Konstrukte:
  • Havel-Hakimi-Algorithmus
• Involvierte Definitionen:
  • Folge
  • monoton fallend
  • Valenzsequenz
• Veranstaltung: AlMa
• Referenz: @felsner2013

⠀

Theorem: Havel-Hakimi-Theorem

Sei eine monoton fallende Folge.

Dann ist genau dann Valenzsequenz eines Graphen, wenn die Folge

eine Valenzsequenz ist.