Question

Graphs with prescribed degree sequences. Given a list of n positive integers ${\mathbf{d}}_{\mathbf{1}}\mathbf{,}{\mathbf{d}}_{\mathbf{2}}\mathbf{,}\mathbf{\dots }\mathbf{,}{\mathbf{d}}_{\mathbf{n}}$, we want to efficiently determine whether there exists an undirected graph$\mathbf{G}\mathbf{=}\mathbf{(}\mathbf{V}\mathbf{,}\mathbf{E}\mathbf{)}$ whose nodes have degrees precisely${\mathbf{d}}_{\mathbf{1}}\mathbf{,}{\mathbf{d}}_{\mathbf{2}}\mathbf{,}\mathbf{\dots }\mathbf{,}{\mathbf{d}}_{\mathbf{n}}$ . That is, if $\mathbf{V}\mathbf{=}\mathbf{\{}{\mathbf{v}}_{\mathbf{1}}\mathbf{,}\mathbf{\dots }\mathbf{,}{\mathbf{v}}_{\mathbf{n}}\mathbf{\}}$, then the degree of ${\mathit{v}}_{\mathbf{i}}$ should be exactly ${\mathbf{d}}_{\mathbf{i}}$. We call $\mathbf{(}{\mathbf{d}}_{\mathbf{1}}\mathbf{,}\mathbf{\dots }\mathbf{,}{\mathbf{d}}_{\mathbf{n}}\mathbf{)}$ the degree sequence of $\mathit{G}$. This graph $\mathit{G}$ should not contain self-loops (edges with both endpoints equal to the same node) or multiple edges between the same pair of nodes.

(a) Give an example of ${\mathit{d}}_{\mathbf{1}}\mathbf{,}{\mathit{d}}_{\mathbf{2}}\mathbf{,}{\mathit{d}}_{\mathbf{3}}\mathbf{,}{\mathit{d}}_{\mathbf{4}}$ where all the ${\mathit{d}}_{\mathbf{i}}\mathbf{\le }\mathbf{3}$ and ${\mathit{d}}_{\mathbf{1}}\mathbf{+}{\mathit{d}}_{\mathbf{2}}\mathbf{+}{\mathit{d}}_{\mathbf{3}}\mathbf{+}{\mathit{d}}_{\mathbf{4}}$ is even, but for which no graph with degree sequence$\mathbf{(}{\mathbf{d}}_{\mathbf{1}}\mathbf{,}{\mathbf{d}}_{\mathbf{2}}\mathbf{,}{\mathbf{d}}_{\mathbf{3}}\mathbf{,}{\mathbf{d}}_{\mathbf{4}}\mathbf{)}$ exists.

(b) Suppose that ${\mathit{d}}_{\mathbf{1}}\mathbf{\ge }{\mathit{d}}_{\mathbf{2}}\mathbf{\ge }{\mathit{d}}_{\mathbf{3}}\mathbf{\ge }{\mathit{d}}_{\mathbf{n}}$ and that there exists a graph $\mathbf{G}\mathbf{=}\mathbf{(}\mathbf{V}\mathbf{,}\mathbf{E}\mathbf{)}$ with degree sequence $\mathbf{(}{\mathbf{d}}_{\mathbf{1}}\mathbf{,}\mathbf{\dots }\mathbf{,}{\mathbf{d}}_{\mathbf{n}}\mathbf{)}$. We want to show that there must exist a graph that has this degree sequence and where in addition the neighbors of ${\mathit{v}}_{\mathbf{1}}$ are ${\mathit{v}}_{\mathbf{2}}\mathbf{,}{\mathit{v}}_{\mathbf{3}}\mathbf{,}\mathbf{\dots }\mathbf{,}{\mathit{v}}_{{\mathbf{d}}_{\mathbf{i}}\mathbf{+}\mathbf{1}}$ . The idea is to gradually transform $\mathit{G}$ into a graph with the desired additional property.

i. Suppose the neighbors of${\mathit{v}}_1$ in $\mathit{G}$are not ${\mathit{v}}_{\mathbf{2}}\mathbf{,}{\mathit{v}}_{\mathbf{3}}\mathbf{,}\mathbf{\dots }\mathbf{,}{\mathit{v}}_{{\mathbf{d}}_{\mathbf{i}}\mathbf{+}\mathbf{1}}$. Show that there exists $\mathbf{i}\mathbf{<}\mathbf{j}\mathbf{\le }\mathbf{n}$ and $\mathit{u}\mathbf{\in }\mathit{V}$ and such that $\mathbf{\{}{\mathbf{v}}_{\mathbf{1}}\mathbf{,}{\mathbf{v}}_{\mathbf{i}}\mathbf{\}}\mathbf{,}\mathbf{\{}\mathbf{u}\mathbf{,}{\mathbf{v}}_{\mathbf{j}}\mathbf{\}}\mathbf{\notin }\mathit{E}$and $\mathbf{\{}{\mathbf{v}}_{\mathbf{1}}\mathbf{,}{\mathbf{v}}_{\mathbf{j}}\mathbf{\}}\mathbf{,}\mathbf{\{}\mathbf{u}\mathbf{,}{\mathbf{v}}_{\mathbf{i}}\mathbf{\}}\mathbf{\in }\mathit{E}$

