Q:

Maximum number of vertices in undirected graph

I'm studying about time complexity of Kruskal's algorithm.
But there are two opinions to express time complexity as $O(|E|\lg|E|), O(|E|\lg|V|)$.
I know $O(|E|\lg|E|)$ is occurred from sorting by non-decreasing order of vertices.
But I don't understand of $O(|E|\lg|V|)$. This answer explains by $|E|\le|V|^2$, however from my knowledge, maximum number of vertices in undirected graph is $|E|\le\frac{|V|(|V|-1)}{2}$.
What is right time complexity for Kruskal's algorithm? 

A:

Kruskal's algorithm is only applied to connected graphs. These have at least $|V|-1$ edges. On the other hand, the complete graph has $\binom{|V|}{2}$ edges, and so
$$
|V|-1 \leq |E| \leq \binom{|V|}{2}.
$$
The left-hand side is $\Omega(|V|)$ and the right-hand side is $O(|V|^2)$. Therefore $\log |E| = \Theta(\log |V|)$. For this reason, the two quoted running times $O(|E| \log |E|)$ and $O(|E| \log |V|)$ are completely identical — on connected graphs, an algorithm has running time $O(|E| \log |E|)$ iff it has running time $O(|E| \log |V|)$.

