It seems intuitive that any natural problem that is NP-hard on trees, should be hard on graphs that are not trees. But perhaps this is wrong?
Question: Is there some natural decision problem on graphs that is NP-hard when we are promised the graph is a tree, but in $ P$ when the graph is promised to not be a tree.
Here’s a list of problems that are NP-hard on trees: https://cstheory.stackexchange.com/questions/1215/np-hard-problems-on-trees The ones I saw were all also hard on non-trees.
Given any NP-complete language $ M$ that is NP-complete on trees, you can obtain a tautological example via the decision problem $ L$ where $ x \in L$ iff $ x \in M$ and $ x$ is a tree. This is pretty unnatural though.
Is there some object that trees have a lot of of, but non-trees only have a few of?