A \(\frac{4}{3}\)-approximation algorithm for the maximum internal spanning tree problem (Q2656175)

The problem is to find a spanning tree with maximal number of internal vertices in an undirected graph. It seems to have already earlier attracted some activity. Here, a 7-line verbally formulated algorithm is presented. It is based on a sequence of ideas to reduce the given graph. Performance ratios of \(\frac{4}{3}\) vs. \(\frac{3}{2}\) and others in the literature are discussed.