Non-negative Graphs

Notation	Meaning
$c_e$	For every edge $e\in E$ in graph $G=(V,E)$, $c_e$ is the cost of the edge $e$.
$c(G')$	For any (sub)graph $G=(V',E')$ we use $c(G')=\sum_{e\in E'} c_e$ to denote the cost of $G'$. Typically, we will consider the case when $G'$ is a spanning tree.

Kruskal's Algorithm

Notation	Meaning
$T$	The set to which Kruskal's algorithm adds edges. Initially $T=\emptyset$ and at the end it contains the edges of the MST.

Prim's Algorithm

Notation	Meaning
$T$	The set to which Prims's algorithm adds edges. Initially $T=\emptyset$ and at the end it contains the edges of the MST.
$S$	Set of nodes that have been "handled" by Prim's algorithm. This corresponds to the $R$ in Dijkstra's algorithm.

Reverse Delete Algorithm

Notation	Meaning
$T$	The set to which Reverse Delete algorithm adds edges. Initially $T=E$ and at the end it contains the edges of the MST.

Cut Property Lemma

Notation	Meaning
A cut	Division of the set of vertices into two non-empty parts: i.e. $(S,V\setminus S)$, where $S\neq\emptyset$ and $S\neq V$.
Crossing edge	An edge $(u,w)\in E$ is a crossing edge for cut $(S,V\setminus S)$ if and only if $u\in S$ and $w\not\in S$ (or vice-versa).