2 votes 2 votes Kindly justify with an example Algorithms minimum-spanning-tree + – Pawan Kumar 2 asked Jan 14, 2018 Pawan Kumar 2 431 views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply Manu Thakur commented Jan 14, 2018 reply Follow Share (c) is false if the given graph is connected and has (n-1) edges. 2 votes 2 votes Pawan Kumar 2 commented Jan 14, 2018 reply Follow Share Manu Thakur ,Sir, so every MST will have emax included in it... because every MST has n-1 edges ... am i right sir ? 0 votes 0 votes prateekdwv commented Jan 14, 2018 reply Follow Share Counterexample of option (c): Consider any arbitrary graph with a pendant vertex (say $\mathcal{A}$). Also, let $e_{max}$ of this graph will be the pendant edge (edge incident on $\mathcal{A}$). There is only one way to connect pendant vertex to the rest of the graph, i.e., through $e_{max}$. Hence MST of such a graph must contain $e_{max}$. 2 votes 2 votes Pawan Kumar 2 commented Jan 14, 2018 reply Follow Share prateekdwv SIr .. Thanks :) 0 votes 0 votes Please log in or register to add a comment.