6 System of distinct representatives 6.8 ***Shannon rate of communication***6.10 ***Equivalent theorems to Hall’s matching theorem and more applications***

6.9 Erdös-Gallai Theorem

A list of non-negative integers $(d_{1},\ldots,d_{n})$ is said to be graphic if these are vertex degrees of a $n$ -vertex simple graph. We present the famous theorem giving a necessary and sufficient condition for existence of simple graphs with a given degree sequence. We have seen such a condition for trees already in Theorem 4.6.

Theorem 6.30 (Erdös-Gallai Theorem, 1960 ).

A list of non-negative integers $(d_{1},\ldots,d_{n})$ in nonincreasing order is graphic iff $\sum_{i}d_{i}$ is even and for all $1\leq k\leq n$ , we have that

\sum_{i=1}^{k}d_{i}\leq k(k-1)+\sum_{i=k+1}^{n}\min\{d_{i},k\}.

We present the recent proof due to [Tripathi 2010]. One another proof using Tutte’s $f$ -factor theorem (Theorem 6.27) can be found in [West 2001, Exercise 3.3.29]. There is also a simple proof in [Choudum 1986].

We call a graph $G$ on vertices $v_{1},\ldots,v_{n}$ , is said to be a subrealization of a nonincreasing list $(d_{1},\ldots,d_{n})$ if $d(v_{i})\leq d_{i}$ for all $1\leq i\leq n$ . For a subrealization, we say $r$ is the critical index if $d(v_{i})=d_{i}$ for $1\leq i<r$ and it is the largest such index. The sufficiency part (and the non-trivial one) of the proof proceeds as follows : We start with a subrealization with $n$ vertices and no edges. Assuming $d_{1}\neq 0$ , we set $r=1$ . When $r\leq n$ , we do not change the degree of $r$ but try to increase the degree of vertex $v_{r}$ and reduce the deficiency $d_{r}-d(v_{r})$ .

Proof.

The necessity is argued as follows : Evenness is trivial. If we look at the sum of the degrees of the largest $k$ vertices, then the edges are either among the $k$ vertices or to outside. The edges among the $k$ vertices are counted twice and hence at most twice that of $K_{k}$ i.e., $k(k-1)$ . The edges from $1,\ldots,k$ to $i$ for $i>k$ is at most $\min\{d_{i},k\}$ .

Now, we prove the sufficiency as described above : Given critical index $r$ , define $S=\{v_{r+1},\ldots,v_{n}\}$ . Our construction shall give that $S$ is an independent set at every step. This is true for $r=1$ .

•

Case 0 : $v_{r}\nsim v_{i}$ for some $v_{i}$ such that $d(v_{i})<d_{i}$ . Add edge $(v_{i},v_{r})$ .
•

Case 1 : $v_{r}\nsim v_{i}$ for some $i<r$ . Since $d(v_{i})=d_{i}\geq d_{r}>d(v_{r})$ , there exists $u\sim v_{i},u\nsim v_{r},u\neq v_{r}$ . If $d_{r}-d(v_{r})\geq 2$ , replace $(u,v_{i})$ with $(u,v_{r}),(v_{i},v_{r})$ . If $d_{r}-d(v_{r})=1$ , then since $\sum_{i}(d_{i}-d(v_{i}))$ is even, there is an index $k>r$ such that $d(v_{k})<d_{k}$ . Either add edge $(v_{r},v_{k})$ if the edge is not present and if not replace $(u,v_{i}),(v_{r},v_{k})$ with $(u,v_{r}),(v_{i},v_{r})$ .
•

Case 2: $v_{1},\ldots,v_{r-1}\in N(v_{r})$ and $d(v_{k})\neq\min\{r,d_{k}\}$ for some $k>r$ . Since $d(v_{k})\leq d_{k}$ and $S$ is independent, so $d(v_{k})\leq r$ . Thus, we have that $d(v_{k})<\min\{r,d_{k}\}$ . If $v_{r}\nsim v_{k}$ , we can use Case 0. If not, since $d(v_{k})<r$ , there exists $i<r$ such that $v_{k}\nsim v_{i}$ . Since $d(v_{i})=d_{i}\geq d_{r}>d(v_{r})$ , there exists $u\sim v_{i},u\nsim v_{r},u\neq v_{r}$ . Remove $(u,v_{i})$ and add $(u,v_{r}),(v_{i},v_{k})$ .
•

Case 3: $v_{1},\ldots,v_{r-1}\in N(v_{r})$ and $v_{i}\nsim v_{j}$ for some $i<j<r$ : Since $d(v_{i})\geq d(v_{j})>d(v_{r})$ , we have that there exists $u\sim v_{i},u\nsim v_{r},u\neq v_{r}$ and $w\sim v_{j},u\nsim v_{r},w\neq v_{r}$ . It is possible that $u=w$ . If $u,w\in S$ , then delete $(u,v_{i}),(w,v_{j})$ and replace with $(v_{i},v_{j}),(u,v_{r})$ . If $u\notin S$ or $w\notin S$ , apply the arguments as in Case 1.

Suppose that none of the above cases apply. Since Case 1 doesn’t apply, $v_{1},\ldots,v_{r-1}\in N(v_{r})$ and since Case 3 also doesn’t apply, $v_{1},\ldots,v_{r}$ are all pairwise adjacent. Case 2 also doesn’t apply and hence $d(v_{k})=\min\{r,d_{k}\}$ for all $k>r$ . Since $S$ is independent, we have that $\sum_{i=1}^{r}d(v_{i})=r(r-1)+\sum_{i=r+1}^{n}\min\{r,d_{k}\}$ and hence $\sum_{i=1}^{r}(d_{i}-d(v_{i}))\leq 0$ by the Erdös-Gallai condition. Thus, we get that $d(v_{i})=d_{i}$ for all $1\leq i\leq r$ and we have eliminated deficieny at $r$ . We can now increase $r$ by $1$ and continue with the procedure as above.

∎

6.9 ***Erdös-Gallai Theorem***

Theorem 6.30 (Erdös-Gallai Theorem, 1960 ).

Proof.

6.9 Erdös-Gallai Theorem