# Combinatorial proof for bicolored graphs

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

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