Log In

Recent posts tagged iitk

We have two subgraphs G1 and G2. G1 has k vertices and G2 has n-k vertices. Consider G2. Since we have 2 edge-disjoint spanning trees for G, each vertex in G2 must have two edges leaving it. These edges has only two possibilities- either go to some other vertex in G2 or go to a vertex in G1. In ... cases, it won't add to a an edge in G1. So, maximum edges in G1 = |E| - 2(n-k) =2n-2 -2n+2k =2k-2
posted May 22, 2017 in Interview Experience Digvijaysingh Gautam 3,361 views
To see more, click for the full list of questions or popular tags.