A short constructive proof of the Erd˝os–Gallaicharacterization of graphic listsAmitabha Tripathi∗, Sushmita Venugopalan†, and Douglas B. West‡September 6, 2009AbstractErd˝os and Gallai proved that a nonincreasing list (d1, . . . , dn) of nonnegative inte-gers is the list of degrees of a graph (with no loops or multi-edges) if and only if thesum is even and the list satisfiesPki=1di≤ k(k −1)+Pni=k+1min{k, di} for 1 ≤ k ≤ n.We give a short constructive proof of the characterization.AMS Subject classification: 05C07Keywords: graphic list, graphic sequence, degree sequenceA list of nonnegative integers is graphic if it is the list of vertex degrees of a graph, whereour model of graph forbids loops and repeated edges. Historically, such lists have also beencalled graphic sequences. A graph with degree list d is a realization of d.Many characterizations of graphic lists are known; Sierksma and Hoogeveen [10] list sevencriteria involving inequalities on the list elements. With additional results, these also appearin [9]. Additional characterizations are due to Havel [7] and Hakimi [5], Koren [8], andprobably others.The best-known explicit characterization is that by Erd˝os and Gallai [4]. Many proofsof it have been given, including by Berge [2] (using network flow or Tutte’s f-Factor Theo-rem), Harary [6] (a lengthy induction), Choudum [3], Aigner–Triesch [1] (using ideals in thedominance order), Tripathi–Tyagi [11] (indirect proof), etc. The purpose of this note is togive a short direct proof that constructs a graph whose degree list is the given list.∗Indian Institute of Technology, Hauz Khas, New Delhi, India, [email protected]†Rutgers University, Piscataway, NJ 08854, [email protected]. Work done while at IndianInstitute of Technology, New Delhi, India‡University of Illinois, Urbana, IL 61801, [email protected]. Research partially supported by theNational Security Agency under Award No. H98230-06-1-0065.1Theorem 1 (Erd˝os–Gallai [4]) A list (d1, . . . , dn) of nonnegative integers in nonincreas-ing order is graphic if and only if its sum is even and, for each integer k with 1 ≤ k ≤ n,kXi=1di≤ k(k − 1) +nXi=k+1min{k, di}, for 1 ≤ k ≤ n. (1)Proof. Necessity is immediate and standard: each edge is counted twice to yield even sum,and the right side is the maximum contribution to the sum of the first k degrees from edgesinduced by the corresponding vertices and edges to the remaining vertices.For sufficiency, let a subrealization of a nonincreasing list (d1, . . . , dn) be a graph withvertices v1, . . . , vnsuch that d(vi) ≤ difor 1 ≤ i ≤ n, where d(vi) denotes the degree of vi.Given a list (d1, . . . , dn) with even sum that satisfies (1), we construct a realization throughsuccessive subrealizations. The initial subrealization has n vertices and no edges.In a subrealization, the critical index r is the largest index such that d(vi) = difor1 ≤ i < r. Initially, r = 1 unless the list is all 0, in which case the process is complete.While r ≤ n, we obtain a new subrealization with smaller deficiency dr− d(vr) at vertexvrwhile not changing the degree of any vertex viwith i < r (the degree list increaseslexicographically). The process can only stop when the subrealization is a realization of d.Let S = {vr+1, . . . , vn}. We maintain the condition that S is an independent set, whichcertainly holds initially. Write vi↔ vjwhen vivj∈ E(G); otherwise, vi= vj.Case 0) vr= vifor some vertex visuch that d(vi) < di. Add the edge vrvi.Case 1) vr= vifor some i with i < r. Since d(vi) = di≥ dr> d(vr), there existsu ∈ N(vi) − N(vr), where N(z) = {y : z ↔ y}. If dr− d(vr) ≥ 2, then replace uviwith{uvr, vivr}. If dr−d(vr) = 1, then sincePdi−Pd(vi) is even there is an index k with k > rsuch that d(vk) < dk. Case 0 app lies unless vr↔ vk; replace {vrvk, uvi} with {uvr, vivr}.Case 2) v1, . . . , vr−1∈ N (vr), and d(vk) 6= min{r, dk} for some k with k > r. In asubrealization, d(vk) ≤ dk. Since S is independent, d(vk) ≤ r. Hen ce d(vk) < min{r, dk},and Case 0 applies unless vk↔ vr. Since d(vk) < r, there exists i with i < r such thatvk= vi. Since d(vi) > d(vr), there exists u ∈ N(vi) − N(vr). Replace uviwith {uvr, vivk}.Case 3) v1, . . . , vr−1∈ N(vr), and vi= vjfor some i and j with i < j < r. Case 1applies unless vi, vj∈ N(vr). Since d(vi) ≥ d(vj) > d(vr), there exist u ∈ N(vi) − N(vr) andw ∈ N(vj) − N(vr) (possibly u = w). Since u, w /∈ N(vr), Case 1 applies u nless u, w ∈ S.Replace {uvi, wvj} with {vivj, uvr}.If none of these Cases apply, then v1, . . . , vrare pairwise adjacent, and d(vk) = min{r, dk}for k > r. Since S is indepen dent,Pri=1d(vi) = r(r−1)+Pnk=r+1min{r, dk}. By (1),Pri=1diis bounded by the right side. Hence we have already eliminated the deficiency at vertex r.Augment r and continue. 2The proof can be implemented as an algorithm to construct a realization of the degreelist. Since the subrealization improves lexicographically with each step, the number of stepsis at mostPdi. To bound the time for each step, we maintain th e graph as lists of neighborsand non-neighbors for each vertex. We lo ok through the non-neighbors of vrto see if Case 0or Case 1 applies. To apply Case 1 we access lists twice to find u and possibly check degreesof the high-indexed vertices to find k. The implementation of Cases 2 and 3 involve similaroperations. Each step is implemented using a constant number of set-membership queries.Thus the running time is naively at most O(nPdi). With clever maintenance of sets u singsophisticated data structures involving trees, the factor of n can be reduced.References[1] M. Aigner and E. Triesch, Realizability and uniqueness in graphs, Discrete Math. 136 (1994),3–20.[2] C. Berge, Graphs and Hypergraphs. (North-Holland, 1973).[3] S. A. Choudum, A simple proof of the Erd˝os–Gallai theorem on graph sequences, Bull. Austral.Math. Soc. 33 (1986), 67–70.[4] P. Erd˝os and T. Gallai, Graphs with prescribed degrees of vertices (Hungarian), Mat. Lapok11 (1960), 264–274.[5] S. L. Hakimi, On the realizability of a set of integers as degrees of the vertices of a graph,SIAM J. Applied Math. 10 (1962), 496–506.[6] F. Harary, Graph theory, (Addison-Wesley, 1969).[7] V. Havel, A remark on the existence of finite graphs (Czech.)ˇCasopis Pˇest. Mat 80 (1955),477–480.[8] M. Koren, Extreme degree sequences of simple graphs, J. Combin. Theory B 15 (1973),