Degree sequences and edge connectivity (Q1688269)

For each positive integer \(k\), one can associate a finite list \(C\)(\(k\)) of Bondy-Chvátal type conditions on a nondecreasing sequence \(d=(d_1,\dots ,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. In this connection, the author proves that \(C(k)\) is and must be large by showing that it contains \(p(k)\) many logically irredundant conditions, where \(p(k)\) is the number of partitions of \(k\). Furthermore, he demonstrates how to handle other types of edge-connectivity, such as, for example, essential \(k\)-edge-connectivity. It is also proved that any sublist equivalent to \(C(k)\) has length at least \(p(k)\), where \(p(k)\) is the number of partitions of \(k\), which is in contrast to the corresponding classic result on vertex connectivity where one needs just one such condition. Furthermore,he demonstrates how to handle other types of edge-connectivity, such as, for example, essential \(k\)-edge-connectivity. Finally, he informally describes a simple and fast procedure which generates the list \(C(k)\). Specialized to \(k=3\), this verifies a conjecture of \textit{D. Bauer} et al. [Networks 54, No. 2, 95--98 (2009; Zbl 1207.05109)].