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 it true that $b\_n$ is never divisible by $5$? If so, any proof?
> 
> 
> 


**Update.** One combinatorial proof and two number-theoretic/algebraic proofs are supplied.



Arithmetic problem for bicolored graphs
This follows from the fact that for any prime $p$, and any integer $n\ge0$, we have $b\_{n+p}\equiv b\_{n+1} \pmod p$. This can be proved by a straightforward, though not very interesting, computation, using Fermat's theorem $2^p\equiv 2 \pmod p$ and the fact that $\binom {n+p}{i} \equiv \binom ni + \binom n{i-p} \pmod p$. 


More interesting is a combinatorial proof. (For similar proofs and further references, see my paper [Combinatorial proofs of congruences](http://people.brandeis.edu/~gessel/homepage/papers/combinatorial-congruences.pdf), in *Enumeration and Design*, ed. David M. Jackson and Scott A. Vanstone, Academic Press, Toronto, 1984, pp. 157–197, especially section 5.)


We consider the cyclic group $C\_p$ acting naturally on $[p]=\{1,2,\dots, p\}$. This extends to an action on bicolored graphs with vertex set $[n+p]=\{1,2,\dots, n+p\}$; the group permutes vertices $1, 2, \dots, p$, and does not change the other vertices. Since every orbit has size 1 or $p$, $b\_{n+p}$ is congruent modulo $p$ to the number of bicolored graphs on $[n+p]$ fixed by this action of $C\_p$. It is not hard to see that these fixed bicolored graphs are those in which all vertices in $[p]$ have the same color, no edges join two vertices in $[p]$, and all vertices in $[p]$ have the same neighborhood. By "contracting" all the vertices in $[p]$ to a single vertex, whose neighborhood is the same as the neighborhood of any of the vertices in $[p]$, we get a bicolored graph on $n+1$ vertices. Thus the number of fixed bicolored graphs is $b\_{n+1}$, so $b\_{n+p}\equiv b\_{n+1}\pmod p$.


