On Vertices of Degree n in Minimally n -Edge-Connected Graphs
W. Mader · Combinatorics Probability Computing · 1995
Let G be a minimally n -edge-connected finite simple graph with vertex number | G | ≥ 2 n + 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 )/(2 n + 1))| G | + 2 + 2∈ n , where ∈ n = (3 n + 3)/(2 n 2 − 3 n − 3), and that for every n ≡ 3 (mod 4) this lower bound is attained by infinitely many minimally n -edge-connected finite simple graphs.