Let $G$ be a graph on $n$ vertices. $G$ is allowed to have multiple edges but no loops. The degree sequence of $G$ is the tuple $(d_1,d_2,\ldots,d_n)$ with $d_1\geq d_2 \geq\cdots\geq d_n\geq 0$ obtained (inductively) as follows: $d_1$ is the highest degree of a vertex; $(d_2,\ldots,d_n)$ is the highest degree sequence in lexicographic order of a graph obtained by deleting a vertex of degree $d_1$ and its incident edges from $G$.

A tuple $D=(d_1,d_2,\ldots,d_n)$ is called graphic if there exist a graph with $n$ vertices, with possible multiple edges but no loops such that its degree sequence is $D$.

It is easy to show that $d_n=0$ for any graphic tuple. But of course there are other necessary conditions.

For instance $(2,2,0,0)$ is graphic with $G=(V,E)$, $V=\{1,2,3,4\}$, $E=\{[1−2],[1−2],[3−4],[3−4]\}$ whereas $(4,2,2,0)$ is not (there is no graph with $4$ vertices and with this degree sequence). However $(4,2,2,0,0)$ becomes graphic once the extra $0$ (corresponding to an extra vertex) is added. The example in this case is $V=\{1,2,3,4,5\}$, $E=\{[1−2],[1−2],[1−3],[1−3],[2−3],[2−3],[4−5],[4−5]\}$.

My question is the following: Is there a complete description of graphic tuples? For simple graphs this seems awfully close in flavour to the Erdös-Gallai Theorem. I was, however, not able to find a good reference online.

  • $\begingroup$ There can be more than one vertex with a maximal degree. Then what next? $\endgroup$ Oct 27, 2016 at 3:32
  • 1
    $\begingroup$ If more than one vertex has maximal degree then for each vertex $v$ of maximal degree consider the graph $G_v=G\setminus\{v\}$ and calculate its degree sequence $D_v$. Then compare the $D_v$s lexicographically and choose the $v$ with the highest $D_v$. $\endgroup$
    – Alex
    Oct 27, 2016 at 3:41
  • 1
    $\begingroup$ indeed, one could make this lexicographic decision or one may consider more than one variation of your question. The other variant would call for a study of all sequences obtained by removals of arbitrary maximal vertices (one at the time, of course). $\endgroup$ Oct 27, 2016 at 4:42
  • 1
    $\begingroup$ For simple graphs it is Erdös - Gallai theorem - why? They seem to consider sequence of degrees in the initial graph, without removing vertices. $\endgroup$ Oct 27, 2016 at 7:34
  • $\begingroup$ @FedorPetrov You're right. In the normal definition of degree sequences one does not delete vertices. But it seems awfully close in flavour. I shall edit my post accordingly. $\endgroup$
    – Alex
    Oct 27, 2016 at 8:15


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.