TU Wien:Diskrete Mathematik für Informatik VU (Gittenberger)/Prüfung 2013-12-02

Beispiel 1: Prove with induction over ${\alpha }_0(G)$ that the following holds: $\chi (G)\le 1+\underset{v\in V(G)}{max}d(v)$

Beispiel 2: Given a matroid M=(E,S), a circuit $C\subseteq E$ is a not independent set and minimal under inclusion. I.e. all subsets of C are independent sets. Given two non-equal circuits C and D with an edge $e\in C\cup D$ prove that $K\subseteq (C\cup D)-e$ is also a circuit.

Beispiel 3: Give complete mathematical definitions for:

- degree of a vertex

- matching

- strongly connected

- reduction

- und noch was

Beispiel 4:

- Definition of metric space

- Definition of surface + Give 3 examples

- Definition of Euler characteristic