Graphs in which every spanning tree is an independency tree

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.)

• Any graph in which an induced cycle must contain only cut vertices has this property. I don't know if this is a characterization. Sep 6, 2013 at 13:34
• This is clearly not a characterization. A counterexample is provided by a bull-graph. Sep 6, 2013 at 13:52
• Every edge $\lbrace u,v\rbrace$ is either incident with a leaf, or $\lbrace u,v\rbrace$ is a separating set. Sep 6, 2013 at 14:21
• Does this mean that every such graph has at least one leaf? Sep 6, 2013 at 14:51
• I think that it can be shown that such graphs are not $2$-edge-connected. Taking a spanning tree $T$ with two adjacent vertices $u,v$ of degree $2$ and then add a proper edge from the cycle passing through $uv$ and remove $uv.$ One then obtains a spanning tree in which $u$ and $v$ are leaves. There is some technicality in assuring the chosen edge is not incident with $u$ and $v$ though. Sep 6, 2013 at 17:02

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.

• While this is a correct and useful, I remain unsatisfied. It should be possible to give a more structural description. Might this be correct: Take any connected graph, attach one or more new leaves to every vertex that is not a leaf or a cut-vertex. ?? Sep 8, 2013 at 2:05
• @BrendanMcKay I think, this construction does not produce all graphs having all spanning trees independency. Could you please be more specific? Sep 8, 2013 at 9:05
• Bull-graph again? Sep 8, 2013 at 9:34
• @Sergiy : Yes, it didn't quite work. The idea in my head is that an end-edge can be replaced by an arbitrary tree, and vice-versa, without destroying the property. So reduce every attached tree to an end-edge and what remains? Sep 8, 2013 at 9:44
• @vb le : Please see my previous comment. The software doesn't allow two 'at' flags. Sep 8, 2013 at 9:45

Here's something more about these graphs.

Theorem: Let $G$ be connected graph with $\geq 3$ vertices. Consider the next properties:

1) Every edge in $G$ is incident to a cut vertex.

2) $G$ has all spanning trees independency.

3) The set of all cut vertices in $G$ is dominating.

Then 1)$\Rightarrow$2)$\Rightarrow$3).

Proof

1)$\Rightarrow$2): Let $e=uv\in E(G)$ and $u$ is a cut vertex in $G$. Assume that $v$ isn't a leaf. Then $G-u$ is disconnected and $d_{G-u}(v)\geq 1$. Therefore $G-\{u,v\}$ is also disconnected. Thus $\{u,v\}$ is a separator in $G$.

2)$\Rightarrow$3): Assume that for some non-cut vertex $u\in V(G)$ the set $N(u)$ consists of non-cut vertices. Then for all $v\in N(u)$ the set $\{u,v\}$ is a separator in $G$. It means that $v$ is a cut vertex in $G-u$.

If there exists a component $A$ of $G-\{u,v\}$ such that $V(A)\cap N(u)=\emptyset$, then $A$ is also a component of $G-v$. It means that $v$ is a cut vertex in $G$ which is a contradiction. Thus every component of $G-\{u,v\}$ contains the vertices from $N(u)$.

Therefore, each vertex $v\in N(u)$ separates the set $N(u)-v$ in $G-u$. But this contradicts the connectedness of $G-u$. $\boxtimes$

Two counterexamples to the reverse statements of the Theorem.

2)$\nRightarrow$1):

3)$\nRightarrow$2): $K_{1}+(P_{2}\cup K_{1})$.

For the sake of completeness here's the proof of McKay's characterization. By $L(G)$ I denote the set of all leaves in $G$.

Theorem: Every spanning tree in $G$ is independency tree if and only if every edge $e=uv\in L(G)$ is incident to a leaf or the set $\{u,v\}$ is a separator in $G$.

Proof: $\Rightarrow$ Assume that for some edge $e=uv\in E(G)$ the set $\{u,v\}$ isn't a separator and $u,v\notin L(G)$. Then the graph $H=G-\{u,v\}$ is connected.

Now fix some spanning tree $T'\subset H$.

Since $u,v\notin L(G)$, it holds that $A=N_{G}(u)\cap V(T')\neq\emptyset$ and $B=N_{G}(v)\cap V(T')\neq\emptyset$. Choose $w_{1}\in A$, $w_{2}\in B$ and put $$V(T)=V(G),\ E(T)=E(T')\cup\{uw_{1},vw_{2}\}.$$ Clearly, $T$ is a spanning tree in $G$ and $u,v\in L(T)$ with $uv\in E(G)$ which is a contradiction.

$\Leftarrow$ Let $T\subset G$ be some spanning tree and $u,v\in L(T)$. Clearly, $G-\{u,v\}$ is connected. Therefore the set $\{u,v\}$ never a separator.

Again, assume that $e=uv\in E(G)$. Then $d_{G}(u)\geq 2$ and $d_{G}(v)\geq 2$. It means that $u,v\notin L(G)$. Again, a contradiction.

• Eppstein's answer IS a (simple and nice) proof of McKay's characterization. Sep 7, 2013 at 14:20

Here's a construction showing that the answer may be a bit complicated. Take any connected graph $G$, then add an additional set $X$ of $|V(G)|$ vertices, then add a perfect matching $M$ between $V(G)$ and $X$. Let the resulting graph be $G'$. It is easy to see that any spanning tree $T'$ of $G'$ must consist of $M \cup T$, where $T$ is a spanning tree of $G$. Thus, the only leaves of $T'$ are the vertices in $X$, which are indeed an independent set.

Therefore, the structure of such graphs may not be so nice, since any connected graph can be extended in this way to be in the class.