From Surf Wiki (app.surf) — the open knowledge base

Butterfly graph

Planar graph with 5 nodes and 6 edges

Field	Value
name	Butterfly graph
image	[[Image:Butterfly graph.svg	200px]]
vertices	5
edges	6
automorphisms	8 (D)
diameter	2
radius	1
girth	3
chromatic_number	3
chromatic_index	4
properties	Planar
Unit distance
Eulerian
Not graceful

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. It can be constructed by joining 2 copies of the cycle graph C with a common vertex and is therefore isomorphic to the friendship graph F.

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 C and the complete graph K.

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

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

"Butterfly Graph".
ISGCI: Information System on Graph Classes and their Inclusions. "[http://www.graphclasses.org/smallgraphs.html List of Small Graphs]".
"Graceful graph".

Info: Wikipedia Source

This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page.

individual-graphs planar-graphs

Want to explore this topic further?

Ask Mako anything about Butterfly graph — get instant answers, deeper analysis, and related topics.

Research with Mako

Free with your Surf account

Content sourced from Wikipedia, available under CC BY-SA 4.0.

This content may have been generated or modified by AI. CloudSurf Software LLC is not responsible for the accuracy, completeness, or reliability of AI-generated content. Always verify important information from primary sources.

Report