Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2024/ii/paper-3/17i/a/solution

Repeatedly delete a vertex whose current degree is less than . If every vertex were deleted, charge each edge to the endpoint deleted first. At each deletion fewer than remaining edges are charged, so the original graph would have fewer than edges, contradicting average degree at least . The nonempty graph left by the process has minimum degree at least .

New to topics? Read the docs here!