Problems / combinatorics
combinatorics / Graph theory (induced trees / graph invariants)
WOWII Conjecture 72: Two induced trees pin down tree(G)
The evenly-divided reading of WOWII Conjecture 72 holds:
⌈(A+L)/3⌉≤t,
where t= tree(G) (order of a largest induced tree), A= average eccentricity and L= maximum neighbourhood independence number.
A stronger reading that divides only L by three is false. The argument rests on two elementary observations (a diametral path is chordless and therefore induces a tree on D+1 vertices; a maximum independent set in a neighbourhood induces a star on L+1 vertices). The original conjecture’s precise wording is not yet pinned in a public formal repository, so statement fidelity remains to be audited.