553 views
1 votes
1 votes

2 Answers

1 votes
1 votes

We would like to have maximum degree for a vertex whose removal will have disconnected graph for sure.

Now, (m-1) vertices can be connected using (m-2) edges which is spanning tree and rest n-(m-2) edges are used for connceting vertex 1 to some vertices of  (m-2) vertices.

THus, min edges to be removed = n - (m - 2) = n - m + 2

0 votes
0 votes
We know that number of edges in any spanning tree is m-1. Here m is the number of vertices. Now, it is also known that if you remove any 1 vertex from spanning tree will make the graph disconnected. Now the number of edges which are not part of spanning tree will be mC2-(m-1).

Here mC2 is maximum number of edges possible in a graph.

Therefore, removing

(mC2-(m-1))+1 edges will always guarantee that graph will be disconnected.

In the question, option should be

mC2-m+2.

Related questions

0 votes
0 votes
0 answers
1
abhishekbhingarde asked Jan 6
95 views
Consider a strongly connected directed graph G(V, F), where |V| = 101. The minimum possible value of IEl is
0 votes
0 votes
0 answers
2
jugnu1337 asked Nov 12, 2023
174 views
Suppose A is a 12 by 9 incidence matrix from a connected (but unknown) graph with 12 edges and 9 nodes. Then how many columns of A are independent?what this question want...
0 votes
0 votes
1 answer
3