A result on k-valent graphs and its application to a graph embedding problem (Q1820789)

It is proved that any n-vertex, k-valent undirect simple graph, G, contains a spanning tree with at least \(\frac{(k-2)n}{(5k-8.5)}\) leaves. As a result of this it is shown that any such graph contains an independent set, of size at least n/5k, with the property that deleting the vertices in this set and their incident edges does not disconnect G. This latter result is applied by giving an improved upper bound on the area required to embed arbitrary graphs into grid graphs.