A counterexample to a conjecture of Graffiti.pc on the forest number

Introduction

Graffiti.pc is a program written by DeLaViña [3] after Fajtlowicz’s Graffiti [5]; it proposes inequalities between graph invariants that hold on its database of graphs. DeLaViña’s list Written on the Wall II [4] records its conjectures with their status. Conjecture 66, generated on 25 March 2004, is still marked as open (in the version of 26 July 2026). This note shows that it is false. The proofs are by hand; as in [2], every finite statement is also re-checked by computer, and the counterexamples are also confirmed in the Lean proof assistant (§ 3 and Appendix § 4).

All graphs are finite and simple. For a graph $G$ with $n$ vertices and $m$ edges, $\operatorname{deg}_{\mathrm{avg}}(G)=2m/n$ is the average degree and $\overline{G}$ the complement, in which a vertex of degree $d$ in $G$ has degree $n-1-d$. The forest number $f(G)$ is the largest number of vertices of an induced subgraph of $G$ that is a forest. The list defines the even mode of a graph as “the most frequently occurring degree that is an even integer”, with $\operatorname{even\_mode}_{\min}$ the smallest one when several are equally frequent. We write $\operatorname{em}(H)$ for this number: among the even values in the degree sequence of $H$, the most frequent one, and the smallest of these in case of a tie. Conjecture 66 reads as follows in [4].

The definition of the even mode also admits a second reading: the smallest even value among the most frequent degrees, defined only when some most frequent degree is even. And while the statement uses $\lceil\cdot\rceil$, the definitions that the list attaches to it are those of $f$, the even mode, the complement, the average degree, and the floor function $\lfloor\cdot\rfloor$. The list also records that in 2008 all 11,716,571 connected graphs with 10 vertices were added to the database of Graffiti.pc (see its notes to Conjectures 42 and 187). We show in § 3 that the printed conjecture fails on seven of these graphs, while the version with $\lfloor\cdot\rfloor$ holds on all of them; so the floor may well be what the program meant. We therefore treat all four readings.

For $c \ge1$ let $H_c$ be the graph made of $c$ disjoint copies $Q_1,\ldots,Q_c$ of the complete graph $K_4$, with vertices $x_{i,0},x_{i,1},x_{i,2},x_{i,3}$ in $Q_i$, together with the $c-1$ edges $x_{i,1}x_{i+1,0}$ for $1 \le i < c$ (Figure 1.1).

The smallest member of the family that refutes all four readings, $H_{14}$, has 56 vertices. We did not determine the smallest counterexample to the readings with $\lfloor\cdot\rfloor$; the smallest one we found has 37 vertices (Remark 2.2).

The chains of complete graphs

Proof. Three vertices of one $Q_i$ induce a triangle, so an induced forest contains at most two vertices of each $Q_i$; since the $Q_i$ partition the vertex set, it has at most $2c$ vertices. The $2c$ vertices $x_{i,2},x_{i,3}$ induce $c$ disjoint edges, which form a forest.

Proof. The copies $Q_i$ are connected and consecutive ones are joined by an edge, so $H_c$ is connected; it has $6c$ edges inside the copies and $c-1$ between them. Every vertex has degree 3 inside its copy, and the $2(c-1)$ endpoints $x_{i,1}$ ($i<c$) and $x_{i,0}$ ($i>1$) of the joining edges, which are distinct, have one more neighbour. In $\overline{H_c}$, which has $n=4c$ vertices, the degrees are therefore $4c-4$, which is even, taken $2c+2$ times, and $4c-5$, which is odd, taken $2c-2$ times. So $4c-4$ is the only even degree of $\overline{H_c}$, and it is also its most frequent degree, because $2c+2>2c-2$.

Proof. We have

