minimum spanning tree

given an undirected, connected and weighted graph $\text{[math]}$ . let $\text{[math]}$ be a spanning tree of $\text{[math]}$ . the weight of $\text{[math]}$ is the sum of weights of its edges. i.e.
$\text{[math]}$ the tree $\text{[math]}$ is a minimum spanning tree if for every other spanning tree $\text{[math]}$ of $\text{[math]}$ , the following is true:
$\text{[math]}$

a graph may have multiple mst's

let $\text{[math]}$ be an undirected simple non-negatively weighted graph. let $\text{[math]}$ be a simple cycle in $\text{[math]}$ . let $\text{[math]}$ be the edge with the absolutely biggest weight in the cycle $\text{[math]}$ . then there isnt an mst in $\text{[math]}$ that contains $\text{[math]}$ .

assume in contradiction that there exists an mst $\text{[math]}$ that contains $\text{[math]}$ . according to lem-spantree-1: upon the removal of $\text{[math]}$ from $\text{[math]}$ we get a cut. $\text{[math]}$ and $\text{[math]}$ are found on different sides of the cut. we go through $\text{[math]}$ from $\text{[math]}$ to $\text{[math]}$ , at some point we have to go through a cut edge $\text{[math]}$ (one partition on the side of $\text{[math]}$ and the other on the side of $\text{[math]}$ ) so $\text{[math]}$ . upon the addition of $\text{[math]}$ we get another mst $\text{[math]}$ according to lem-spantree-1.
$\text{[math]}$ which results in a contradiction with the fact that $\text{[math]}$ is an mst

let $\text{[math]}$ be an undirected connected non-negatively weighted simple graph whose weights are different from one another, let $\text{[math]}$ be the edges with the smallest, biggest weights, respectively, prove:

in each mst $\text{[math]}$ has to appear
prove/disprove $\text{[math]}$ has to appear/not in every mst

assume in contradiction that $\text{[math]}$ is an mst such that $\text{[math]}$ , according to lem-spantree-2, upon the addition of $\text{[math]}$ to $\text{[math]}$ we get a single cycle. upon the removal of any edge $\text{[math]}$ from the cycle we again get an mst.
we know $\text{[math]}$ because all of the weights are different
$\text{[math]}$ which means $\text{[math]}$ which is a contradiction because $\text{[math]}$ is supposed to be an mst

let $\text{[math]}$ be an undirected connected non-negatively weighted graph in which each edge has a different weight and let $\text{[math]}$ be the edge with the biggest weight, then:
$\text{[math]}$ doesnt belong to any cycle $\text{[math]}$ $\text{[math]}$ is in every mst

we prove the implication from right to left, i.e. $\text{[math]}$ is in every mst $\text{[math]}$ $\text{[math]}$ doesnt belong to any cycle
assume $\text{[math]}$ belongs to every mst, let $\text{[math]}$ be an mst of $\text{[math]}$ . we know $\text{[math]}$
assume in contradiction $\text{[math]}$ where $\text{[math]}$ is a cycle
according to [[blk:minimum_spanning_tree_lemma_3][lemma 3]] this is a contradiction

we prove the implication from left to right
assume $\text{[math]}$ belongs to no cycles.
assume in contradiction that there exists an mst $\text{[math]}$ such that $\text{[math]}$ . according to lem-spantree-2 upon the addition of $\text{[math]}$ to $\text{[math]}$ we get a cycle, so we've arrived at a contradiction

given $\text{[math]}$ is an undirected non-negatively weighted graph. let $\text{[math]}$ be 2 mst's of $\text{[math]}$ . then there exists a sequence of mst's $\text{[math]}$ and between every 2 adjacent mst's and its possible to go from one to the other by adding an edge and removing another of the same weight. there exists an mst $\text{[math]}$ that is received from $\text{[math]}$ by addition/removal of edges of the same weight and $\text{[math]}$ is closer to $\text{[math]}$ than $\text{[math]}$ (by length not weight)

a lemma built on this definition

if $\text{[math]}$ are mst's of $\text{[math]}$ then $\text{[math]}$

let $\text{[math]}$ be a spanning tree of $\text{[math]}$ , then $\text{[math]}$ denotes the number of edges with weight $\text{[math]}$ in $\text{[math]}$

let $\text{[math]}$ be mst's of $\text{[math]}$ , let $\text{[math]}$ , then $\text{[math]}$

the histogram of weight frequency is the same for all mst's of a given graph