It follows from this question
and the corresponding answers, that the complete graphs and the cycles are precisely the graphs
$G$ having the property that, for every spanning tree $T$ of $G$, the set of leaves of $T$ is a
clique in $G$.
Motivated by this fact, I am looking for a characterization of all (connected) graphs $G$
having the property that, for every spanning tree $T$ of $G$, the set of leaves of $T$ is an
independent set in $G$.
(Such spanning trees are called independency trees
in the literature.)
Best Answer
A graph G has all spanning trees independency if and only if G does not contain two adjacent vertices v and w, neither of degree one, such that the graph G' formed by removing v and w and all their incident edges is connected. (I think this is the same as what McKay said in a comment.)
For, if G' is connected, then a spanning tree of G' plus two edges connecting it to v and w (which exist by the degree constraint) is a non-independency tree of G. And conversely, if T is a non-independency tree, let vw be an edge connecting two leaves of T; then v and w have the stated property.
As a check that this is a useful characterization (and not just a restatement of the definition): Based on this, it is trivial to test in polynomial time whether a given graph has all spanning trees independency, whereas a direct translation of the original definition into an algorithm would be exponential.
ETA: In response to McKay's request for a more structural characterization, here's a description of the graphs with all trees independency, rather than (as above) of the complementary class of graphs. Given a graph G, partition G into its biconnected components, and partition each nontrivial biconnected component into its SPQR tree (system of triconnected components). Then G has all trees independency if and only if, for every non-virtual edge of an R or S node of one of these SPQR trees, at least one endpoint is an articulation vertex. (This is because the edges that do not separate two triconnected components are exactly these edges, so to avoid leaving G' connected they have to instead separate two biconnected components.) And again, this is an improved characterization and not just a restatement of the earlier characterization, because it gives a linear time algorithm while a naive implementation of the earlier characterization would be a higher polynomial.