FormalConjectures/WrittenOnTheWallII/GraphConjecture200.lean

Written on the Wall II - Conjecture 200

Reference:E. DeLaVina, Written on the Wall II, Conjectures of Graffiti.pc

Counterexample

For every integer $q \geq 5$, let $C = \{a,b\} \cup D$ have $q$ vertices and induce $K_q$ minus the edge $ab$. Add two nonadjacent vertices $x,y$, each complete to $C$; a vertex $z$ adjacent exactly to $a,b$; and, for every $d \in D$, a pendant vertex $p_d$ adjacent exactly to $d$.

The local-neighbourhood independence numbers are $2$ at $x,y,z$, $1$ at each $p_d$, and $3$ at every vertex of $C$. Their sum is $4q+4$, while the graph has $2q+1$ vertices, so $$\left\lceil 1 + l_{\mathrm{avg}}(G)\right\rceil = 4.$$ The vertices $\{a,x,y,z\}$ induce a claw, and a case split on the number of vertices from $C$ shows that no induced tree has more than four vertices. Thus $\operatorname{tree}(G)=4$. Finally, the graph has $q-2 \geq 3$ pendant vertices, but a Hamiltonian path has only two endpoints.

The smallest member of this family has 11 vertices and graph6 encoding J??FFBRq}N_. This is a smallest counterexample overall: an exhaustive search over all 11,989,760 connected graphs on 4 ≤ n ≤ 10 vertices (via nauty's geng; graphs on at most 3 vertices are trivially traceable) found no graph satisfying the premise without a Hamiltonian path.