Combinatorics and Graph Theory · Problem 5.7.1

Graph Theory — David Guichard

Mathematics — Combinatorics · connectivity

Problem

Suppose a simple graph GG on n≥2n \geq 2 vertices has at least (n−1)(n−2)2+1\dfrac{(n-1)(n-2)}{2} + 1 edges. Prove that GG is connected.

Browse the problem library