{"id":8045,"date":"2014-11-13T07:40:14","date_gmt":"2014-11-13T06:40:14","guid":{"rendered":"http:\/\/djalil.chafai.net\/blog\/?p=8045"},"modified":"2025-05-03T12:53:49","modified_gmt":"2025-05-03T10:53:49","slug":"erdos-gallai-theorem-on-degree-sequence-of-graphs","status":"publish","type":"post","link":"https:\/\/djalil.chafai.net\/blog\/2014\/11\/13\/erdos-gallai-theorem-on-degree-sequence-of-graphs\/","title":{"rendered":"Erd\u0151s-Gallai theorem on degree sequence of graphs"},"content":{"rendered":"
\"Cubic<\/a>
Cubic graph (source: Wikipedia)<\/figcaption><\/figure>\n

In a finite graph \\( {G=(V,E)} \\), the degree of a vertex \\( {i\\in V} \\) is the number \\( {d(i)} \\) of vertices connected directly to \\( {i} \\) by an edge:<\/p>\n

\\[ d(i)=\\mathrm{card}\\{j\\in V:\\{i,j\\}\\in E\\}. \\]<\/p>\n

We say that the graph \\( {G} \\) is \\( {d} \\)-regular<\/b> where \\( {d\\geq0} \\) is a fixed integer when \\( {d(i)=d} \\) for all \\( {i\\in V} \\). The \\( {0} \\)-regular graphs are formed by isolated vertices and do not have any edge. The \\( {1} \\)-regular graphs are formed by disconnected edges. The \\( {2} \\)-regular graphs are formed by disconnected cycles and infinite chains.<\/p>\n

The Erd\u0151s-Gallai theorem<\/b> states that for any integers \\( {n\\geq1} \\) and \\( {d_1\\geq\\cdots\\geq d_n\\geq0} \\), there exists a graph with \\( {n\\geq1} \\) vertices with respective degrees \\( {d_1,\\ldots,d_n} \\) if and only if the following two conditions hold true:<\/p>\n

    \n
  1. the integer \\( {d_1+\\cdots+d_n} \\) is even;<\/li>\n
  2. for any \\( {1\\leq k\\leq n} \\), \\( {d_{1}+\\cdots+d_{k}\\leq k(k-1)+ \\min(k,d_{k+1})+\\cdots+\\min(k,d_{n})} \\).<\/li>\n<\/ol>\n

    In this case we say that \\( {d_1,\\ldots,d_n} \\) is graphic<\/b>. The fact that the sum \\( {d_1+\\cdots+d_n} \\) is even comes from the fact that each edge counts twice. The quantity \\( {k(k-1)+\\min(d_{k+1},k)+\\cdots+\\min(d_{n},k)} \\) is the maximum contribution to \\( {d_1+\\cdots+d_k} \\) of the edges connected to the vertices \\( {1} \\) to \\( {k} \\): at most \\( {\\binom{k}{2}=k(k-1)\/2} \\) edges (count twice) between the vertices \\( {1} \\) to \\( {k} \\), and at most \\( {\\min(k,d_{k+i})} \\) edges between the vertex \\( {i>k} \\) and the vertices \\( {1} \\) to \\( {k} \\). We say that \\( {d_1,\\ldots,d_n} \\) is the degree sequence<\/b> of the graph.<\/p>\n

    In particular, for a \\( {d} \\)-regular graph with \\( {n} \\) vertices, we have \\( {d_1=\\cdots=d_n=d} \\) and the Erd\u0151s-Gallai theorem states that \\( {d} \\) is even and \\( {kd\\leq k(k-1)+(n-k)\\min(k,d)} \\) for every \\( {1\\leq k\\leq n} \\), which gives in particular \\( {d\\leq n-1} \\) and equality is achieved for the complete graph.<\/p>\n

    The Erd\u0151s-Gallai theorem was proved by Paul Erd\u0151s<\/a> and Tibor Gallai<\/a> in a paper published in 1960 in hungarian. Nowadays, many proofs are available, including one<\/a> by Claude Berge<\/a>. A short and constructive proof can be found in a paper<\/a> by Amitabha Tripathi, Sushmita Venugopalan, and Douglas West.<\/p>\n

    Further reading.<\/b> Lecture notes on random graphs by Remco van der Hofstad<\/a>, and by Charles Bordenave<\/a>, none of which contains a proof of the Erd\u0151s-Gallai theorem.<\/p>\n","protected":false},"excerpt":{"rendered":"

    In a finite graph \\( {G=(V,E)} \\), the degree of a vertex \\( {i\\in V} \\) is the number \\( {d(i)} \\) of vertices connected…<\/p>\n

    Continue readingErd\u0151s-Gallai theorem on degree sequence of graphs<\/span><\/a><\/div>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"iawp_total_views":884},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts\/8045"}],"collection":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/comments?post=8045"}],"version-history":[{"count":8,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts\/8045\/revisions"}],"predecessor-version":[{"id":21940,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts\/8045\/revisions\/21940"}],"wp:attachment":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/media?parent=8045"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/categories?post=8045"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/tags?post=8045"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}