Given is a weighted complete graph where every weigth is a positive ineger. Let n be the amount of vertices.
I have to prove that the number of edges of a minimum spanning tree of that graph is equal to n-1.
$\endgroup$1 Answer
$\begingroup$A spanning tree of a connected graph $G$ by definition is a tree whose vertex set is all of $V(G)$. All trees $T$ satisfy the equation $E(T) = V(T) -1$. Let $V(G) =n$.
Therefore, if $T$ is spanning tree of $G$, $T$ has $E(T) = V(T) -1 = V(G) -1 = n-1$.
$\endgroup$
