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
8.0k 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.9k points

No related questions found

Welcome to QAmmunity.org, where you can ask questions and receive answers from other members of our community.

9.4m questions

12.2m answers

Categories