# Smallest Connected Graph for Given Degree Sequence

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?

• in what sense can you talk about the smallest graph here? All such graphs have the same number of vertices and edges. Jul 31, 2014 at 20:31
• regarding the uniqueness, very few graphs are characterized by their degree sequences. E.g. cubic graphs (all $d_k=3$) on $n$ vertices form a very big family... Jul 31, 2014 at 20:34
• smallest connected can be both smallest vertex connected and smallest edge connected.
– user39815
Jul 31, 2014 at 20:39
• I don't understand. The number of vertices and the number of edges are already GIVEN! Jul 31, 2014 at 20:43
• ok, i edited the question as to make it clear here. Jul 31, 2014 at 21:11

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.