TU Wien:Discrete Mathematics VO (Rubey)/Written Exam on 16/06/2023

The exam was made up of four pages with one problem per page, each problem consisted of several sub-problems. As far as I can remember, it contained the following:

Max Flow/Min Cut

very similar to the problem in the mock exam in general, it consisted of the following subproblems:

• In the context of the Maximum Flow/Min Cut theorem, define a flow network.
• Define a flow on the flow network and its valuation.
• Define a cut on a flow network and its capacity
• Define an augmenting path and its existence on a flow network
• Show that the value of any flow is at most the value of any cut
• Assuming there is no augmenting path for a flow, define a minimum cut
• Show that if there exists an augmenting path, the flow can be increased

Spanning Trees and Chromatic Polynomial

• Compute the number of spanning trees for the diamond graph, which is obtained by deleting one edge from $K_{4}$
• What does the chromatic Polynomial $P_{G}(x)$ express?
• Without providing a proof, state the chromatic polynomial for a path of $n$ vertices and the star graph of $n$ vertices (one vertex of degree $n-1$ connected to all other vertices of degree 1).
• Also without proof, state the deletion-contraction rule for the chromatic polynomial of a graph and for the number of spanning trees in a graph

I think there was one more problem on this page related to the same topic, it was however definitely not in the mock exam.

Generating Functions

• Compute the exponential generating function for the number of ordered trees where no vertex has exactly one child (i.e., no vertex has degree 2)
• Same for unordered trees where no vertex has exactly one child
• Solve the recurrence relation $f_{n}=\sum _{k=0}^{n-1}f_{k},f_{0}=1$ using generating functions (Hint: Exchange the order of summation)

Counting Principles and Number Theory

• State the principle of inclusion and exclusion
• Use the principle of inclusion and exclusion to compute the number of integers $1\leq n\leq 100$ such that $2\nmid n,3\nmid n$ and $5\nmid n$.
• State the Chinese Remainder Theorem
• Which values can $x$ take if $100\leq x\leq 200$ and $x\equiv 2\mod 7,x\equiv 6\mod 9$ (not entirely sure about $a_{i}$ for the first congruence)
• Find $a$ and $b$ given an equation of the $x=ac+bd$ where $\operatorname {gcd} (a,b)=x$ (can't remember the concrete numbers for $x,c$ and $d$, but there were about 3 steps of extended euclidean algorithm involved, not too bad)

I prepared pretty well for the exam, but ran out of time writing, especially with the generating functions; Also, there was only 90 minutes of work time, I am not sure whether this is the same in all exams or if this was just because of the Bachelor Math Exams that took place in the same lecture hall. 10 Minutes of extra time wouldn't have been bad. I was a bit surprised by the amount of definitions asked to be given, I thought that's what the oral exam is for (especially, in comparison with other math course I've taken). I find it however quite interesting that the "polynomials on finite fields" topic was entirely skipped in the exam, I suppose the oral exam will be more focused on the algebraic structures and their definitions.

To summarize, if you want to get a positive grade, I think the exam was quite easy and definitely doable if you understood the content of the mock exam. For me personally however, giving a mathematically sound answer to all problems wasn't possible in the time given, except when you know all theorems and proofs from the lecture by heart, which I only partially did.