# Partition of a graph into subgraphs with small maximum degree

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.)

and:

• 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.

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.

• Thanks. But attempting to write an algorithm to find such a partition seems pretty hard, looking at the above description? Oct 14, 2021 at 6:17
• 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 Oct 14, 2021 at 8:17