Maximum cuts and judicious partitions in graphs without short cycles

We consider the bipartite cut and the judicious partition problems in graphs of girth at least 4. For the bipartite cut problem we show that every graph G with m edges, whose shortest cycle has length at least r⩾4, has a bipartite subgraph with at least m2+c(r)mrr+1 edges. The order of the error term in this result is shown to be optimal for r=5 thus settling a special case of a conjecture of Erdős. (The result and its optimality for another special case, r=4, were already known.) For judicious partitions, we prove a general result as follows: if a graph G=(V,E) with m edges has a bipartite cut of size m2+δ, then there exists a partition V=V1∪V2 such that both parts V1,V2 span at most m4−(1−o(1))δ2+O(m) edges for the case δ=o(m), and at most (14−Ω(1))m edges for δ=Ω(m). This enables one to extend results for the bipartite cut problem to the corresponding ones for judicious partitioning.