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

Question

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?

Answer 1

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

Answer 2

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!

Answer 3

The proof is not correct, bits of text in italic below correspond to the parts of the proof which are flawed.

I think that the property is true, and that we can build a solution and then a random sample of such graphs.

Here is a scheme of proof. It needs a little more formalization, though I think there are enough elements to assess if it works or not.

Proof of existence and construction process

• Finding adequate $G_a=(V,E_a)$ and $G_b=(V,E_b)$ is equivalent to color the edges of a realization of $c$, so that an edge is either red (belongs to $E_a$) or blue (belongs to $E_b$), I will use this lexicon in the following,

• let $G_c=(V,E)$ be any realization of sequence $c$ (for example achieved using a Havel-Hakimi process),

• the general idea is, starting from $G_c$ to color edges in red following a process similar to Havel-Hakimi process based on sequence $a$, either the edge to color already exists in $G_c$ and this is fine, or it doesn't and in this case we create the edge by swapping edges,

• precisely, let us suppose that nodes are relabeled $1, 2, \ldots ,n$ so that $a$ is ordered in a decreasing order: $ a_1 \geq a_2 \geq \ldots \geq a_n $

• according to Havel-Hakimi, we should color edges $ (1,2) $, $(1,3)$ , ... , $(1,a_1+1)$ (if these edges do not exist we will modify the graph without changing its degree sequence $c$, as explained later), when this is done the remaining degree sequence of $a$ is reordered and we distribute the remaining highest degree node over the other highest degree nodes and so on until sequence $a$ is realized by $ G_a=(V,E_a)$

• when trying to color an edge $(u,v)$, one of two things are possible:

  • either $ (u,v) $ exists in the graph then the edge is colored in red,

  • or it doesn't, so $u$ is related to another node $x$ by an uncolored edge and so is $v$ to $y$, so we can swap these edges by connecting $u$ to $v$ and $x$ to $y$,

    • there are a few special cases to handle: i) if $ (x,y) $ already exists (which would lead to a multi-edge) and ii) if $x=y$ (which would lead to a self-loop)

    • i) if $ (x,y) $ already exists and is red, we can simply color $(u,x)$ and $ (v,y) $ in red and turn back $ (x,y) $ uncolored, we have strictly decreased $a$ sequence and we carry on the process,

    • if $ (x,y) $ already exists and is uncolored, note that edges which will belong to $E_b$ are uncolored at this stage, so we know that there is another uncolored edge $ (x',y') $ in the graph, otherwise sequence $b$ is $ (2,2) $ which is not a valid sequence, here it can be objected that we can have $ x' = x $ (or similarly $ y' = y$) but we would go back to a similar problem: it leads to a sequence (3,2,1) which is not valid,

    • ii) if $x=y$, we can make a similar argument: there must be an uncolored edge $ (x',y') $ elsewhere in the graph with both $ x \neq x'$ and $ x \neq y'$ for sequence $b$ to be valid, then we can swap $(u,x)$ and $ (x',y') $ to create $ (u,x') $ and $(x,y')$ and it is possible to swap again to create $ (u,v) $ and $ (x,x') $

  • So in all cases, we can always find either a swap sequence or a recoloring sequence which allows to continue the process until we have completed the red-coloration of edges.

In the end, the set of red edges is $E_a$ and the remaining uncolored edges of the modified graph can be colored in blue as they satisfy $ \forall i$, $ c_i = a_i + b_i $ (we didn't change the degree of any node in the original graph, and we colored exactly $a_i$ edges incident to node $c_i$).

Sampling

For this part, I think that the following process achieves a uniform random sampling:

• starting from the 2-color graph constructed above, select any edge randomly

• depending on its color, select any edge of the same color, swap their ends as long as it doesn't create a loop or a multi-edge of this color, if it does, we keep the current configuration,

• iterate this process until we reach the steady state of this Markov process

• note that this process can produce 2-edges as we may get two nodes connected simultaneously by a blue edge and a red edge

  • if there is one or more 2-edge, we discard the graph obtained as it is not a valid realization of $c$, and restart the process,

  • if the final graph doesn't have 2-edge, the 2-colored graph is a valid realization of $G_c$ which edge-coloring corresponds to a valid realization of $b$ and $b$ is added to the sample.

Such a process is very similar to sampling graphs with a given degree sequence with a swap process, which has been largely discussed in the literature (I like this article where it is called "switching-and-holding").

Again, it deserves a formal proof, but I have good confidence that this process achieves detailed balance which leads to a uniform sample.