The cycle set of a graph $G$ on $n$ vertices is a set $A \subseteq {3, \dots, n}$ such that there is a cycle in $G$ of length $ℓ$ if and only if $ℓ \in A$ . Let $f (n)$ count the number of possible such $A$ . Prove that $f (n) = o (2^{n})$ .Prove that $f (n) / 2^{n /2} \to \infty$ .

Worked, still open.

graph theory · open · possible · 0 attempts

use this record

vela registry pull vfr_37aec80d874a0239

vela reproduce examples/erdos-problems

evidence

unverified AI candidates (2)

gpt-erdos · GPT-5.2 Pro + Deep Research · unverified

Let $f(n)$ be the number of sets (A\subseteq{3,\dots,n}) that occur as the **cycle set** of some graph on $n$ vertices.

llm-hunter · gpt 5.2, gpt pro 5.2 · unverified

2 LLM attack(s) recorded (gpt 5.2, gpt pro 5.2); unverified.

open