Spanning tree with many leaves in quadratic graph

Many problems arising in computer science can be viewed as a problem of, given a graph, finding a spanning tree that satisfies a specified property.Another large class of properties deals with the structure of the leaves of the spanning tree.Here, we wish to find a spanning tree with a Lower bound on maximum number of leaves (NP-complete problem).Applications of this problem include communications networks, circuit layout, and graph Theoretic problem.A polynomial algorithm for constructing full spanning trees for 4-regular (Quadratic) graph is presented.For a connected graph G let L(G) denote the maximum number of leaves in any spanning tree of G.We give a simple construction and a complete proof that if G is a connected quadratic graph on n vertices, then L (G) ≥ 2n/5 +2.The main idea is to count the number of "dead leaves" as the tree is being constructed.