Guichard-Combinatorics-Graph-Theory · Problem 5.7.4
Graph Theory
Mathematics — Probability · connectivity
Problem
Recall that a graph is k-regular if all the vertices have degree k. What is the smallest integer k that makes this true:
If G is simple, has n vertices, m≥k, and G is m-regular, then G is connected.
(Of course k depends on n.)