TU Wien:Diskrete Mathematik für Informatik VU (Stufler)/Probeprüfung 2022-12-06

Probeprüfung zur Vorbereitung auf die Prüfung (Übungsleiter: Philipp Beltran).

1. Give the definition of a matroid and a base of a matroid and give an example.
2. Draw the following graph $G$ and determine if it is planar. If it is planar, then also draw one of its duals. $G=(V,E)$ with vertex set $V=\{1,2,3,4,5,6,7,8,9,10,11,12,13,14\}$ and edge set $E=\{\{1,2\},\{2,3\},\{3,4\},\{4,5\},\{5,6\},\{5,8\},\{6,7\},\{8,9\},\{9,10\},\{10,11\},\{11,12\},\{11,13\},\{11,14\},\{13,14\}\}$.
3. Let G be a connected planar graph with at least $10$ vertices. Show that the average degree of vertices is smaller than $10$.
4. 1. Give one characterization of a tree and determine the relationship between the amount of vertices to the amount of edges. Also prove your claim.
   2. Let $G$ be a connected planar graph with $n\leq 3$ vertices. Determine the maximal amount of edges and prove your claim.