Question

Suppose that \({\bf{e}}\) is an edge in a weighted graph that is incident to a vertex v such that the weight of \({\bf{e}}\) does not exceed the weight of any other edge incident to v. Show that there exists a minimum spanning tree containing this edge.

Short answer

Therefore, the given statement is true. That is, there exists a minimum spanning tree containing this edge.

Step-by-step solution

General form

Definition of tree: A tree is a connected undirected graph without simple circuits.

Definition of Circuit: It is a path that begins and ends in the same vertex.

Deep Search or Backtracking: A procedure for building a spanning tree by adding edges that form a path until it is possible, then backtracking the path until you find a vertex where a new formed path can be created.

Minimum spanning tree: A spanning tree with the smallest possible sum of the edge weights

Proof of the given statement

Given that, e is an edge in a weighted graph G.

e is incident to a vertex v such that \({\bf{\omega }}\left( {\bf{e}} \right) \le {\bf{\omega }}\left( {{\bf{e'}}} \right)\) for all order edges incident to v.

To prove: there exists a minimum spanning tree containing e.

Proof:

Let T contain be a minimum spanning tree that does not contain e.

Adding e to T will then result in a simple circuit being formed in the resulting graph \(T'\).

Let \(e'\) be another edge in the simple circuit C incident to v. Deleting \(e'\) from \(T'\) will then result in a new spanning tree that contains e.

Moreover, since \({\bf{\omega }}\left( {\bf{e}} \right) \le {\bf{\omega }}\left( {{\bf{e'}}} \right)\), the weight of will then be less than or equal to the weight of the original minimum spanning tree T.

Since T is a minimum spanning tree, another tree cannot have a lower weight.

By the definition of a minimum spanning tree, is then also a minimum spanning tree.

Hence proved.