Definition
In graph theory, a flower snark is a member of an infinite family of snarks—connected, bridgeless cubic graphs whose edges cannot be colored with only three colors (i.e., whose chromatic index equals 4). The family was introduced by Rufus Isaacs in 1975.
Overview
The flower snarks are denoted $J_n$ where $n$ is an odd integer with $n \ge 5$. Each graph $J_n$ has $4n$ vertices and $6n$ edges, and it is 3‑regular (cubic). The construction proceeds by taking $n$ copies of a 4‑vertex star, linking the outer vertices of the stars into two cycles, and then joining the central vertices to their respective outer vertices. By design the resulting graphs are non‑planar, non‑Hamiltonian, and 1‑planar.
Special cases are often highlighted:
- $J_5$ (20 vertices, 30 edges) is frequently referred to simply as “the flower snark.” It is one of six known snarks on 20 vertices and is hypohamiltonian (removing any vertex yields a Hamiltonian graph).
- $J_3$ is a trivial variation of the Petersen graph obtained by replacing one vertex with a triangle; this graph is also known as Tietze’s graph, but it is not considered a snark under the usual girth‑≥ 5 restriction.
Etymology / Origin
The term “snark” in graph theory originates from a 1975 paper by Isaacs, borrowing the whimsical name coined by mathematician Martin Gardner for a class of hard‑to‑solve puzzles. The qualifier “flower” was assigned by Isaacs to this particular family, likely reflecting the visual appearance of the constructed graphs, though no formal etymology is recorded in the literature.
Characteristics
| Property | Description |
|---|---|
| Vertex count | $4n$ (for odd $n \ge 5$) |
| Edge count | $6n$ |
| Degree | Cubic (regular of degree 3) |
| Chromatic number | 3 |
| Chromatic index | 4 (hence a snark) |
| Girth | 3 in general; for $n \ge 5$ the girth is at least 5 when the snark restriction is applied |
| Planarity | Non‑planar; however, each $J_n$ is 1‑planar (can be drawn with at most one crossing per edge) |
| Hamiltonicity | Non‑Hamiltonian; $J_5$ is hypohamiltonian |
| Book thickness | 3 for $J_5$ and $J_7$ |
| Queue number | 2 for $J_5$ and $J_7$ |
| Construction | Combine $n$ 4‑vertex stars, form an $n$-cycle on one set of outer vertices, and a $2n$-cycle on the remaining outer vertices. |
Related Topics
- Snark (graph theory) – the broader class of cubic, bridgeless, non‑3‑edge‑colorable graphs.
- Petersen graph – a classic small snark; $J_3$ can be obtained from it.
- Tietze’s graph – another name for $J_3$.
- Cubic graph – a graph where every vertex has degree 3.
- Edge coloring – the problem of assigning colors to edges so that adjacent edges differ; snarks have chromatic index 4.
- Hamiltonian graph – a graph containing a cycle that visits every vertex exactly once; flower snarks are non‑Hamiltonian.
- 1‑planar graph – graphs drawable with at most one crossing per edge; flower snarks belong to this class.
- Rufus Isaacs – mathematician who introduced the flower snarks.
References: R. Isaacs, “Infinite Families of Nontrivial Trivalent Graphs Which Are Not Tait Colorable,” American Mathematical Monthly, 1975; Wikipedia article “Flower snark” (accessed 2026).