Simple graphs with prescribed degrees as disjoint union of simple subgraphs with prescribed degrees

The answer to this question is No.

Let us assume $V = \{1,2,3,4,5,6\}$ and consider degree sequences $a = [3,2,2,1,0,0]$, $b = [1,0,0,3,2,2]$ and $c = a+b = [4,2,2,4,2,2]$.

The only simple graph with degree sequence $a$ is given by $1-2$, $1-3$, $1-4$, and $2-3$. Similarly, the only one with degree sequence $b$ is given by $4-1$, $4-5$, $4-6$, and $5-6$. In the union of these two graphs, the edge between $4$ and $1$ appears twice, making it a multi-graph.

However, $c$ is graphical: a simple graph with degree sequence $c$ is given by $1-2$, $1-3$, $1-5$, $1-6$, $4-2$, $4-3$, $4-5$, $4-6$.

Thus, we have three graphical degree sequences $a$, $b$ and $c$ such that $c=a+b$ but no simple graph with degree sequence $c$ is the disjoint union of a simple graph with degree sequence $a$ and a simple graph with degree sequence $b$.

I think your property is true and can be shown recursively depending on the size $n$ of the graph.

Existence

For $n=2$ well one of the sequences has to be (0,0), so the other one is equal to $c$: it works just fine.

Now suppose that works for any valid sequence of length $n-1$ for some integer $n>2$. Take valid degree sequences $a$, $b$, $c$ of size $n$. Build any simple graph $G=(V,E)$ following sequence $c$.

Remove whichever node $u$ and its adjacent edges $U$. It will change the degree distrubution of its neighbours $N_u$ in the remaining graph. Define sequences $c'$, $a'$ and $b'$, copies of $c$, $a$ and $b$ except: $$\forall v\in N_u, c'_v=c_v-1$$ $$\forall v\in N_u\text{ st }a_v>0, a'_v=a_v-1 $$ $$\forall v\in N_u\text{ st }a_v=0, b'_v=b_v-1 $$

The edges in $U$ can be separated in $E_a$ and $E_b$ depending on whether they impact distribution $a'$ or $b'$: $$E_a=\{(u,v)\in U \:|\: a_v>0\}$$ $$E_b=\{(u,v)\in U \:|\: a_v=0\}$$

By construction, we have $\forall v\in V, c'_v=a'_v+b'_v$, and $a',b',c'$ are valid sequences of size $n-1$. This is not necessarily true: the sequences may not be valid, so the recursion is wrong.

By assumption, we can build a graph $G'=(V',E')$ such that:

• $V'=V\backslash\{u\}$
• $E'=E'_a\cup E'_b$ and $E'_a\cap E'_b=\emptyset$
• $G'$ follows distribution $c'$, $G'_a=(V',E'_a)$ follows distribution $a'$ and $G'_b=(V',E'_b)$ follows distribution $b'$

Finally, you add the node $u$ and its former edges to obtain the graph $G^*=(V,E'\cup U)$. The partition of edges is $E_a^*=E_a\cup E'_a$ and $E_b^*=E_b\cup E'_b$, which satisfies all the properties.

So this decomposition exists for distributions of size $n$.

Construction

This recursion provides a constructive process. If distributions of size $n$ are given, assuming they are valid, you can select a random node to remove, apply the procedure on the remaining graph, and then add the extra edges.

Note that the above definition of $E_a$ and $E_b$ is not symmetrical: it would be more balanced to choose at random if an edge of $U$ is affected to $E_a$ or $E_b$.

If $u$ is also chosen at random, and the case $n=2$ forces uniformly $a=c$ or $b=c$, then it may be considered as "uniform". However in my opinion, this concept needs to be clearly defined. Moreover, the recursion may not yield all the possible constructions.

Cheers!