# Bowtie-minor-free graphs

The pseudoforests can be characterized as the minor-closed graph family in which no graph has a bowtie or diamond (shown below) as a minor, and the cactus graphs (and their disjoint unions) can be characterized as the minor-closed graph family in which no graph has a diamond as a minor. What about the family in which no graph has a bowtie as a minor?

The bowtie (left) and the diamond (right).

First a word about terminology: what I'm calling here the bowtie appears to be more commonly called a butterfly (e.g. in ISGCI) so that's what I call it on Wikipedia. But here, I'd prefer to call it a bowtie, to avoid confusion with the butterfly graphs used as parallel computer communication networks.

Each connected bowtie-minor-free graph can have at most one nontrivial biconnected component, and any bowtie-minor-free graph can be formed as the disjoint union of trees and the graphs formed by attaching trees to a biconnected bowtie-minor-free graph. So the biconnected ones are what we really need to classify, and the rest will follow. As a shorthand, let BCBMFG stand for "biconnected bowtie-minor-free graph". By some case analysis, I can show that the BCBMFGs fall into six different classes:

First, suppose that G is a BCBMFG with girth five or more, and let C be a shortest cycle in G. Then G can have no other vertices or edges attached to C: such an attachment would have to connect to at least two vertices of C (else G wouldn't be biconnected), and any path connecting those two vertices within the attachment would have to be at least as long as the longer of the two paths connecting the same two vertices in C. If we contract the shorter path in C connecting the vertices, these two long paths would form a figure eight that can be contracted to form a bowtie, a contradiction to the assumption that G is a BCBMFG. So, this high-girth case consists only of one type of graph, a

BCBMFG type I: cycles.

Second, suppose that G is a BCBMFG containing a triangle abc, and that some component of the remaining graph attaches to this triangle at all three of its vertices. This attachment must be a tree: if it contained a cycle, it and triangle abc could be contracted together to form a bowtie. There can be no second attachment to abc, for the cycle formed by the second attachment and one of the edges of abc could be combined by the cycle formed by the first attachment and a different edge of abc to form a bowtie. Thus, in this case, the attachment and the triangle together form a

BCBMFG type II: subdivided K

Third, suppose that G is a BCBMFG containing a triangle abc, and all components of the remaining graph attach at two vertices of abc. They must all attach at the same two vertices, for otherwise we could form a figure eight by cycles through two attachments and two edges of abc. Each attachment must be a simple path, because if an attachment contained a cycle then it and triangle abc could be contracted together to form a bowtie. At most one attachment can be a path of length three or more, because if there were two such long paths we could contract abc to form a figure eight. If there are no long paths, then G is a

BCBMFG types III and IV: book of triangles, and cycle with attached book of triangles.

In the remaining case, G is a triangle-free BCBMFG containing a quadrilateral abcd. Again, look at the attachments to abcd formed by the components of the remaining graph; each must be cycle-free and attach to two or more vertices of abcd. No such attachment can connect adjacent vertices of abcd, because it would either form a triangle or allow us to form a figure eight by contracting abcd; thus each attachment connects an opposite pair of vertices of abcd. It is not possible to connect both opposite pairs, because in this case contracting one edge of abcd and deleting the opposite edge would produce a figure eight; therefore all attachments connect the same opposite pair. And as in the triangle case, at most one of the attachments can be a long path, or we could form a figure eight by contracting abcd. If there are no long paths, then G is a

BCBMFG types V and VI: K

And that's the complete classification! ...at least, if I haven't made any mistakes.

Is this class of graphs good for anything? That's less clear.

The bowtie (left) and the diamond (right).

First a word about terminology: what I'm calling here the bowtie appears to be more commonly called a butterfly (e.g. in ISGCI) so that's what I call it on Wikipedia. But here, I'd prefer to call it a bowtie, to avoid confusion with the butterfly graphs used as parallel computer communication networks.

Each connected bowtie-minor-free graph can have at most one nontrivial biconnected component, and any bowtie-minor-free graph can be formed as the disjoint union of trees and the graphs formed by attaching trees to a biconnected bowtie-minor-free graph. So the biconnected ones are what we really need to classify, and the rest will follow. As a shorthand, let BCBMFG stand for "biconnected bowtie-minor-free graph". By some case analysis, I can show that the BCBMFGs fall into six different classes:

First, suppose that G is a BCBMFG with girth five or more, and let C be a shortest cycle in G. Then G can have no other vertices or edges attached to C: such an attachment would have to connect to at least two vertices of C (else G wouldn't be biconnected), and any path connecting those two vertices within the attachment would have to be at least as long as the longer of the two paths connecting the same two vertices in C. If we contract the shorter path in C connecting the vertices, these two long paths would form a figure eight that can be contracted to form a bowtie, a contradiction to the assumption that G is a BCBMFG. So, this high-girth case consists only of one type of graph, a

**cycle**. To make sure we cover all BCBMFGs, we'll include cycles of length three or four in this case as well.BCBMFG type I: cycles.

Second, suppose that G is a BCBMFG containing a triangle abc, and that some component of the remaining graph attaches to this triangle at all three of its vertices. This attachment must be a tree: if it contained a cycle, it and triangle abc could be contracted together to form a bowtie. There can be no second attachment to abc, for the cycle formed by the second attachment and one of the edges of abc could be combined by the cycle formed by the first attachment and a different edge of abc to form a bowtie. Thus, in this case, the attachment and the triangle together form a

**subdivision of the complete graph K**. At most one edge of K_{4}_{4}can be subdivided, for the triangle itself is not subdivided and if two legs of the attachment were subdivided, we could contract the third leg and omit the opposite triangle edge to form a figure eight, contractible to a bowtie.BCBMFG type II: subdivided K

_{4}.

Third, suppose that G is a BCBMFG containing a triangle abc, and all components of the remaining graph attach at two vertices of abc. They must all attach at the same two vertices, for otherwise we could form a figure eight by cycles through two attachments and two edges of abc. Each attachment must be a simple path, because if an attachment contained a cycle then it and triangle abc could be contracted together to form a bowtie. At most one attachment can be a path of length three or more, because if there were two such long paths we could contract abc to form a figure eight. If there are no long paths, then G is a

**book of triangles**(or complete split graph). If there is one long path, then it and one of the edges of abc forms a long cycle, and we have a**cycle of length ≥ 4 with a book of triangles attached to one edge**.BCBMFG types III and IV: book of triangles, and cycle with attached book of triangles.

In the remaining case, G is a triangle-free BCBMFG containing a quadrilateral abcd. Again, look at the attachments to abcd formed by the components of the remaining graph; each must be cycle-free and attach to two or more vertices of abcd. No such attachment can connect adjacent vertices of abcd, because it would either form a triangle or allow us to form a figure eight by contracting abcd; thus each attachment connects an opposite pair of vertices of abcd. It is not possible to connect both opposite pairs, because in this case contracting one edge of abcd and deleting the opposite edge would produce a figure eight; therefore all attachments connect the same opposite pair. And as in the triangle case, at most one of the attachments can be a long path, or we could form a figure eight by contracting abcd. If there are no long paths, then G is a

**complete bipartite graph**K_{2,i}. If there is a long path, then G is a**cycle of length ≥ 4 with one of its edges replaced by a complete bipartite graph**.BCBMFG types V and VI: K

_{2,i}, and cycle with edge replaced by K

_{2,i}.

And that's the complete classification! ...at least, if I haven't made any mistakes.

Is this class of graphs good for anything? That's less clear.