Butterfly graph
{{Short description|Planar graph with 5 nodes and 6 edges}}
{{Infobox graph
| name = Butterfly graph
| image = 200px
| vertices = 5
| edges = 6
| automorphisms = 8 ({{math|D{{sub|4}}}})
| diameter = 2
| radius = 1
| girth = 3
| chromatic_number = 3
| chromatic_index = 4
| properties = Planar
Unit distance
Eulerian
Not graceful
}}
In the mathematical field of graph theory, the butterfly graph (also called the bowtie graph and the hourglass graph) is a planar, undirected graph with 5 vertices and 6 edges.{{MathWorld|urlname=ButterflyGraph|title=Butterfly Graph}}ISGCI: Information System on Graph Classes and their Inclusions. "[http://www.graphclasses.org/smallgraphs.html List of Small Graphs]". It can be constructed by joining 2 copies of the cycle graph {{math|C{{sub|3}}}} with a common vertex and is therefore isomorphic to the friendship graph {{math|F{{sub|2}}}}.
The butterfly graph has diameter 2 and girth 3, radius 1, chromatic number 3, chromatic index 4 and is both Eulerian and a penny graph (this implies that it is unit distance and planar). It is also a 1-vertex-connected graph and a 2-edge-connected graph.
There are only three non-graceful simple graphs with five vertices. One of them is the butterfly graph. The two others are cycle graph {{math|C{{sub|5}}}} and the complete graph {{math|K{{sub|5}}}}.{{mathworld|title=Graceful graph|urlname=GracefulGraph}}
Bowtie-free graphs
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.{{citation
| last = Ando | first = Kiyoshi
| contribution = Contractible edges in a k-connected graph
| doi = 10.1007/978-3-540-70666-3_2
| mr = 2364744
| pages = 10–20
| publisher = Springer, Berlin
| series = Lecture Notes in Comput. Sci.
| title = Discrete geometry, combinatorics and graph theory
| volume = 4381
| year = 2007}}.
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 .