Decomposing Degenerate Graph into Two Degenerate Graphs

graph theory

Let $G$ be a $p+q+1$ degenerate graph (meaning, every subgraph has a vertex of degree at most $p+q+1$). Then how do you show there exist sets $A,B \subseteq V(G)$ which partition $V(G)$ such that $G[A]$ (subgraph induced by $A$) is $p$ degenerate and $G[B]$ is $q$ degenerate?

Best Answer

The degeneracy of a graph is defined the way it is to make it easy to induct on $d$-degenerate graphs.

So in this case, we also want a proof by induction on the number of vertices in the graph. Given a $(p+q+1)$-degenerate graph $G$, we:

  • Find a vertex $v$ with degree at most $p+q+1$.
  • By the induction hypothesis, partition the vertex set of $H = G-v$ into two sets $A$ and $B$ such that $G[A]$ is $p$-degenerate and $G[B]$ is $q$-degenerate.
  • Now decide whether to add the vertex $v$ to $A$ or to $B$.

All this is a sort of "template" for doing induction on degenerate graphs: we can always pick out a vertex $v$ with small degree, and be left with a degenerate graph $G-v$ that we can apply the induction hypothesis to. (The base case is often straightforward, as it is here: if there's only one vertex, we can add it to $A$ or to $B$ as we prefer.)

I'll leave you to finish the proof: how do we decide whether to add the vertex $v$ to $A$ or to $B$ such that the partition of $G$ has the property we want? And how do we know that one of the options will always work?

Related Question