Notice that the value of (n - k)(n - k + 1)/2 decreases when k becomes larger. If a simple graph with n vertices is not connected, it will contain at least 2 connected components. Therefore, the value of k in previous problem is k>2. Then, there are at most (n - 2)(n - 2 + 1)/2 edges in the graph, which contradicts to the condition that the graph has more than (n - 1)(n - 2)/2 edges. Therefore, the graph is connected.