Number of possible bipartite graphs

Question

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!

Answer 1

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! $$

Answer 2

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.

Answer 3

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.