# Number of ways to hook up all vertices of a bipartite graph?

Let A represent the number of labeled vertices on the left side of a bipartite graph, and let B represent the number of labeled vertices on the right. How many ways are there to connect every vertex in A to some number of vertices in B such that no vertex in B is left behind?

You are only given A and B, the number of labeled vertices in the left and right set. I am asking how many ways there are to place edges such that no vertex is left untouched.

Edit: For some reason I can't reply to the messages below, so I have to do it here. I don't think the current answers are right. By exhaustion I count 7 such cases for A=B=2, whereas the answers return 9.

Edit again: Look at the upper left and lower left graphs of the pictures posted below in Fabrício Caluza Machad's answer. Some vertices don't have any edges connecting to them. This is what I mean by "no vertex untouched."

-
You are given the vertices and no edges, and you have to create the edges? –  Aryabhata May 1 '13 at 16:25
When you say "every vertex in $A$ to "some number" of vertices in $B$, are you including that this number might be zero for some of the vertices in $A$, as long as all of $B$ gets covered by something from $A$? Or do you mean to have each thing in $A$ map to a nonempty subset of $B$? it makes a difference, and when $A=B=2$ would account for your answer being two less, since you would exclude the two maps where $A_1$ maps to nothing, or when $A_2$ maps to nothing. This distinction will make a difference in the count. –  coffeemath May 1 '13 at 17:27

Use the inclusion-exclusion principle.

Let $|A|=n, |B|=m$.

There are $2^{nm}$ bipartite graphs between $A$ and $B$. From these, $\binom{m}{k}2^{n(m-k)}$ reach at most $m-k$ vertices from $B$. by The inclusion exclusion principle, the number you seek is

$$\sum_{k=0}^m (-1)^k \binom{m}{k}2^{n(m-k)} =2^{mn}\sum_{k=0}^m \binom{m}{k}(\frac{-1}{2^{n}})^k =2^{mn}(1-\frac{1}{2^{n}})^m=(2^n-1)^m$$

Edit: *Second solution*

The answer suggested the following simpler solution:

Any such graph is uniquely determined by the set of vertices connected with every vertex of $B$.

Let $X$ denote the set of all non-empty subsets of $A$ and let

You can uniquely identify any graph $G$ like in the problem with a function $f: B \to X$ by

$$f(v) :=\{ u \in A | uv \in E(G) \} \,.$$

Moreover, any $f: B \to X$ uniquely determines a bipartite graph like in the problem, with $V(G)=A \cup B$ and

$$E(G)= \{ uv| v \in B, u \in f(v) \} \,.$$

It is easy to prove that the processes I described define inverse functions, thus the number of graphs is equal with the number of function $f: B \to X$, which is

$$|X|^{|B|}=(2^{|A|}-1)^{|B|}$$

To solve the same problem for $A$, do again the same process for $A$. There are $(2^n-1)^m$.

The number of such graphs which don't use $k$ particular fixed vertices are

$$(2^{n-k}-1)^m$$

Thus bi inclusion Exclusion principle, the total number is:

$$\sum_{k=0}^n (-1)^k \binom{n}{k}(2^{n-k}-1)^m$$

-

You can solve it with the inclusion-exclusion principle.

Let $\mathcal B_i, 1 \leq i \leq |B|$ be the family of graphs such that $b_i \in B$ isn't connected with a vertice in $A$. We can count the number of graphs in $\mathcal B_i$ as $2^{|A|\ (|B|-1)}$ (every vertex in $A$ can connect with $|B|-1$ vertices in $B$)

Similarly, if $I \subset \{1,2,...,|B|\}$ and $i = |I|$, then $| \bigcap_{k\in I} \mathcal B_k| = 2^{|A|\ (|B|-i)}$.

So, what you want to count is: $|( \bigcup_{k=1}^{|B|} \mathcal B_k)^C | = 2^{|A||B|} - \sum_{k=1}^{|B|}(-1)^{k-1}\binom{|B|}{k}2^{|A|\ (|B|-k)} = \sum_{k=0}^{|B|}(-1)^{k}\binom{|B|}{k}2^{|A|\ (|B|-k)}$

Answering question edit: case |A| = 2 and |B| = 2, we have 9 answers:

-
These are the cases in which "no vertex in $B$ is left behind" as stated in the OP. However the OP has now seemingly objected also to the upper and lower pictures in column 1, by the phrase "no vertex untouched". If OP wants that, his wording in the question should say so, i.e something like "every vertex in $A \cup B$ has at least one edge going out of it". That makes the count harder! BTW a simple argument in which one only wants $B$ vertices untouched gives $(2^a-1)^b$ where $a=|A|,b=|B|$. –  coffeemath May 1 '13 at 18:07