A note on bisections of graphs with girth at least 6

Abstract

A bisection of a graph is a partition of its vertex set into two sets which differ in size by at most 1, and its size is the number of edges between the two sets.  Let G be a graph with m edges, perfect matchings and girth at least 6. Let d₁, d₂,  . . .  , d_n be vertex degrees, then there is a constant c > 0 such that G admits a bisection of size at least m/2 + \(c \; \sum_{i=1}^{n} \; \sqrt{d_i}\).  It follows as a corollary that G has a bisection of size at least m/2 + cm^3/4.