Butterfly graph

A graph is bowtie-free if it has no butterfly as an induced subgraph. The triangle-free graphs are bowtie-free graphs, since every butterfly contains a triangle. In a k-vertex-connected graph, an edge is said to be k-contractible if the contraction of the edge results in a k-connected graph. Ando, Kaneko, Kawarabayashi and Yoshimoto proved that every k-vertex-connected bowtie-free graph has a k-contractible edge. ==Algebraic properties==

The full automorphism group of the butterfly graph is a group of order 8 isomorphic to the dihedral group D4, the group of symmetries of a square, including both rotations and reflections. The characteristic polynomial of the butterfly graph is -(x-1)(x+1)^2(x^2-x-4). == References ==