Timeline for Every simple undirected graph with more than $(n-1)(n-2)/2$ edges is connected

4 events

when toggle format	what		by	license	comment
Dec 9, 2015 at 7:42	comment	added	David Richerby		Trees are connected graphs with substantially fewer than $C(n-1,2)$ edges. I guess you meant that every graph with more than $C(n-1,2)$ edges must be connected. But even that doesn't quite work because all you've shown is that a graph with that many edges can't have an isolated vertex: it's possible to be disconnected but have no isolated vertices. In any case, the question isn't really asking for a proof that every graph with more than $C(n-1,2)$ edges is connected: it's asking why $n-1$ edges isn't enough.
Dec 9, 2015 at 7:14	review	Late answers
Dec 9, 2015 at 7:42
Dec 9, 2015 at 7:00	review	First posts
Dec 9, 2015 at 7:38
Dec 9, 2015 at 6:57	history	answered	Yugandhar Reddy Akkisetty	CC BY-SA 3.0