Question

When must an edge of a connected simple graph be in every spanning tree for this graph?

Short answer

When the edge is a cut edge, a connected simple graph is in every spanning tree for the graph.

Step-by-step solution

Some definition.

A tree is an undirected graph that is connected and that does not contain any simple circuit.

A spanning tree of a simple graph is a subgroup of G that is a tree and that contains all vertices of G.

A circuit is a path that begins and ends in the same vertex.

A cut edge is an edge that when removed from a graph, the resulting graph has more connected components than the original graph.

Check the result.

Let e be an edge of a connected simple graph.

If e is an edge in some circuit of the simple graph, then the edge e can be removed from the simple graph without disconnecting the simple graph, and thus the edge e does not necessarily need to lie in the spanning tree.

However, if e is not an edge in some circuit of the simple graph, then the edge will need to be an edge in the spanning tree as removing this edge will disconnect the graph.

This implies that the edge e is in every spanning tree of the connected graph when e is a cut edge.

Therefore, when the edge is a cut edge, a connected simple graph is in every spanning tree for the graph.