3,683 views
3 votes
3 votes
Assume undirected graph G is connected . G has 6 vertices and 10 edges. Find the minimum number of edges whose deletion from graph G is always guaranteee that it will become disconnected

3 Answers

Best answer
10 votes
10 votes

We know : 

A tree is a minimally connected acyclic graph which contains n vertices and (n-1) edges..

Hence if a graph of n vertices contain less than (n-1) edges , then it will always guarantee that the resulting graph is disconnected..

So given we have 6 vertices and 10 edges at present..So 

Minimum number of edges required for connectivity  =  5 edges..

So if a graph contains 4 edges it will be disconnected.

Hence no of edges that need to be deleted   =    10  -  4    =   6

selected by
3 votes
3 votes
Number of edges in graph = 10

So sum of indegree of all vertices = 10*2 = 20

let a,b,c,d,e,f be the indegree of 6 vertices

So a+b+c+d+e+f = 20

Now, consider the following values of this variables

5 + 3 + 3 + 3 + 3 + 3 = 20

that means minimun indegree here is 3

So if we remove 3 edges from that vertex then the graph will become disconnected.

From above example we conclude that removing only 1 or 2 edges will not make the graph disconnected.

Now let us assume that removing 3 edges will also not make the graph disconnected. That means vertices in the graph have indegree greater than 3. That means the vertices have indegree 4 or 5 only. Lets us assume that 'x' vertices have indegree 4 and 'y' vertices have indegree 5. Then the two possible equations that they must satisfy are:

4x + 5y =20 and-----------------------------( sum of indegree of all vertices =20 )

x + y =6------------------------------------( total number of vertices = 6 )

if u solve this we will not get valid value of x and y

That means we cant make the graph having vertices with indegree only 4 or 5.

Hence answer should be 3.
1 votes
1 votes

see 3 is correct but not 6,5,4,3,2,1  why reason is 

first for 6 , given no of vertices is 6 in simple graph 'n' vertices maximum degree is n-1 means as given 6 vertices and  one vertex should have maximum 5 edges  so 6 edges not possible in case of minimum

second for 5 , only degree sequence possible is 5,3,3,3,3,3 so in this graph minimum degree is 3 whose removal makes graph disconnected 

third for 4 ; degree sequence possible is 4,4,4,4,2,2 , so in this graph minimum degree is 2 whose removal makes garph disconnected

forth for 3, same above 5,3,3,3,3,3 so min degree is 3

fifth for 2 ; degree sequence possible is 4,4,4,4,2,2 same above

sixth for 1; no degree sequence possible

so total 2 graph possible 1st have degree sequence is 4,4,4,4,2,2 let named is G1

2nd have degree sequence is 5,3,3,3,3,3 let named is G2

in G1 '2' edges removal graph disconnected and G2 '3' edges  removal graph disconnected 

now what should be the answer see question  "minimum number of edges whose deletion from graph G is always guarantee"  now removing min edge 2 work only for G1 not G2 bu  removing min edge 3 always guarantee for G1 as well as G2  so ans is 3 minimum edge

Related questions

0 votes
0 votes
0 answers
1
Malusi asked Jan 12
88 views
Consider a weighted undirected graph with positive edge weights and let (u, v) be an edge in the graph. It is known that the shortest path from source vertex r to u hasw...
0 votes
0 votes
1 answer
3
Dknights asked Dec 12, 2023
349 views
which of the following statements is true:a complete graph is $(N-1)$ regulara $(N-1)$ regular is a complete graph
1 votes
1 votes
1 answer
4