# Matthias Kriesell: Degree sequences and edge connectivity

Vir: Seminar za teorijo grafov in algoritme

**Abstract: **

For each positive integer *k*, we give a finite list *C(k)* of Bondy--Chvátal type conditions to a nondecreasing sequence *d=(d_1,...,d_n)* of nonnegative integers such that every graph on *n* vertices with degree sequence at least *d* is *k*-edge-connected. These conditions are best possible in the sense that whenever one of them fails for *d* then there is a graph on *n* vertices with degree sequence at least *d* which is not *k*-edge-connected.

We prove that *C(k)* is and must be large by showing that it contains *p(k)* many pairwise logically irredundant conditions, where *p(k)* is the number of partititons of *k*. Since, in the corresponding classic result on vertex connectivity, one needs just one such condition, this is one of the rare statements where the edge connectivity version is *much* more difficult than the vertex connectivity version. Furthermore, we demonstrate how to handle other types of edge-connectivity, as, for example, essentially *k*-edge-connectivity.

Finally, we informally describe a simple and fast procedure which generates the list *C(k)*. Specialized to *k=3*, this verifies a recent conjecture of Bauer, Hakimi, Kahl, and Schmeichel, and for *k=2* we obtain an alternative prove for their result on bridgeless connected graphs. The explicit list for *k=4* is given, too.