On Vertices of Degree n in Minimally n-Edge-Connected Graphs

Abstract

Let G be a minimally n-edge-connected finite simple graph with vertex number |G| ≥ 2n + 2 + [3/n] and let n ≥ 3 be odd. It is proved that the number of vertices of degree n in G is at least ((n − 1 − ∈n)/(2n + 1))|G| + 2 + 2∈n, where ∈n = (3n + 3)/(2n2 − 3n − 3), and that for every n ≡ 3 (mod 4) this lower bound is attained by infinitely many minimally n-edge-connected finite simple graphs. © 1995, Cambridge University Press. All rights reserved.