\subsection*{Problem 1}
How many different such trees exist on $100$ labeled vertices, labeled $v_1, \dots, v_{100}$, each of which contains all the edges in the set $\{ v_iv_j : i+j = 101 \}$?

\subsection*{Problem 2}
Let $G$ be a graph on 1863 vertices, each of degree at least $1492$. What is the size of the largest matching in $G$? (\textit{Reminder: a matching is a set of pairwise disjoint edges.})

\subsection*{Problem 3}
There is a small island with $n$ families living on it. The Ministry of Agriculture has partitioned the land into $n$ equal-sized hunting zones, and independently, also into $n$ equal-sized planting zones. It is the duty of the Ministry of Social Affairs to assign each of the $n$ families one hunting zone and one planting zone. Officials of this ministry are concerned about the independence of the two partitions. They fear that it may not be possible to assign each family a hunting zone and a planting zone in such a way that the hunting zone of each family intersects the planting zone of the same family, which was their original intention. However, the Chief Magician of the island claims that such an assignment is always possible, even without seeing the actual partitions. Prove that he is correct.

\subsection*{Problem 4}
Given a directed graph $D=(V,A)$, vertices $s,t \in V$, and conservative cost functions $c_1, \dots, c_k: A \to \mathbb{R}$. Give an algorithm that decides whether there exists a directed $s$-$t$ path that is of minimum cost with respect to all $c_i$.

\subsection*{Problem 5}
Let $x_1$ and $x_2$ be maximum flows in the network $D=(V,A,s,t,c)$, where $s,t \in V$ and $c: A \to \mathbb{R}_+$ is a capacity function. Show that there exists a maximum flow $x$ such that $x(sv)=x_1(sv)$ for every arc leaving $s$, and $x(wt)=x_2(wt)$ for every arc entering $t$.
