Why can't edges be fewer than vertices in Graph theory?

user_16864917 0
Viewed 44

Upon analyzing Kruskal's Algorithm, Kruskal's Algorithm is apparently considered to be E log E because "for an MST to exist, E can't be smaller than V so assume it dominates"

However, the simplest tree input would have more vertices than edges...

snippet of the lecture slide I was looking at

Can someone tell me why "for an MST to exist, E can't be smaller than V so assume it dominates"

hence run time is ElogE not ElogE + V

kruskals-algorithm minimum-spanning-tree graph-theory big-o algorithm
1 Answers

The term "smaller" here should be understood in terms of computational complexity, or big-O.

For an MST to exist, E must be greater than or equal to V - 1. While you are right that this means E can be less than V, it puts it in the same complexity class.

For graphs that have an MST, E can be O(V), or O(V^2), or anything in between.

user_87425050
Related