ii. Specify the changes you would make to $\mathit{G}$ to obtain a new graph ${\mathit{G}}^{\mathbf{\text{'}}}\mathbf{=}\mathbf{(}\mathbf{V}\mathbf{,}{\mathbf{E}}^{\mathbf{\text{'}}}\mathbf{)}$ with the same degree sequence as ${\mathit{G}}^{}$ and where $\mathbf{(}{\mathbf{v}}_{\mathbf{1}}\mathbf{,}{\mathbf{v}}_{\mathbf{i}}\mathbf{)}\mathbf{\in }{\mathit{E}}^{\mathbf{\text{'}}}$.

iii. Now show that there must be a graph with the given degree sequence but in which ${\mathit{v}}_{\mathbf{1}}$ has neighbors ${\mathit{v}}_{\mathbf{2}}\mathbf{,}{\mathit{v}}_{\mathbf{3}}\mathbf{,}\mathbf{\dots }\mathbf{,}{\mathit{v}}_{{\mathbf{d}}_{\mathbf{i}}\mathbf{+}\mathbf{1}}$.

c) Using the result from part (b), describe an algorithm that on input ${\mathit{d}}_{\mathbf{1}}\mathbf{,}\mathbf{\dots }\mathbf{,}{\mathit{d}}_{\mathbf{n}}$ (not necessarily sorted) decides whether there exists a graph with this degree sequence. Your algorithm should run in time polynomial in $\mathit{n}$ and in $\mathit{m}\mathbf{=}{\sum }_{i=1}^n{d}_i$ .

Short answer

a. Example is given.

b. (i) The given can be proved.

(ii) The new graph$G^{\text{'}}=(V,E^{\text{'}})$ has same degree as sequence of graph $G$.

(iii) The execution process will always end, because degree sequence $d_1$ is finite.

c. The above algorithm's concurrent execution in terms of $n$ and $m={\sum }_{i=1}^{i=n}{d}_i$ is $O(n\log n+m)$.

Step-by-step solution

Input Positive contributions

a)

Another collection of $n$ positive numbers is provided as input. $d_1,d_2,d_3,d_4$. To choose another input values for, apply the following condition $d_1,d_2,d_3,d_4$. The first requirement is that "all contributions must be less than as well as equal to $3(d_i\le 3)$. The second criterion is that the total number of inputs must be an even amount $d_1,d_2,d_3,d_4$.

Example:

Choose the appropriate values for $d_1,d_2,d_3,d_4$. Choose values of $d_1,d_2,d_3,d_4$as long as it is less than as well as equal to three. Consider the values of $d_1$ as $3$, $d_2$ as 3, $d_3$ as $1$, and$d_4$ as $1$ . Thus, selected value of $d_1,d_2,d_3$, and $d_4$ is (3, 3, 1, 1) that satisfies the first condition $(d_i\le 3)$.

Check if the inputs meet the second criteria as follows,

$\begin{array}{c}{d}_1+d_2+d_3+d_4=3+3+1+1\\ =8\end{array}$

This degree series is even, and there is no graph with for this degree pattern. The total of the all the input is even and it fulfils the second criteria..

Therefore, one of the possible valid example is $d_1,d_2,d_3,d_4$ with the values $1,1,3,3$.

Confirmation of vertices

b)

(i)

Proof:

Consider the given graph $G$contains the vertex $V_1$ which is neighbor of $d_1$. Because, they are not vertices such as $v_2,v_3,\dots ,v_{d_i+1}$. By definition $(v_1,v_j)\in E$for some $j$ value with the range of $d_1+1<j\le n$and $(v_1,v_j)\notin E$for some $i$ value with the range of $1<i\le d_j+1$. This implies $i$and $j$value with range of $i<j\le n$.

By definition, vertex $v_j$contains the $d_1$ neighbors for $j$and vertex $v_I$contains the $d_i$ neighbors for $i$. From this, vertex $v_j$is a neighbor of $v$in the condition of $d_j>0$. The order of degree indicates that $d_i\ge d_j$. Since, the condition for $i$ and $j$ is $i<j$.

