Post by maholiza on Dec 2, 2014 23:29:36 GMT
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.
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.
