2
$\begingroup$

A bicolored graph is a graph each vertex of which has been assigned one of two colors such that each edge connects vertices of different colors. A bipartite graph is a graph $G$ which admits such a coloring. Given $j$ white and $i$ black vertices, there are $2^{ji}$ ways to join vertices of different colors. Thus the number of (labeled) bicolored graphs on n vertices is $$b_n=\sum_{i+j=n}\binom{n}i2^{ij}.$$

Question. Is there a combinatorial proof for this identity? $$\sum_{i+j=n}\binom{n}{i,j}2^{ij}=2\sum_{i+j+\ell=n-1}\binom{n-1}{i,j,\ell}2^{ij+j\ell}.$$

$\endgroup$

1 Answer 1

3
$\begingroup$

RHS also enumerates bipartite labelled graphs. Fix a vertex $v$. We choose a color for it (multiple 2 in RHS), then we choose $j$ vertices of the same color and $i$ neighbors of $v$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .