Another characterization of bipartite graphs is that every cycle, every closed walk, must have even length. The graph below is not bipartite, since it has cycles of length 5, but still ... . Can you solve a randomly created instance? How many of the randomly generated instances can you solve?