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

Summary It is proved that any n-vertex, k-valent undirected simple graph, G, contains a spanning tree with at least 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.