Basic Doubt in spanning tree complexity

Question

Let us say Simple graph has V vertices and E edges.

Now i am trying to find relation between E and V.

If it is a complete graph ,then E=V(V-1)/2,

=>   E=$c.V^2$

=>   E=$O(V^2)$   

=> taking log of both sides.

=>   $\log E$=$O(\log V)$------------------ (1)

Now in case we are fining spanning tree from graph ,we now the number of edges will be minimum V-1 in graph.So i can say

V-1<=E

V=O(E)

=> taking log of both sides.

=>$\log V$=$O(\log E)$------------------ (2)

So ,both the equations are coming valid. So is can if i say,combing both the equation i can say.

$\log E$ =theta$(\log V)$.------------------(3)

Can someone confirm if the 1 ,2  and the result of them i.e the 3rd equation is valid ?

Answer 1

The loophole in this analysis is a graph may or may not have spanning trees..

In this regard (if a graph is devoid of spanning trees) , the number of edges may be less than (v-1) [ approximately close to null graph].In this case equation (2) will become false..

Hence equation (3) will not hold as well..

But E <= V(V-1)/2 is a sure thing for a simple graph..

Hence equation (1) is correct.

Comments

While analyzing the complexity of prims and kruskal's, does equation 2 holds?Because if i am finding spanning tree complexity then graph must have atleast v-1 edges.Is this correct assumption?

---

But we apply spanning tree algo in graphs na..The result is of course a spanning tree if it exists or it may not exist as well..[In that case we use the term "spanning forest"]..The assumption that a graph must have at least v-1 edges is wrong.

---

Yeah.Got that.thanks