Since $c$ is an integer, $\lceil q_c\rceil\geq c+1$ if and only if $q_c>c$, that is, $c>7$. Next, $q_c\geq c+1$ if and only if $c(c-7)\geq7c-1$, that is, $c^2-14c+1\geq0$. The roots of $t^2-14t+1$ are $7\pm\sqrt{48}$, which lie in $(0,1)$ and $(13,14)$, so for positive integers $c$ this holds exactly when $c\geq14$. Finally, for $c\geq7$ we have $c/(7c-1)\geq1/7$ and $c-7\geq0$, so $q_c-c\geq(c-7)/7$, and taking integer parts gives the last claim.

Proof of Theorem 1.1. By Lemma 2.2, under either reading of the even mode,

By Lemma 2.1, Conjecture 66 fails for $H_c$ exactly when $2\lceil q_c\rceil>2c$, and the version with the floor fails exactly when $2\lfloor q_c\rfloor>2c$; Lemma 2.3 identifies these cases. The difference between the right side and $f(H_c)$ is at least $2\lfloor q_c\rfloor-2c\geq2\lfloor(c-7)/7\rfloor$.

For example, $H_8$ has 32 vertices, $f(H_8)=16$ and $q_8=448/55\approx8.15$, so the printed right side is 18. For $H_{14}$, with 56 vertices, $f(H_{14})=28$ and $q_{14}=1456/97\approx15.01$, so the right side is 32 with $\lceil\cdot\rceil$ and 30 with $\lfloor\cdot\rfloor.

Remark 2.1. The family is close to extremal in the following sense. Alon, Kahn and Seymour [1] proved that $f(G)\geq\sum_v\min\{1,2/(d(v)+1)\}$, with equality for disjoint unions of complete graphs. For a connected graph whose degrees are all close to $d$, the right side of Conjecture 66 is at most about $2n/d$ while $f(G)$ is at least about $2n/(d+1)$; a counterexample therefore needs the near-equality of disjoint cliques, a large even mode of the complement, and few extra edges to make the graph connected. The chains $H_c$ have all three.

Remark 2.2. Let $T$ be the graph made of 12 disjoint triangles $a_i b_i c_i$, the 11 edges $b_i a_{i+1}$, and one pendant vertex attached to $a_1$. It has 37 vertices and 48 edges, $f(T)=25$ (at most two vertices of each triangle, and the pendant vertex), and the only even degree of $\overline{T}$ is 34, taken by the 13 vertices of degree 2 in $T$. With the first reading of the even mode, $34/\operatorname{deg}_{\mathrm{avg}}(\overline{T})=34\cdot37/96\approx13.10$, so the right side is 26 with $\lfloor\cdot\rfloor$ and 28 with $\lceil\cdot\rceil$. The most frequent degree of $\overline{T}$ is the odd number 33, so $T$ says nothing about the second reading.

Small graphs

Let $G_{10}$ be the graph obtained from a triangle $t_1t_2t_3$ and a complete graph on $\{q_1,q_2,q_3,q_4\}$ by adding the edge $t_1q_1$ and three pendant vertices $\ell_1,\ell_2,\ell_3$, with $\ell_i$ adjacent to $q_i$ (Figure 3.1).

Proof. An induced forest contains at most two vertices of the triangle, at most two of the $K_4$, and the three pendant vertices, so $f(G_{10})\leq7$; the seven shaded vertices in Figure 3.1 induce the forest $t_2t_3$, $\ell_2q_2q_3\ell_3$, $\ell_1$. The degrees of $G_{10}$ are 5 ($q_1$), 4 ($q_2,q_3$), 3 ($t_1,q_4$), 2 ($t_2,t_3$) and 1 ($\ell_1,\ell_2,\ell_3$); so $m=13$, $\operatorname{degavg}(G_{10})=13/5$, and the degrees of $G_{10}$ are 4, 5, 5, 6, 6, 7, 7, 8, 8, 8. The value 8 occurs three times and every other value at most twice, so it is the even mode under both readings, and the right side is $2\lceil8\cdot5/13\rceil=2\lceil40/13\rceil=8$.

With $\lfloor\cdot\rfloor$ the right side for $G_{10}$ is $2\lfloor40/13\rfloor=6$, and the inequality holds.

