1. Yes. If T is a spanning tree that doesn't contain e=(u,v), there must be a path from u to v in T, so remove one edge on that path and add e; this will create a new spanning tree T' that connects all the vertices, and is cheaper than T. So, T couldn't have been a minimal spanning tree. Comment: Saying "Kruskal's algorithm will start by picking e first, so its output will definitely contain e." is not a valid proof. There may be multiple minimal spanning trees (all with the same cost). It's not immediately obvious whether all of them be generated by Kruskal's algorithm; if Kruskal's algorithm can only generate a subset of them, then this doesn't prove that they'll all contain e. Answers that try to reason about shortest paths are unlikely to be correct, as path lengths don't really matter (it doesn't matter what the shortest path from u to v is). It's not correct to say that the edge (u,v) is shorter than the length of the path from u to v through the MST, so we have a lower cost; what matters is not the total cost of the length of the path from u to v, but rather that each edge along that path has higher cost than e. 2. Using the inequality 1 + x <= e^x, we can write 1.5 = 1 + 0.5 < e^0.5 = sqrt(e).