# Why does graph minor not work with multiple edges?

When $H$ has multiple edges, and we ask whether it is a minor of another graph $G$, using the method:

G.minor(H)


the multiple edges are ignored. As a result, it can return True, when $H$ is not actually a minor of $G$.

Here is a small example of this incorrect behavior.

Let $H$ be a triangle with a double edge, and let $G$ be a square. Clearly, $H$ is not a minor of $G$.

H = Graph()
H.allow_multiple_edges(True)

G = Graph()
G.allow_multiple_edges(True)

G.minor(H)


The output is:

{0: [0], 1: [1], 2: [2, 3]}


Is there a work-around?

edit retag close merge delete

Sort by ยป oldest newest most voted

I would say that if you split all edges of both graph by adding adding a new vertex b joined to a and c where there was an edge from a to c (this is a way to transform a graph with multiple edges into a normal graph), then checking that one is a minor of the other would give you the good definition.

I expect it to be slower, though.

And the explanation to your question "why aren't multiple edges considered by the minor function" is very easy and natural : why should it ? Things get implemented if somebody who cares about them takes the time to do it. Otherwise, they are not implemented.

Nathann

more

Yeah. I had already done that, but it was too slow. Thank you, though.

( 2013-05-12 12:42:50 -0600 )edit

## Stats

Seen: 114 times

Last updated: May 12 '13