Skip to main content
2 of 2
edited body
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

Yes, every graph $G$ with maximum degree $\Delta$ can be partitioned into $k$ sets $X_1, \dots, X_k$ such that the maximum degree of $G[X_i]$ is at most $\lfloor \Delta / k \rfloor$ for all $i$. This bound is best possible (consider the complete graphs $K_n$).

Proof. Given an arbitrary partition of $V(G)$, call an edge monochromatic, if both of its ends are in one set of the partition. The required partition is obtained by choosing a partition $X_1, \dots, X_k$ that minimizes the number of monochromatic edges. Suppose not and assume $v \in X_i$ has more than $\lfloor \Delta / k \rfloor$ neighbours in $X_i$. By the Pigeonhole Principle, there must be some $X_j \neq X_i$ with at most $\lfloor \Delta / k \rfloor$ neighbours of $v$. Moving $v$ from $X_i$ to $X_j$, decreases the number of monochromatic edges, which is a contradiction.

Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187