Theorem 1.2 comes from an exhaustive search. The connected graphs with at most 10 vertices were generated with geng from nauty [7], and for each of them the four right sides were computed in integer arithmetic (the quotient $x/\operatorname{degavg}(G)$ equals $xn/(2m)$) and compared with the forest number, computed by branch and bound over vertex subsets. Table 3.1 gives the results. The seven counterexamples with 10 vertices all have 13 edges, three pendant vertices and forest number 7; their graph6 codes are I?ACJ@PqW (this is $G_{10}$), I?AACJafO, I?AACIdu_, I?AADJAfO, I?AADHQbW, I?ABAeKOw and I?`CR@PoW, and the last two violate only the first reading of the even mode.

$n$	graphs	first, $\lceil\cdot\rceil$	second, $\lceil\cdot\rceil$	first, $\lfloor\cdot\rfloor$	second, $\lfloor\cdot\rfloor$
2–8	12,112	0	0	0	0
9	261,080	0	0	0	0
10	11,716,571	7	5	0	0

Verification

The proofs above use no computation. The computer checks the finite claims and the search of § 3, independently in C, C++, Bash, Python, Julia and Lean; all files are in the repository listed under Data and code availability, where scripts/run_all.sh runs them.

1. C. wowii66.c performs the search of § 3 on graph6 input, and for $c\leq300$ builds $H_c$ and checks Lemmas 2.1–2.3: the degrees, the even modes and both right sides, the partition into cliques and the explicit forest of order $2c$, and $f(H_c)=2c$ by branch and bound for $c\leq6$.

2. C++. wowii66.cpp repeats both computations with no shared code and a different method for $f$ (a greedy lower bound, and an exact value over all vertex subsets only when that bound is below the right side). Its output for all connected graphs with at most 10 vertices is identical, line for line, to that of the C program.

3. Bash (shell integer arithmetic only): $G_{10}$, with $f(G_{10}) = 7$ over all 1024 vertex subsets; $H_c$ for $c \le40$; and the inequalities of Lemma 2.3 for $c \le20000$.

4. Python (exact rational arithmetic): $G_{10}$ and the seven graphs of Table 3.1, with $f$ over all vertex subsets and a colour-refinement check that the seven are pairwise non-isomorphic; every labelled connected graph with at most 6 vertices; $H_c$ for $c \le60$, with $f$ over all subsets for $c \le4$; and the inequalities of Lemma 2.3 for $c \le10^{5}$.

5. Julia (exact rational arithmetic): the same graphs, $H_c$ for $c \le300$, and $f(H_c) = 2c$ over all $2^{4c}$ vertex subsets for $c \le5$.

6. Lean 4 [8]: a self-contained file without Mathlib computes, in the kernel, every quantity of Proposition 3.1 from the edge list of $G_{10}$, including $f(G_{10}) = 7$ over all 1024 vertex subsets, and proves that Conjecture 66 fails for $G_{10}$ under both readings; the proof depends only on the axiom propext.

7. Lean 4 with Mathlib [6]: a second file defines the forest number, both readings of the even mode and the average degree for every finite simple graph, and proves for every $c$ that $H_c$ is connected, that $f(H_c) \le2c$, the degrees of $\overline{H_c}$, both even modes and both right sides. It concludes that $H_c$ violates Conjecture 66 under both readings for every $c \ge8$, and the version with $\lfloor\cdot\rfloor$ for every $c \ge14$. The proof uses only the standard axioms propext, Classical.choice and Quot.sound.

Declarations

Funding. No funding was received for conducting this study.

Competing interests. The author has no competing interests to declare that are relevant to the content of this article.

Data and code availability. The programs, their outputs and the Lean files are available at https://github.com/creelie/eConjectureWOWII66 and archived on Zenodo, https://doi.org/10.5281/zenodo.23254096.

Use of generative AI. The author used Claude (Anthropic) for programming, computation and drafting; the author checked the mathematics and takes full responsibility for the content.