Every student from a set of students applies for exactly three seminars among the seminars that are offered at their university. Two of the seminars are chosen by exactly 40 students, all others are chosen by less than 40 students. Show that every student can participate in a seminar he or she applied for, while guaranteeing that no seminar has more than 13 participants.
We can think this problem in term of bipartite graph with bipartition $A$ represents for students and $B$ for seminars. Every vertex in $A$ has degree 3 and in B has 2 vertex of degree 40 and all other vertices has degree less than 40. Problem is to ask for a cover of $A$. I think it should be generalization of Hall theorem. But I cannot figure out how to solve this problem. Can anyone give me some hints? Thank you in advance!
Let $S_1,\ldots,S_k$ be the seminars and $s_i$ the number of applications for seminar $S_i$. Split each seminar in $\lceil \frac{s_i}3\rceil$ parts of size at most 3, except the two seminars that had 40 applications, which we split in 12 parts of size 3 and 1 part of size 4. Note that each seminar is split in at most 13 parts.
Consider the $A,B$-bigraph where the vertices of $A$ are the students, the vertices of $B$ are the "seminar parts" we just created.
Let $S\subseteq A$, say $|S|=s$. Assume $|N(S)|=t$. $N(S)$ receives exactly $3s$ edges from $S$, and each vertex of $N(S)$ can accomodate only 3 edges, except two, which can hold 4 edges, so $N(S)$ can accomodate at most $3t+2$ edges. This means $3t+2\geq 3s$ so $t\geq s$ (since $s$ and $t$ are integers), which proves that Hall's condition holds in this bigraph.
So the bigraph has a matching of $A$. In each seminar part at most one edge arrives, and each seminar has at most 13 parts, so this matching leads to the desired configuration.