Number of possible bipartite graphs Apologies if this is a basic question, I'm a bit of a rookie when it comes to maths.
If I have two sets of nodes $U$ and $V$, is there a way to calculate how many bipartite graphs could be formed if:


*

*All the nodes in $U$ must have a degree $\geq$ 1

*All the nodes in $V$ must have a degree of 0 or 1


Thank you!
 A: Each $v \in V$ is assigned either a vertex in $U$ or is left disconnected. Thus, each bipartite graph where the vertices in $V$ have degree at most one is equivalent to a function $f:V \to U \cup \{*\}$ where we interpret $f(v) = *$ as $v$ having no neighbour. Now, as an extra condition, we need each vertex in $U$ to be connected to one in $V$. Thus, if $V' = V \setminus f^{-1}(\{*\})$, the mapping $f\restriction_{V'}$ should be surjective. This also chacterizes our graphs, since each solution can be written is this form.
Therefore, we can count these in the following manner: first, we select a subset $W$ of vertices of $V$ that will be disconnected so that at least $|U|$ vertices of $V$ are left. Afterwards, each possible option to connect the vertices on $V \setminus W$ corresponds to a surjective function from $V\setminus W$ to $U$. More concretely, it will suffice to count the following set
$$
\coprod_{\quad W \subseteq V \\ |W| \leq |V| - |U|} \{f:V\setminus W \to U : f \text{ is surjective}\}
$$
whose cardinal is
$$
\sum_{\quad W \subseteq V \\ |W| \leq |V| - |U|} S(|V \setminus V|,|U|)|U|!
$$
where $S(i,j)$ denotes the Stirling number of second kind. A bit more explicitly, if $|V| = m$, $|U| = n$, we have
$$
\sum_{i = 0}^{m-n}{m\choose i}S(m-i,n)n!
$$
possible options (here we use that sets of same size give an equal amount of surjective functions since these only depend on the size of the domain and codomain). Making a change of variable as $k = m - i$ and using the symmetry of the binomial coefficients, we get:
$$
\sum_{k = m}^{n}{m\choose k}S(k,n)n!
$$
A: Let $|V|=n\ge|U|=m$  We want to count the number of functions from subsets of $|V|$ onto $|U|.$  Let $f(k,m)$ be the number of functions from a set of $k$ elements onto a set of $m$ elements.  Since we have $\binom{n}{k}$ ways to choose $k$ elements of |$V|,$ the number we seek is $$\sum_{k=m}^n\binom{n}{k}f(k,m)$$.
It remains to calculate $f(k,m).$  These number are given by the Stirling numbers of the second kind, as explained here.
A: The answer to this question depends quite a bit on what it means for two graphs to be the same. The other answers attempt to address what happens when the labels in $U$ and $V$ matter. The question is just as fun, if a bit more simplistic, when we only consider the count up to isomorphism.


*

*Our first observation is that two such graphs are isomorphic iff the
vertices in $U$ have the same degrees up to a re-ordering.

*Our second observation is that any total number of edges $n$ with $|U|\leq n\leq |V|$ is allowed, and no other number of edges satisfies the necessary constraints.

*Lastly, for any fixed total number of edges $n$, the number of ways of assigning vertex degrees to the vertices in $|U|$ in a way which satisfies the constraints is the number of partitions of $n$, denoted $p(n)$.


Putting it all together, we have $$\boxed{\sum_{n=|U|}^{|V|}p(n)}$$ graphs up to isomorphism.
