A remark on the number of vertices of degree k in a minimally k-edge-connected graph

AbstractLet G be a minimally k-edge-connected simple graph and vk(G) be the number of vertices of degree k in G. Mader (1974) proved that (i) vk(G) ⩾ ⌊(|G|−1)(2k + 1)⌋ + k + 1 for even k, and (ii) vk(G)⩾⌊|G|(k + 1)⌋ + k for odd k⩾5 and vk(G)⩾⌊2|G|(k + 1)⌋ + k − 2 for odd k⩾7, where |G| denotes the number of vertices of G. In this paper we slightly improve the result for k being even, i.e., vk(G)⩾⌊|G|(k + 1)⌋ + k if k⩾4 and vk(G)⩾⌊2|G|(k + 1)⌋ + k−2 if k⩾10