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??
Best Answer
Consider a spanning tree of $G$. Then adding your edge $e$ creates a cycle. Removing any other edge of this cycle creates a spanning tree containing $e$. Hence there is no other edge in the cycle, which means that the edge must be a loop.