TxGraffiti Conjecture 4: the saturation number versus the harmonic index
Reference:arxiv/2507.17780In Reverie Together: Ten Years of Mathematical Discovery with a Machine
Collaborator by Randy Davila, Boris Brimkov, Ryan Pepper
TxGraffiti is an automated conjecturing program, a successor of Fajtlowicz's
Graffiti and DeLaViña's Graffiti.pc. Conjecture 4 in the cited collection
asserts a bound between two graph invariants:
the saturation number $\mu^*(G)$ (SimpleGraph.saturationNumber), the
minimum number of edges in a maximal matching of $G$;
the harmonic index $H(G)$ (SimpleGraph.harmonicIndex),
$\sum_{uv \in E(G)} 2 / (\deg u + \deg v)$.
The conjecture is false. It was first refuted by Bıyıkoğlu, who exhibited a
family of counterexamples — a disjoint union of edges joined to an independent
set — with unbounded ratio $\mu^*/H$. That the smallest counterexample has
order $9$, namely the friendship graph $F_4$ formalised below, and that the
windmill family has an exact limiting ratio, are established in Gupta.
The friendship graph $F_4$: a hub vertex $0$ joined to four triangles, whose
rims are the pairs ${1,2}, {3,4}, {5,6}, {7,8}$. It has $12$ edges on
$9$ vertices ($8$ spokes and $4$ rim edges).
TxGraffiti Conjecture 4:
for every nontrivial connected graph $G$, the saturation number is at most
the harmonic index, $\mu^*(G) \le H(G)$.
This conjecture is FALSE.
Counterexample.
The friendship graph $F_4$ (friendshipF4) is connected and nontrivial, with
$\mu^(F_4) = 4$ and $H(F_4) = 18/5$. Indeed the four rim edges
${1,2}, {3,4}, {5,6}, {7,8}$ form a maximal matching of size $4$, and
no maximal matching is smaller, so $\mu^(F_4) = 4$; the eight spokes
contribute $2/(8+2) = 1/5$ each and the four rim edges contribute
$2/(2+2) = 1/2$ each, giving $H(F_4) = 8 \cdot 1/5 + 4 \cdot 1/2 = 18/5$.
Since $4 > 18/5$, the bound fails.
More generally the friendship graphs $F_k$ satisfy $\mu^(F_k) = k$ and
$H(F_k) = 2k/(k+1) + k/2$, so the conjecture fails for every $k \ge 4$. An
exhaustive search confirms that $F_4$ is the smallest counterexample
(order $9$). The unbounded separation was first shown by Bıyıkoğlu, whose
family of edges joined to an independent set makes $\mu^/H$ arbitrarily
large; the windmill generalisation and its exact limit appear in
arXiv:2606.15761.