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.
2026-04-24 16:09:31.1777046971
On
How to know if a graph exists based on the list of degrees
668 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
2
There are 2 best solutions below
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$.
Not possible: the two vertices of degree $5$ would need to be connected to all other vertices, including the vertex of degree $1$.