why E dominates v?

Question

I analyzed the running time for Kruskal algorithm and I come up with O(ElogE+Elogv+v)

I asked my prof and he said that if the graph is very sparse with many isolated vertices V dominates E which makes sense if not then E dominates V and I can not understand why? I can give an example where graph is not sparse but still V is greater than E

Can anyone help me to clear this confusion?

Answer 1

A tree in a undirectional graph has |V|-1 edges.

Since a tree is the connected component with least edges as possible - it basically means that for each connected undirectional graph, |E| is in Omega(|V|), so |V| is dominated by |E|.

This basically means that if |E| < |V|-1 - the graph is not connected.

Now, since Kruskal algorithm is designed to find a spanning tree, you can abort the algorithm once you have found |E| < |V|-1 - there is no spanning tree at all, no point to look for one.

From this we conclude that when |E| < |V|-1, there is no point in discussing complexity of Kruskal Algorithm, and we can safely assume that |E| >= |V| -1 , so |V| is dominated by |E|.

Answer 2

Density = number of edges / number of possible edges = E / (V(V-1))/2

Let the graph be a tree E = V - 1

So V = (E + 1)

And Kruskal's complexity is

O(E log E + E log V + V) = O(E log E + E log (E + 1) + (E + 1)) = O( E log E )

So E dominates. E will dominate as long as E = O(V).