10
$\begingroup$

I'm trying to make a list of ways to tell if a given degree sequence is impossible. For example $3,1,1$ is not possible because there are only 3 vertices in total so one can't have degree 3.

The list so far

  • vertices has degree equal to or larger than number of vertices
  • sum of degrees is odd
  • for n vertices if one has degree n-1 and another has degree 0
  • for n vertices the sum of the degrees cannot be greater than $n(n-1)$ because this would be have more edges than a complete graph
$\endgroup$
  • 4
    $\begingroup$ Please remove 2 from denominator in 4 th point $\endgroup$ – Believer Sep 12 '18 at 17:32
  • $\begingroup$ do you think? I'm not sure about that @Believer $\endgroup$ – Marine Galantin Jan 21 at 18:10
  • $\begingroup$ @Marine Galantin, yes I am sure.Take complete graph on 4 vertices as a counter example.Also read answer by Sanjeet kumar $\endgroup$ – Believer Jan 23 at 17:19
  • $\begingroup$ Well it has 6 edges? Because the edges are simple and not in both direction $\endgroup$ – Marine Galantin Jan 23 at 17:21
6
$\begingroup$

The Erdős–Gallai theorem completely characterizes the possible degree sequences for simple graphs.

It is stated by Wikipedia as:

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$.

$\endgroup$
6
$\begingroup$

Three is Havel–Hakimi algorithm It is stated by Wikipedia as:

The algorithm The algorithm is based on the following theorem. Let $$S=(d_{1},\dots ,d_{n})$$ be a finite list of nonnegative integers that is nonincreasing. List S is graphic if and only if the finite list $$S'=(d_{2}-1,d_{3}-1,\dots ,d_((d_{1}+1))-1,d_((d_{1}+2)),\dots ,d_{n})$$ has nonnegative integers and is graphic. If the given list S graphic then the theorem will be applied at most $n-1$ times setting in each further step $$S:=S'$$. Note that it can be necessary to sort this list again. This process ends when the whole list S' consists of zeros. In each step of the algorithm one constructs the edges of a graph with vertices $$v_{1},\cdots ,v_{n}$$, i.e. if it is possible to reduce the list $S$ to $S'$, then we add edges $$\{v_{1},v_{2}\},\{v_{1},v_{3}\},\cdots ,\{v_{1},v_((d_{1}+1))\}$$. When the list S cannot be reduced to a list S' of nonnegative integers in any step of this approach, the theorem proves that the list S from the beginning is not graphic.

see also
What condition need to be imposed on Havel-Hakimi theorem to check for connected graph?

$\endgroup$
3
$\begingroup$

The most general version is the Erdos-Gallai theorem, referred to in this MathOverflow post.

$\endgroup$
1
$\begingroup$

Fourth point is not valid. n(n-1)/2 is number of edges of completed graph not the degree sum. Degree sum can be n(n-1) at most.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.