41.3k views
0 votes
Prove that a pendant edge, namely an edge whose one end vertex is of degree one, in a connected graph (V,E) must be contained in every spanning tree of (V,E).

User Ivanz
by
7.4k points

1 Answer

3 votes

Final answer:

A pendant edge in a connected graph must be contained in every spanning tree because its exclusion would result in an isolated vertex, thereby not satisfying the definition of a spanning tree which includes all vertices.

Step-by-step explanation:

A pendant edge in a graph is an edge that is connected to a vertex of degree one. In a connected graph (V, E), a spanning tree is a subgraph that includes all the vertices of the original graph with the minimum number of edges such that there is a path between any two vertices.

Now, let's consider the property of a spanning tree. A spanning tree must connect all vertices with the least number of edges, which is |V| - 1 (where |V| is the number of vertices). Since a vertex with degree one is only connected to one other vertex, the only edge it has must be part of the spanning tree; otherwise, it would not satisfy the condition of being a spanning tree.

If we were to exclude the pendant edge from our spanning tree, then the vertex with degree one would become isolated, contradicting the definition of a spanning tree which must include all vertices. Therefore, it is evident that every spanning tree of the graph will contain the pendant edge connected to a degree-one vertex, ensuring all vertices are included in the spanning tree.

User Blazehub
by
7.6k points