A note on triangle-free and bipartite graphs Original Research Article

Using a clever inductive counting argument Erdős, Kleitman and Rothschild showed that almost all triangle-free graphs are bipartite, i.e., the cardinality of the two graph classes is asymptotically equal. In this paper, we investigate the structure of the few triangle-free graphs which are not bipartite. Using similar techniques as Erdős, Kleitman and Rothschild we prove that with high probability these graphs can be made bipartite by removing a single vertex. In this sense these graphs are almost bipartite.