# 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?

• For a connected graph, the two running times you state are equivalent. May 22, 2018 at 5:18
• @YuvalFilmus That is I already said in the post. May 22, 2018 at 5:26
• So both running times are correct. May 22, 2018 at 5:51
• @YuvalFilmus My question is why connected graph of undirected graph has maximum number of vertices as $|V|^2$. May 22, 2018 at 6:04
• The maximum number of edges is $\binom{|V|}{2}$. May 22, 2018 at 6:24

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|)$.
• Thank you for your excellent answer! Then, what is the answer of binomial coefficent? Is it almost $|V|^2$ and why? If it bothers you, just skip it. It is enough to your sincere answer. May 22, 2018 at 14:39
• The binomial coefficient is roughly $|V|^2/2$. Its exact value is $|V|(|V|-1)/2$. May 22, 2018 at 14:41