TU Wien:Discrete Mathematics VU (Gittenberger)/Exam 2026-01-30

Note: these exercises were recalled from memory and might not be completely correct.

Exercise 1

Consider a ring $R$ with a subset $A\subseteq R$. Let $I(A)$ be the set of all ideals containing $A$ and $J=\bigcap _{X\in I(A)}X$.

1. Show $J$ is an ideal.
2. Show if $A\subseteq M$, then $J\subseteq M$.

Exercise 2

Solve the following recurrence relation using generating functions:

$a_{n+3}+3a_{n+2}-3a_{n+1}+a_{n}=1$

Exercise 3

Show that ${\sqrt {3}}-{\sqrt {5}}$ is algebraic over $\mathbb {Q}$ and find its minimal polynomial.

Exercise 4

Define a graph coloring and what it means for it to be feasible.

Define a tree.

What is the chromatic number of a tree and of $K_{n}$?

Provide a proof sketch of the fact that any planar graph can be colored with no more than 5 colors.