A note on bipartite subgraphs of triangle‐free graphs

Abstract

Abstract Let G be a triangle‐free graph on n points with m edges and vertex degrees d 1 , d 2 ,…, d n . Let k be the maximum number of edges in a bipartite subgraph of G. In this note we show that k ⩾ m /2 + Σ √ d i . It follows as a corollary that k ⩾ m /2 + cm 3/4 .