  We present a polynomial time algorithm that for any graph G and integer k >=
0, either finds a spanning tree with at least k internal vertices, or outputs a
new graph G' on at most 3k vertices and an integer k' such that G has a
spanning tree with at least k internal vertices if and only if G' has a
spanning tree with at least k' internal vertices. In other words, we show that
the Maximum Internal Spanning Tree problem parameterized by the number of
internal vertices k, has a 3k-vertex kernel. Our result is based on an
innovative application of a classical min-max result about hypertrees in
hypergraphs which states that "a hypergraph H contains a hypertree if and only
if H is partition connected."
