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 .
No takes yet. Share an insight, caveat, or question.
James B. Shearer (1992) studied this question.