Zum Inhalt springen

Graph/Paarung/Größte/Charakterisierung/Aufgabe

Aus Wikiversity

Zeige, dass für einen Graphen  G=(V,E)  folgende Eigenschaften äquivalent sind.

  1. Es gibt unter allen (durch Inklusion geordneten) Paarungen eine größte Paarung.
  2. G ist selbst eine Paarung
  3. Alle Wege in G haben die Länge 0 oder 1.
  4. Die Zusammenhangskomponenten sind (leer oder) ein- oder zweielementig.