Maths WorkshopMaths problems with full solutions
Exercise 1691Combinatorics › Graph theoryL1Added 3 Nov 2026

Minimum degree and connectivity

#minimum degree#connectivity#edge connectivity

Statement

Relate minimum degree δ(G)\delta(G) to vertex connectivity κ(G)\kappa(G) and edge connectivity λ(G)\lambda(G).

Hint

Show κ(G)≤λ(G)≤δ(G)\kappa(G)\le\lambda(G)\le\delta(G).

Show solutionHide solution

Solution

λ≤δ\lambda\le\delta. Removing all edges incident to a vertex of minimum degree disconnects the graph, so λ≤δ\lambda\le\delta.

κ≤λ\kappa\le\lambda. Removing λ\lambda edges disconnecting the graph involves at most λ\lambda vertices on one side; removing those vertices disconnects.

Conclusion. κ(G)≤λ(G)≤δ(G)\kappa(G)\le\lambda(G)\le\delta(G).