Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

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)
H.add_edges([(0,1), (0,1), (0,2), (1,2)])

G = Graph()
G.allow_multiple_edges(True)
G.add_edges([(0,1), (0,3), (1,2), (2,3)])

G.minor(H)

The output is:

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

Is there a work-around?