+\paran{Multigraphs}\id{multimst}%
+All theorems and algorithms from this chapter work for multigraphs as well,
+only the notation sometimes gets crabbed, which we preferred to avoid. The Minimality
+theorem and the Blue rule stay unchanged. The Red rule is naturally extended to
+self-loops (which are never in the MST) and two-edge cycles (where the heavier
+edge can be dropped) as already suggested in the Flattening lemma (\ref{flattening}).
+
+\paran{Multiple edges of the same weight}\id{multiweight}%
+In case when the edge weights are not distinct, the characterization of minimum
+spanning trees using light edges is still correct, but the MST is no longer unique
+(as already mentioned, there can be as much as~$n^{n-2}$ MST's).
+
+In the Red-Blue procedure, we have to avoid being too zealous. The Blue lemma cannot
+guarantee that when a~cut contains multiple edges of the minimum weight, all of them
+are in the MST. It will however tell that if we pick one of these edges, an~arbitrary
+MST can be modified to another MST that contains this edge. Therefore the Blue rule
+will change to ``Pick a~cut~$C$ such that it does not contain any blue edge and color
+one of its lightest edges blue.'' The Red lemma and the Red rule can be handled
+in a~similar manner. The modified algorithm will be then guaranteed to find one of
+the possible MST's.
+
+The Kruskal's and Jarn\'\i{}k's algorithms keep working. This is however not the case of the
+Bor\o{u}vka's algorithm, whose proof of correctness in Lemma \ref{borcorr} explicitly referred to
+distinct weights and indeed, if they are not distinct, the algorithm will occasionally produce
+cycles. To avoid the cycles, the ties in edge weight comparisons have to be broken in a~systematic
+way. The same applies to the contractive version of this algorithm.
+