Set of edges not contained in any spanning tree

Question

The question is as follows: Prove that in a graph $G$ a set of edges $X$ which is not contained in any spanning tree is a cycle (or possibly an edge disjoint union of cycles).

My thoughts: Proceed by contradiction.

Any help will be appreciated.

Answer 1

Your statement seems wrong. The good property is : if $X$ is not contained in any spanning tree, then $X$ contains a cycle.

Notice that if $X$ contains a cycle, $X$ isn't contained in any spanning tree (since a spanning tree is cycle-free), so that we couldn't prove any stronger property.

You can prove the property by contradiction :

• First notice that for $X \subset E$ that does not contain a cycle, then $X$ is included in a spanning tree. Just add edges to $X$ as much as you can without creating a cycle, and you get a spanning tree. This is because, if a vertice $k$ is not on one of the edges of $X$, then you can add an edge from $X$ to $k$ without creating a cycle.

  If you can't add any edge, this means $X$ is a spanning tree.

  (Both Kruskal and Prim algorithm make us of this property).

• Thus, by contradiction, if $X$ isn't included in any spanning tree, then $X$ must contain a cycle.