Existence of graphs when given the degrees of all vertices

Question

My question is:

How to decide whether a graph is exist when given the degree sequence of all vertices?

This question can be easily reduced to the {0,1}-solutions of integer linear equation system, since we can let the edges to be variables and establish linear equations for each vertices associate with its degree. However, the problem to find integer solutions for linear equation system is NP-hard in general.

So, does anyone know that whether there are polynomial time algorithms to solve this problem? or to show it is NP-hard as well?

If it is not for the general graphs but planar graphs, what would be the answer?

Answer 1

I assume you mean simple graph, i.e. no loops, no multi-edges.

Here's how to solve (or die trying) a degree sequence $\mathbf d=(d_1,d_2,\ldots, d_n)$:

Assume wlog. (or sort in $O(n\ln n)$) that $d_1\le d_2\le \ldots \le d_n$. If $d_n\ge n$ there clearly is no solution and we are done. If $d_n<n$, recursively try to find a solution for $\mathbf{d'}=(d_1',d_2',\ldots, d_{n-1}')$ where $$d_k'=\begin{cases}d_k&\text{if $k<n-d_n$}\\d_k-1&\text{if $k\ge n-d_n$}\end{cases}$$ and add a new node with an edge to each of the $d_n$ last vertices.

The time complexity is $O(n^2\ln n)$, hence polynomial.

But why does this work? If there is a solution at all, then removing the $n$th vertex produces a solution to some $\mathbf d''=(d_1'',d_2'',\ldots, d_{n-1}'')$ where exactly $d_n$ of the $d_i''$ are $d_i-1$ and the rest are $d_i$. The algorithm assumes that the $d_n$ special vertices can always be picked to be those of highest degrees. So what we need is the following

Lemma. Assume there is a solution to $\mathbf d=(d_1,\ldots,d_n)$. Let $e_k=d_k$ except for two indices $i.j$, where $e_i=d_i-1$ and $e_j=d_j+1$. If $d_i>d_j$ then there also exists a solution to $\mathbf e=(e_1,\ldots, e_n)$.

Proof. Let $G$ be a solution to $\mathbf d$. If $d_j=d_i-1$, then $(d_i,d_j9=(e_j,e_i)$, i.e. swapping vertices $i$ and $j$ in $G$ gives us a solution to $\mathbf e$. If on the other hand $d_j<d_i-1$, then there exists a neighbour $v$ of $i$ that is neither $=j$ nor a neighbour of $j$. Remove the edge $iv$ and add an edee $jv$ to obtain a solution to $\mathbf e$. $_\square$

By applying the lemma repeatedly, it is possible to turn $\mathbf d''$ into $\mathbf d'$. That is, if there is any solution, then we may assume that it "comes from" the subproblem $\mathbf d'$ as in the algorithm.

Remark: The restriction to planar graphs looks less inviting, I'm afraid. One may apply some matching theory / marriage theorems, bounds by Eulers formula and the like ...