Let's have a tree and the task is to find the maximum subset (by cardinality, by the number of edges) of edges such that no 2 edges are adjacent (have no common vertex). Tree has n edges and the task is to find this subset of edges in O(n) time.
I have found simple solution in non-linear time: every tree can be considered as the bipartite graph and every subset of non-adjacent edges in this graph is the matching and the so - the task reduces finding maximal mathcing in bipartite graph. But https://www.wikiwand.com/en/Maximum_cardinality_matching lists only algorithms with nonlinear time (that reduces to maximum flow problem that can be solved by Ford-Fulkerson or Edmund-Hopcroft algorithm.
Is there linear-time algorithm? Maybe I can map my problem back: prove, that every maximum-flow problem can be converted to matching problem, to maximum subset problema and hence prove that no optimal algorithm exists for maximum subset initial problem?