Edge Contraction Definition

614 Views Asked by At

enter image description here I was reading about the definition of contracting an edge from this site. Above and to the left is a diagram which I called picture $1$ which is exactly the picture from the site which shows contraction of the blue edge from the graph. In picture $2$, I labeled the edge $e_1$ in the picture and kept it there after contracting the blue edge because as reading the definition as how it is now I figure the edge should be there.

$\textbf{Question:}$ Is the reason $e_1$ is left out of picture $1$ after contracting the blue edge, because the graph can't have multiple edges? In my terminology, it is fine to have graphs with multiple edges. So would picture $2$ work for contracting the blue edge if I allow this?

It does say in the article, "As defined below, an edge contraction operation may result in a graph with multiple edges even if the original graph was a simple graph." I just find that weird though, because the picture does not coincide with the definition if that was the case.

1

There are 1 best solutions below

0
On BEST ANSWER

Quote

As defined below, an edge contraction operation may result in a graph with multiple edges even if the original graph was a simple graph. However, some authors disallow the creation of multiple edges, so that edge contractions performed on simple graphs always produce simple graphs.

Sometimes you want the extra edge other times you don't. For example, when enumerating graph colourings (via deletion-contraction) you don't want to create loops but it doesn't matter whether or not you have multiple edges (so usually you remove the extra edges for simplicity). For enumerating spanning trees you need to keep the extra edges to get the right count.