• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon

Suggested languages for you:

Americas

Europe

Q33E

Expert-verified
Found in: Page 803

### Discrete Mathematics and its Applications

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.

See the step by step solution

## Step 1: Definition

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$$

## Step 2: Proof by contradiction

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)$$

## Step 3: Weight of edge

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$$).