In an undirected graph with n vertices, when the number of edges k >; (N- 1)(N-2)/2, proved to be a connected graph, and proved as follows:

Suppose there is an undirected graph with n nodes and k edges, which is disconnected, that is, suppose it has two connected branches (the more connected branches, the fewer edges, so we only need to discuss the case of two connected branches), and suppose that one connected branch has s nodes and the other connected branch has N-S, it is easy to know that the maximum number of edges of this graph is.

(s-1) (s)/2+(n-s) (n-s-1)/2, (every connected branch is a complete graph), and the maximum number of edges is n× n-(2s+1)+S. =/. (N- 1)(N-2)/2 = N×N-3N+2 & gt； =N×N-(2S+ 1)+S×S, so there must be an edge between these two connected branches, which proves the conclusion.