How to Contract a Loop?

272 Views Asked by At

I am trying to prove the following proposition below (it can be found here on p. 6 too where it specifically states that the proposition holds with loops and multiple edges).

Question: How do you contract a loop? I thought $G-e=G/e$ when $e$ is a loop. However, it is clear that $t(G/e)=0$ when $e$ is a loop to make the proposition below hold true.

Proposition: Let $G$ be a graph. Then, for any edge $e$, $t(G)=t(G-e)+t(G/e)$ .

As for notation, I assume graphs allow repeated edges and loops, and the notation $t(G)$ denotes the number of spanning trees of $G$. Also, $G-e$ denotes the deletion of edge $e$ and $G/e$ denotes the contraction of edge $e$.

1

There are 1 best solutions below

0
On BEST ANSWER

Probably the best way to make sense of it is to say that $G/e$ is not defined if $e$ is a loop, and that the proposition does not claim anything in that case.

This requires doing a bit of violence to the wording, but produces something that is true and still useful, because you'll never need to apply it to loops in order to make progress anyway.


Alternatively you can say that you work only with multigraphs without loops and define contraction such that it removes all edges parallel to the one you contract.