The minimum size of graphs satisfying cut conditions

A graph G of order n satisfies the cut condition (CC) if there are at least |A| edges between any set A⊂V(G), |A|≤n∕2, and its complement A¯=V(G)∖A. For even n, G satisfies the even cut condition (ECC), if [A,A¯] contains at least n∕2 edges, for every A⊂V(G), |A|=n∕2. We investigate here the minimum number of edges in a graph G satisfying CC or ECC. A simple counting argument shows that for both cut conditions |E(G)|≥n−1, and the star K1,n−1 is extremal. Faudree et al. (1999) conjectured that the extremal graphs with maximum degree Δ(G)