Cases[set1, _ -> "green"]
tells Cases to replace expressions matching
_
(any Mathematica expression) with "green". That is the way Cases works. But what you want is to find cases of occurrence of the pattern
(_ -> "green")
To do this you must use
HoldPattern[_ -> "green"]
which is the same as
_ -> "green"
for pattern matching. There is an example in the "Possible issues" section in the documentation of Cases.
So we get
In[53]:= Cases[set1, HoldPattern[_ -> "green"]]
Out[53]= {"tree1" -> "green", "tree3" -> "green", "tree7" -> "green"}
