Diskrete Mathematik/Gemischte Definitionsabfrage/3. Drittel/3/Aufgabe/Lösung

1. Ein Automorphismus ist ein Isomorphismus ${}\varphi \colon G\rightarrow G$.
2. Ein Graph heißt zusammenhängend, wenn es zu je zwei Punkten  ${}u,v\in G$  einen Weg gibt, der ${}u$ und ${}v$ verbindet.
3. Ein Weg ist eine Folge ${}v_{1},v_{2},\ldots ,v_{m}$ von Knoten derart, dass ${}v_{i}v_{i+1}$ für alle ${}i$ eine Kante ist.
4. Eine Knotenüberdeckung ist eine Teilmenge  ${}W\subseteq V$  mit der Eigenschaft, dass jede Kante mindestens einen Knoten aus ${}W$ trifft.
5. Ein aufspannender Baum ist ein Untergraph  ${}B\subseteq G$  von ${}G$, wenn ${}B$ ein Baum mit der vollen Knotenmenge ${}V$ ist.
6. Die Paarung heißt perfekt, wenn jeder Knoten des Graphen durch eine Kante der Paarung abgedeckt wird.

Zur gelösten Aufgabe