Question

a. Suppose a weighted undirected graph had distinct edge weights. Is it possible that every minimal spanning tree includes the edge of maximal weight? If true, under what conditions would it happen?

b. Suppose a weighted undirected graph had distinct edge weights. Is it possible that no minimal spanning tree includes the edge of minimal weight?

c, Is it possible for the root of a tree to have a degree less than a leaf of the tree?

Answer 1

Part a answer

Sample graph for question first part

if a vertex has no edge other than maximum weight edge we have to include this maximum weight edge

If other edges inclusion add cycle to tree but maximum edge addition would not add cycle to tree we add maximum edge in spanning tree

Part b answer

if edge weights are unique we have to include minimum weight edge and build tree with respect to weight edge to get minimum spanning tree if we dont include minimum weight edge we get a spanning tree but weight of this spanning tree is greater than minimum spanning tree .This is standard property of distinct undirected egde weights graph.you can try to get a spanning tree for above graph or any other distinct edge weight graph excluding minimum weight edge you will not get a minimum spanning tree

Part c answer

degree of node in a tree is no of children a node has

Root has zero or more than zero children (zero childern in the case when there is only node and in other case root has more than one children)

Leaf node does not have any children so degree of leaf is always zero

It is not possible to have degree of leaf greater than root

If you are having any doubts please ask i will answer asap