Trees · Matrix Tree Theorem (Optional)
Lesson 3
Nikolai Chukhin · Alexander S. Kulikov
Edge contraction \(e=\{i,j\} \in E\) of a graph \(G(V,E)\) is a procedure where the edge \(\{i,j\}\) is removed, and the vertices \(i\) and \(j\) are identified (all occurrences of \(j\) are replaced with \(i\)). The resulting graph is denoted as \(G / e\).
=2/image0.png)
As seen, contraction may result in loops and multiple edges. Therefore, in the formulation of the next theorem, we find it convenient to assume that both may be present in the graph. (Two spanning trees that include different copies of the same edge are considered distinct.)