StudySmarter AI is coming soon!

- :00Days
- :00Hours
- :00Mins
- 00Seconds

A new era for learning is coming soonSign up for free

Suggested languages for you:

Americas

Europe

Q33E

Expert-verifiedFound in: Page 803

Book edition
7th

Author(s)
Kenneth H. Rosen

Pages
808 pages

ISBN
9780073383095

**Show that if \(G\) is a weighted graph with distinct edgeweights, then for every simple circuit of \(G\), the edge of maximum weight in this circuit does not belong to anyminimum spanning tree of \(G\).**

**The edge of maximum weight in some circuit of a weighted graph cannot be included in the minimum spanning tree of the graph.**

A minimum spanning tree of a weighted graph \(G\) is a spanning tree of \(G\) with minimal weight.

Given: \(G\) is a connected undirected weighted graph

\(G\) has distinct edge weights

\(C\) is a simple circuit in \(G\)

\(T\) is a minimum spanning tree of \(G\)

To proof: The edge of maximum weight in \(C\) does not belong to \(T\)

Let the edge of maximum weight in \(C\)be\({\bf{e = \{ u,v\} }}\)and let \(e\) belong to \(T\).

Let \({\bf{T' = T - \{ e\} }}\). \({\bf{T''}}\) is then a forest with \(2\) connected components.

Let \(f\) be the edge in the path \({\bf{C - \{ e\} }}\) that is used to "jump" between the \(2\) connected components (this edge has to exists, as \(C\) was a circuit). \(f\) is not an edge in \(T\) (because else \(T\) would contain a circuit).

Since \(e\) is the edge in \(C\) with maximum weight and since \(G\) has distinct edge weights, \(e\) has a larger weight than \(f\)

\(w(e){\bf{ > }}w(f)\)

Let \(T''{\bf{ = }}T \cup \{ f\} {\bf{ - }}\{ e\} \), then the weight of \({\bf{T''}}\) is less than or equal to the weight of \(T\) since \(w(e){\bf{ > }}w(f)\)

\(w(T''){\bf{ < }}w(T)\)

Thus \({\bf{T''}}\) is then a spanning tree with a smaller weight than \(T\). However as \(T\) was the minimum spanning tree, there should not exist a spanning tree with a lower weight and thus we have derived a contradiction. This means that the assumption that \(e\) belongs to \(T\) was wrong (and thus \(e\) cannot belong to \(T\)).

94% of StudySmarter users get better grades.

Sign up for free