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



Combinatorial proof for bicolored graphs
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$.


