How to know if a graph exists based on the list of degrees

668 Views Asked by At

I was wondering if that is a way to know if a graph exists based on a given sequence of degrees. Example: Is possible do draw a simple graph with 6 vertex and sequence of degrees of 1;2;3;4;5;5.

2

There are 2 best solutions below

0
On

Not possible: the two vertices of degree $5$ would need to be connected to all other vertices, including the vertex of degree $1$.

0
On

I don't want to give you the answer but can you apply the following theorem to your example? This works in every scenario where you have a degree sequence.

The Erdos-Gallai Theorem which states (according to Wikipedia):

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 every $k$ in $1\leq k\leq n$.