322 views
1 votes
1 votes

1 Answer

Best answer
2 votes
2 votes
A graph needs atleast $n-1$ to remain connected. Given $ \#vertices =6$ we require atleast $5$ edges to be connected. Now having $10$ edges, we can remove $6$ edges to make the number of edges as $4$. Thus, the given graph with $4$ edges would be definitely disconnected.

Proof: The most lightly connected graph is a chain for $n$ vertices. Removing any edge from the chain breaks it. Hence $n-1$ edges are required to keep a graph connected.

Note: Just because there are $n-1$ edges, we cannot reason that the given graph is connected. Eg: A $3-vertex$ cycle and an additional isolated node has 3 edges. But still the graph is disconnected.
selected by

Related questions

0 votes
0 votes
1 answer
1
Çșȇ ʛấẗẻ asked Jul 3, 2023
514 views
Prove that following graph does not have Hamiltonian cycle.
0 votes
0 votes
1 answer
2
iarnav asked Apr 9, 2018
475 views
A connected graph ‘G’ may have at most (n–2) cut vertices.
1 votes
1 votes
0 answers
3
0 votes
0 votes
1 answer
4
Abhijeet_Kumar asked Dec 22, 2017
651 views