Edge that does not appear in ANY spanning tree?

Question

I have a problem that just puzzles me...

I am told I have a graph $G$ and asked what I can say about an edge that appears in no spanning tree of $G$.

My question is...is there such an edge to start with? So, okay if an edge exists, it simply connects two vertices...so if I wrote out every single possible spanning tree, i.e. every single combination of edges of vertices, then that means an edge appears at least once in the set of spanning trees, right?

I just can't think of an example of an edge that does not appear in any spanning tree of a graph $G$.

Can anyone come up with one??

Answer 1

Consider a spanning tree. Then adding your edge $e$ creates a cycle. Removing any other edge of this cycle creates a spanning tree containg $e$. Hence there is no other edge in the cycle, which means that the edge must be a loop.

Answer 2

You can say $G$ is disconnected.

Suppose $G$ is connected. Since $G$ is connected it contains at least on spanning tree. Lets call this tree $T$. Now consider the edge $uv$. Take $T$ and assume it does not contain edge $uv$ (if it does we are done), since $T$ is a tree it contains a unique path between $u$ and $v$ label this path $ux_1\dots x_nv$ Remove the edge $ux_1$ and replace it by $uv$ and call this new graph $T'$. We now prove this new graph is connected.

We wish to prove vertices $a$ and $b$ are connected. $a$ and $b$ where connected in $T$ so there is a path between them. Is this path did not contain edge $ux_1$ it is also a path in $T'$. If the path contained $ux_1$ then swap $ux_1$ for $uvx_nx_{n-1}\dots x_1$ and we get a trail in $T'$ that connects $a$ and $b$, this trail can be shortened to a path if required. We have that $T'$ is also connected and since it has the same number of edges as $T$ it is also a tree.