Category:

Sei G = (V, E) ein Baum mit |V | ≥ 2. Dann enth¨alt G mindestens zwei Bl¨atter.

Für n ∈ N sei En = {[n], ∅}, d.h ein Graph ganz ohne Kanten.

benachbart / adjazent

die Gradfolge

leer

eine Folge von Knoten (v0, · · · , vk) (nicht notwendigerweise paarweise verschieden), so dass {vi−1, vi} ∈ E für alle i ∈ [k] gilt. auch im Fall k = 0…

Ein Kantenzug darf Knoten mehrfach benutzen, ein Weg nicht Ein Weg ist ein Subgraph, ein Kantenzug nur eine Knotenfolge

Blatt (Blätter)

Es sei G = (V, E) ein Graph. Dann gilt: G ist zusammenh¨angend 1.19 ⇔ ∀x, y ∈ V existiert ein x,y-Weg in G 1.23 ⇔ ∀x, y ∈ V existiert ein…

gerichtete Kanten