"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 )...
The Soifer graph is a planar graph on 9 nodes that tangles the Kempe chains in Kempe's algorithm and thus provides an example of how Kempe's supposed proof of the four-color theorem fails. As proved by Gethner and Springer, the Soifer graph is the smallest such counterexample (and is smaller than the Kittell graph and Errera graph).It is implemented in the Wolfram Languageas GraphData["SoiferGraph"].
The Moser spindle is the 7-node unit-distance graph illustrated above (Read and Wilson 1998, p. 187). It is sometimes called the Hajós graph (e.g., Bondy and Murty 2008. p. 358), though this term is perhaps more commonly applied to the Sierpiński sieve graph .It is implemented in the Wolfram Languageas GraphData["MoserSpindle"].A few other (non-unit) embeddings of the Moser spindle are illustrated above.The Moser spindle has chromatic number 4 (as does the Golomb graph), meaning the chromatic number of the plane must be at least four, thus establishing a lower bound on the Hadwiger-Nelson problem. After a more than 50-year gap, the first unit-distance graph raising this bound (the de Grey graph with chromatic number 5) was constructed by de Grey (2018).
The -pan graph is the graph obtained by joining a cycle graph to a singleton graph with a bridge. The -pan graph is therefore isomorphic with the -tadpole graph. The special case of the 3-pan graph is sometimes known as the paw graph and the 4-pan graph as the banner graph (ISGCI).Koh et al. (1980) showed that -tadpole graphs are graceful for , 1, or 3 (mod 4) and conjectured that all tadpole graphs are graceful (Gallian 2018). Guo (1994) apparently completed the proof by filling in the missing case in the process of showing that tadpoles are graceful when or 2 (mod 4) (Gallian 2018), thus establishing that pan graphs are graceful.The fact that the -pan graphs, corresponding to -tadpole graphs, are graceful for , 2 (mod 4) follows immediately from adding the label to the "handle" vertex adjacent to the verex with label 0 in a cycle graph labeling.Precomputed properties of pan graphs are available in the Wolfram Language as GraphData["Pan",..
"The" H graph is the tree on 6 vertices illustrated above. It is implemented in the Wolfram Language as GraphData["HGraph"].The term "H-graph" is also used to refer to a graph expansion with the 6-vertex H graph as its base (e.g., Horton and Bouwer 1991). There are exactly two graph expansions with H-graph base that are symmetric (Biggs 1993, p. 147).graphexpansion 102Biggs-Smith graph (17; 3, 5, 6, 7)204cubic symmetric graph (34; 3, 5, 7, 11)