A sequence of numbers is called a graphic sequence if it is the degree sequence of some graph. Given a simple graph $G$, let its degree sequence be $D_G$. Suppose we have another sequence of numbers $D$ that satisfies:
- $D_G[i] \ge D[i], \forall i$
- $\bigg( \sum_{i}^{}{D_G[i]} - \sum_{i}^{}{D[i]} \bigg)$ is an even number
I'd like to realize $D$ as the degree sequence of a spanning subgraph of $G$, by removing edges from $G$. I was wondering if there is any polynomial-time algorithm to determine if such a spanning subgraph exists?
After some research, I think I figured out a poly-time algorithm to find a spanning subgraph of $G$ that has $D$ as its degree sequence or conclude none exists.
Let $G=(V, E)$. The idea is to utilize Tutte's $f$-factor theorem. An $f$-factor of a graph $G$ is a spanning subgraph $H$ such that the degree of any node $v \in V$ is: $deg(v)=f(v)$. In my problem $f(v) = D[v], \forall v \in V$. An algorithm was given by Tutte, which decides if an $f$-factor exists in polynomial time. The basic idea of the algorithm is to construct another graph $G^\prime$. Then Tutte showed that an $f$-factor exists in $G$ if and only if a perfect matching exists in $G^\prime$. Finally, the problem of deciding if an $f$-factor exists is reduced to find a perfect matching in $G^\prime$.