A333717 a(n) is the minimal number of vertices in a simple graph with exactly n cycles.

3, 5, 4, 6, 8, 5, 4, 6, 8, 6, 6, 5, 5, 6, 6, 8, 7, 6, 6, 6, 6, 5, 6, 6, 7, 7, 7, 7, 7, 6, 7, 6, 6, 7, 6, 6, 5, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 6, 6, 7, 7, 7, 7, 6, 7, 7, 7, 6, 7, 7, 7, 8, 8, 7, 7, 7, 8, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 7, 7

Offset

1,1

Comments

a(n+1) is at most a(n) + 2 since we can add a triangle to a graph with a(n) vertices and increase the number of cycles by 1.

David Eppstein observed that an N-gon with each edge replaced by a triangle has 2^N + N cycles and 2N vertices, and gluing such graphs together greedily yields an upper bound on a(n) of O(log n).

Links

Table of n, a(n) for n=1..87.

David Eppstein, Mathstodon post about O(log n) upper bound, 26 August 2020.

Example

For n = 2, a pair of triangles sharing a vertex has five vertices; it is easy to check that no graph on three or four vertices has exactly two cycles, so a(2) = 5.

Crossrefs

Sequence in context: A021286 A200324 A063259 * A064425 A094761 A114748

Adjacent sequences: A333714 A333715 A333716 * A333718 A333719 A333720

Keyword

nonn

Author

Christopher Purcell, Sep 03 2020

Status

approved