Given a tree on $$$n$$$ nodes, perform the following operation as many times as you like (including zero times): Choose four nodes connected in a chain, and contract them to a single node, merging their adjacency lists. Output the minimum size you can reduce the tree to.

Does anyone know how to find a polynomial time solution for this, or prove that the problem is NP-Complete? It seems very difficult for me. Has anyone seen this problem, or something equivalent, before?

I tried it for very long, and then I gave it to several IGMs and they couldn't solve it, and ChatGPT 5.5 Pro can neither solve it nor prove NP-completeness.