Exercise 1691Combinatorics › Graph theoryL1Added 3 Nov 2026
Minimum degree and connectivity
#minimum degree#connectivity#edge connectivity
Statement
Relate minimum degree to vertex connectivity and edge connectivity .
Hint
Show .
Show solutionHide solution
Solution
. Removing all edges incident to a vertex of minimum degree disconnects the graph, so .
. Removing edges disconnecting the graph involves at most vertices on one side; removing those vertices disconnects.
Conclusion. .