Proposition - T ist ein Baum genau dann wenn T kreisfrei ist und das Hinzufügen einer beliebigen Kante zu einem Kreis führt

• Involvierte Definitionen:
  • Baum
  • Kreisfreiheit eines Graphen
  • Kantenmenge
  • Knotenmenge
• Veranstaltung: AlMa
• Referenz: @herzogWiSe22

⠀

Proposition: Charakterisierung per Kreisfreiheit und Zerstörung dieser

Sei ein Graph.

Es gilt:
ist ein Baum ist kreisfrei und das Hinzufügen einer beliebigen Kante führt zu einem Kreis (zerstört die Kreisfreiheit).