If $M=(E,I)$ is a matroid, and $e$ is not a loop (a loop is an element of the matroid which is not an element of any independent set), we may define the matroid obtained by contracting $e$ to be the matroid whose edges are $E\smallsetminus\{e\}$ and whose independent sets are $\{A\smallsetminus\{e\}\mid A\cup\{e\}\in I\}$.

The graphic intuition behind this works well with the graphic notation of contraction; in case of graphic matroids, both definitions coincide. One other important observation is that a contraction in $M$ is equivalent to a removal in the dual matroid $M^*$.

I've taken the graphic intuition and checked the case in which $e$ is a loop. In that case, "contracting" $e$ would mean removing it. Taking a simple example of a lemniscate graph (one vertex, two loops), the dual matroid in this case is the graphic matroid of a $V$-shaped tree (3 vertices, 2 edges). A removal in the dual would leave us with a single edge, and the dual of that is a single loop. That is, even when $e$ is a loop, at least in this example, the "contraction as a removal in the dual" definition coincides with the graphic one. In this case it also coincides with the original definition.

My question is this: why are loops omitted from the original definition? The dual question would be: why are coloops (bridges) omitted from the definition of removal?


1 Answer 1


There are no independent sets containing the loop $e$. So $\{A\smallsetminus\{e\}\mid A\cup\{e\}\in I\} = \phi$.

But this means $M^*$ has no dependent sets, which is not true (this could have been true if we consider isolated vertices after deleting edges, but we don't. We simply ignore the isolated vertices.)

Hence the original definition has to put exceptions on loops.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .