An Edwards-type lower bound for the maximum k-cut of a connected graph

Abstract

Let G be a finite simple connected graph with n vertices and m edges, and let f_k(G) denote the maximum number of bichromatic edges over all k-colorings of G. We prove that for every integer k ≥ 3, f_k(G) ≥ (k−1)m/k + (n−1)/k. Equivalently, the minimum number es_k(G) of edges whose deletion makes G k-colorable satisfies es_k(G) ≤ ⌊(m−n+1)/k⌋. The proof proceeds in two steps: a greedy k-coloring reduces the problem to an ordering lemma, which is then proved by induction based on the deletion of non-cut vertices. Trees and cycles show that the additive coefficient 1/k is best possible.