Denote the maximum degree of an undirected graph $G=(V,E)$ by $\Delta$. That is, $\Delta = \max_{v\in V} \deg(v)$. I'm looking for a way to divide $G$ into two separate induced subgraphs $G_1=(V_1,E_1),\,\,G_2=(V_2,E_2)$ such that:

  • $V=V_1\dot{\cup} V_2$ (That is, $V$ is the union of $V_1, \,V_2$ and they are disjoint).
  • $E_i$ are the induced edges from $G$ with both vertices being from $V_i$ (That is, $E_i=\{ (u,v) \, | \,\,u,v\in V_i \wedge (u,v)\in E\} $).

(Note that some edges will be neither in $E_1$ nor $E_2$, being cross edges.)


  • The maximum degree, $\Delta_i$ (of $G_i$) is bounded by $\frac{\Delta}{2}$, or by another constant $c<1$: $\,\,\,\Delta_i \leq c\cdot \Delta$.

If I divide the vertices arbitrary, then I have no bound on $\Delta_i$ and I cannot guarantee it will even get smaller (it may remain $\Delta$). Is there a way to divide the graph while maintaining this upper bound on $\Delta_i$?

Additionally, if the answer to the above is positive, I would like to expand this idea to $G_1, \dots ,G_k$ where $k\in\mathbb{N}$, such that each $\Delta_k$ will have a tighter upper bound.


1 Answer 1


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.

  • $\begingroup$ Thanks. But attempting to write an algorithm to find such a partition seems pretty hard, looking at the above description? $\endgroup$ Oct 14, 2021 at 6:17
  • $\begingroup$ For $k=2$, a global minimum cut has the desired property and can be found via Karger's algorithm. en.wikipedia.org/wiki/Karger%27s_algorithm $\endgroup$
    – Tony Huynh
    Oct 14, 2021 at 8:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.