"The" butterfly graph is a name sometimes given to the 5-vertex graph illustrated above. This graph is also known as the "bowtie graph" (West 2000, p. 12)
and is the triangular snake graph 
. The butterfly graph is ungraceful
(Horton 2003). It is implemented in the Wolfram
Language as GraphData["ButterflyGraph"].
A different type of butterfly graph is defined as follows. The 
-dimensional butterfly graph is a directed
graph whose vertices are pairs 
, where 
is a binary string of length 
and 
is an integer in the range 0 to 
and with directed edges from vertex 
to 
iff 
is identical to 
in all bits with the possible exception of the 
th bit counted from the left.
The 
-dimensional
butterfly graph has 
vertices and 
edges, and can be generated in the Wolfram
Language using ButterflyGraph[n,
b] (with 
).
