Complexity of the maximum leaf spanning tree problem on planar and regular graphs

In this paper, we consider the problem of finding a spanning tree in a graph that maximizes the number of leaves. We show the NPNP-hardness of this problem for graphs that are planar and cubic. Our proof will be an adaption of the proof for arbitrary cubic graphs in Lemke (1988) [9]. Furthermore, it is shown that the problem is APXAPX-hard on 5-regular graphs. Finally, we extend our proof to k  -regular graphs for odd k>5k>5.