A short constructive proof of the Erdős-Gallai characterization of graphic lists. (English) Zbl 1209.05058
Summary: P. Erdős and T. Gallai [“Graphs with prescribed degrees of vertices,” Mat. Lapok 11, 264–274 (1961; Zbl 0103.39701)] proved that a nonincreasing list \((d_{1},\dots ,d_n)\) of nonnegative integers is the list of degrees of a graph (with no loops or multi-edges) if and only if the sum is even and the list satisfies
\[
\sum _{i=1}^k d_i \leq k(k-1)+\sum _{i=k+1}^n \min \{k,d_i\}\qquad\text{for }1\leq k\leq n.
\]
We give a short constructive proof of the characterization.
MSC:
| 05C07 | Vertex degrees |
Citations:
Zbl 0103.39701References:
| [1] | Aigner, M.; Triesch, E., Realizability and uniqueness in graphs, Discrete Math., 136, 3-20 (1994) · Zbl 0817.05048 |
| [2] | Berge, C., Graphs and Hypergraphs (1973), North-Holland · Zbl 0483.05029 |
| [3] | Choudum, S. A., A simple proof of the Erdős-Gallai theorem on graph sequences, Bull. Austral. Math. Soc., 33, 67-70 (1986) · Zbl 0571.05048 |
| [4] | Erdős, P.; Gallai, T., Graphs with prescribed degrees of vertices (Hungarian), Mat. Lapok, 11, 264-274 (1960) · Zbl 0103.39701 |
| [5] | Hakimi, S. L., On the realizability of a set of integers as degrees of the vertices of a graph, SIAM J. Appl. Math., 10, 496-506 (1962) · Zbl 0109.16501 |
| [6] | Harary, F., Graph Theory (1969), Addison-Wesley · Zbl 0797.05064 |
| [7] | Havel, V., A remark on the existence of finite graphs (Czech.), Časopis Pěst. Mat., 80, 477-480 (1955) · Zbl 0068.37202 |
| [8] | Koren, M., Extreme degree sequences of simple graphs, J. Combin. Theory B, 15, 213-224 (1973) · Zbl 0268.05123 |
| [9] | Mahadev, N. V.R.; Peled, U. N., Threshold graphs and related topics, (Annals of Discrete Math., vol. 56 (1995), North-Holland) · Zbl 0852.05001 |
| [10] | Sierksma, G.; Hoogeveen, H., Seven criteria for integer sequences being graphic, J. Graph Theory, 15, 223-231 (1991) · Zbl 0752.05052 |
| [11] | Tripathi, A.; Tyagi, H., A simple criterion on degree sequences of graphs, Discrete Appl. Math., 156, 3513-3517 (2008) · Zbl 1168.05307 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