The vertex $v_1$ is a neighbor of $v_j$, but it is not the neighbor of $v_i$. In other words, it simply specifies $(v_1,v_j)\in E$ and $(v_1,v_j)\notin E$.

Therefore, the condition $d_i\ge d_j$ indicates that there must be some vertex $u\ne v_j$.

That is, vertex $u$ is a neighbor of $v_i$ but, it is not the neighbor of $v_j$. In other words, it simply specifies $(u,v_i)\in E$ and $(u,v_i)\notin E$.

Therefore, the graph $G$ exists in the condition of $i<j\le n$ and $u\in V$such that $(v_1,v_i),(u,v_i)\in E$ and $(v_1,v_i),(u,v_i)\notin E$.

ii)

Consider the new graph$G^{\text{'}}$ derived from the graph $G$.In the graph $G$, remove the edges such as $(v_1,v_i)$ and $(u,v_i)$ and add the edges of $(v_1,v_i)$and $(u,v_i)$ to get the new graph $G^{\text{'}}$.

$E=E\cup \{(v_1,v_i),(u,v_i)\}/\{(v_1,v_i),(u,v_i)\}$

Note that the vertices $v_1,v_i,v_j,u\in V$ and the degree does not change. Then, the new graph $G^{\text{'}}=(V,E^{\text{'}})$has same degree sequence of graph$G$ and $(v_1,v_i)\in E$that is,$(v_1,v_i)$is an edge.

Therefore, the new graph $G^{\text{'}}=(V,E^{\text{'}})$has same degree as sequence of graph $G$.

iii)

Proof:

Iterate the above b (i) and b (ii) procedure until the neighbors of vertices$v_1$ are $v_2,\dots ,{v_{d_1}}_{+1}$.

Therefore, the execution process will always end, because degree sequence $d_1$ is finite.

Algorithm for the given input.

c)

Algorithm:

Note: Refer the Question No: 27 (b) in the textbook.

From the above procedure, Consider that the graph $G$is exist on $n$vertices with the degree sequence of$d_1,d_2,\dots ,d_n$. Likewise, if $n-1$vertices contains the degree sequence of

$d_1,d_{2-1},\dots ,d_{d_1+1}-1,d_{d_1+2},\dots ,d_n$

Input:degree sequence$d_1,d_2,\dots ,d_n$ .

Output:The graph is exist on vertices with the degree sequence of $d_1,d_2,\dots ,d_n.$

//Check whether the degree sequence is 0

If $d_1=0$:

//Display the output

Output is "The graph is not exist on vertices"

//Sort the degree sequence$d_1,d_2,\dots ,d_n$ in the decreasing order

Sort the degree sequence in decreasing order

//Execute until the list not more than $n-1$

for list $i$ is not more than $n-1$

//Check whether the degree sequence $d_i$ is less than

if $d_i<0$:

//Display the output when base case is not empty list

Output is "The graph is not exist on $n$vertices"

else:

//Delete the degree sequence from the list

Remove $d_i$ from the list

//Subtract the degree sequence by 1

Decrement degree sequence $d_2,d_3,\dots ,d_{d_1+1}$by 1

//Display the output when base case is empty list

Output is "The graph is exist on $n$vertices"

Explanation:

Use the recursive procedure for given degree sequence $d_1,d_2,\dots ,d_n$ .Check whether the degree sequence contains the length of 1. Sort the degree sequence $d_1,d_2,\dots ,d_n$in the decreasing order. Verify the condition whether the degree sequence $d_i<0$. If the condition satisfies, display the graph is not exist on $n$vertices.

If the condition is not satisfied, remove $d_1$ from the sequence and subtract $d_2,\dots ,d_{d_1+1}$ by 1. Repeat the steps until the list no more than of $n-1$ Finally, the base case list is empty and displays the graph is exist on “n” vertices with degree sequence $d_1,d_2,\dots ,d_n$.

Therefore, the graph $G$ is exists on $n$ vertices with degree sequence of$d_1,d_2,\dots ,d_n$.

Complexity:

• Each unique degree order is sorted$d_1,d_2,\dots ,d_n$ .This insertion sort, on the other hand, reduces overall running time by such a factor of two$O\left(n\log n\right)$ . With each and every process, there should be at least one repetitive procedure call $d_i$ in the degree sequence takes $O{\sum }_{i=1}^{i=n}{d}_i$.

As a result, when the sorting plus recursive function calls are added together, overall total running time is $O(n\log n+{\sum }_{i=1}^{i=n}{d}_i)$.

The duration of the film is $O(n\log n+m)$ .

Therefore, The above algorithm's concurrent execution in terms of $n$ and $m={\sum }_{i=1}^{i=n}{d}_i$ is $O(n\log n+m)$.