Degree sequence

U radu proučavamo niz stupnjeva neusmjerenog konačnog jednostavnog grafa. Navodimo dva najpoznatija kriterija koji daju nužne i dovoljne uvjete koje mora zadovoljavati niz nenegativnih cijelih brojeva da bi predstavljao niz stupnjeva nekog grafa, teorem Havela i Hakima te teorem Erdősa i Gallaia. Teorem Havela i Hakima je zasnovan na rezidualnom ostatku najvećeg elementa niza stupnjeva. Na osnovu teorema Havela i Hakima može se razviti algoritam kojim se utvrđuje predstavlja li niz nenegativnih cijelih brojeva niz stupnjeva nekog grafa. Erdős i Gallai su dali nužan i dovoljan uvjet, koji nije algoritamskog tipa, da bi niz bio grafički.This paper discusses the degree sequence of a finite simple graph. Two well-known criteria which give the necessary and sufficient conditions for a sequence of nonnegative integers to be a degree sequence of a graph have been proved, the Havel-Hakimi theorem and the ErdősGallai theorem. The Havel-Hakimi theorem is based on the residual sequence of the largest element of a degree sequence. Based on the Havel-Hakimi theorem, an algorithm can be developed to determine whether a set of nonnegative integers is a degree sequence. Erdős and Gallai have given a necessary and sufficient condition, which is not of an algorithmic type, for a sequence to be graphi