For a given integer sequence $(d_1, d_2,…,d_n)$, a natural question is if such a sequence is graphical, i.e. is a degree sequence of some graph. According to Erdős–Gallai theorem, A sequence of non-negative integers $d_1\geq\cdots\geq d_n$ can be represented as the degree sequence of a finite simple graph on $n$ vertices if and only if $d_1+\cdots+d_n$ is even and
$\sum^{k}_{i=1}d_i\leq k(k-1)+ \sum^n_{i=k+1} \min(d_i,k)$
holds for $1\leq k\leq n.$
My questions are
(1) If Erdős–Gallai theorem holds, what is the condition that this graph is unique?
(2) If those graphs are not unique, how to find a connected graph with smallest connectivity among them?
Best Answer
A theorem of Hakimi says that any pair of degree-equivalent graphs can be obtained one from the other by a sequence of "elementary $2$-switchings" (probably known under many other names), which involve the subgraph switch on the subgraph induced by four vertices, as illustrated in one instance below.
So whatever you seek to minimize (cf. the comments), likely it could be pursued by searching for the minimum via these $2$-switchings.