Vertices of degree k in edge-minimal, k-edge-connected graphs

2009/05/07 by Kingsford, Carl, Marçais, Guillaume
#05C40 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.0905.1064

Abstract

Halin showed that every edge minimal, k-vertex connected graph has a vertex of degree k. In this note, we prove the analogue to Halin's theorem for edge-minimal, k-edge-connected graphs. We show there are two vertices of degree k in every edge-minimal, k-edge-connected graph.

Related

• Ends and vertices of small degree in infinite minimally k-(edge)-connected graphs
• Note on minimally k-connected graphs
• Edge-connectivity keeping trees in k-edge-connected graphs
• Super-minimally 3-connected graphs
• Minimal Connectivity