in G whose leaves include all vertices that are not in D: form a spanning tree of the subgraph induced by D, together with edges connecting each remaining vertex v that is not in D to a neighbor of v in D. This shows that ''l'' >= ''n'' − ''d''.

In the other direction, if T is any spanning tree in G, then the vertices of T that are not leaves form a connected dominating set of G. This shows that ''n'' − ''l'' >= ''d''. Putting these two inequalities together proves the equality 1=''n'' = ''d'' + ''l''.

Therefore, in

1.Previous
3.Next