Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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."

share|improve this question
    
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

2 Answers 2

up vote 0 down vote accepted

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


ADDED AFTER THE CLARIFICATION

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

share|improve this answer

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:

enter image description here

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.