I have to solve a problem using bipartite graphs and matchings. The way I modeled it is to have a graph $G=(A \cup B, E)$, and have the vertices in $A$ represent persons and the vertices in $B$ representing clubs. Then, the edges represent club membership.
How can I find the smallest possible value of $K$ that guarantees there is an assignment that satisfies the following conditions?
1. A person can be member of at most 50 clubs
2. Each club must have a president (which is a member of the club)
3. A person can be president of at most 5 clubs
4 Each club must have at least $K$ members
Here is a reformulation I made of the problem in mathematical terms:
What value of $K$ ensures that $G$ has a $B$-covering matching $M$ knowing:
1. $ \forall v \in A, deg(v) \leq 50$
2. $\forall v \in A, v$ is incident to at most 5 edges in $M$
3.$ \forall v \in B, deg(v) \geq K$
I know we need to find a matching (to model the presidency relation) in $G$ that contains every vertex from $B$ but I am unsure how to find the value of $K$ that ensures that such a matching can in fact be obtained. Any edge in the matching can be incident to no more than 5 vertices in A. How should I approach the next step of the problem? Thanks