On the CNF-complexity of bipartite graphs containing no $K_{2,2}$'s

By a probabilistic construction, we find a bipartite graph having average degree $d$ which can be expressed as a conjunctive normal form using $C\log d$ clauses. This contradicts research problem 1.33 of Jukna.