Consider a set $V$ of $n$ vertices, and three degree sequences $a\_i$, $b\_i$ and $c\_i$ such that $c\_i = a\_i+b\_i$, $i=1..n$.


Assume these degree sequences are graphical: there exist *simple* graphs (no loop, no multiple edge) with degree sequence $a\_i$, $b\_i$, and $c\_i$.


**Does this imply that there exists a *simple* graph $G\_c=(V,E\_c)$ with degree sequence $c\_i$ being the *disjoint* union of two graphs $G\_a = (V,E\_a)$ and $G\_b = (V,E\_b)$ with degree sequence $a\_i$ and $b\_i$, respectively?**


Remarks:


* Disjoint union means here that $E\_a \cup E\_b = E\_c$ and $E\_a \cap E\_b = \emptyset$; $E\_a$ and $E\_b$ form a *partition* of $E\_c$.
* Since $a\_i$ and $b\_i$ are graphical, there exists simple graphs with these degree sequences. However, they may contain the same edges and so their union is not a simple graph with degree sequence $c\_i$


Subsidiary questions:


* If such graphs do exist, how to build them?
* How to sample the two subgraphs uniformly at random?



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$**.


