#graph theory

Question

Comments

Min edges for 6 vertices connected graph=5 therefore with 4 edges graph is not at all connected.Thus removing 6 edges will disconnect the graph?

---

@saxena0612 why not 2 ?

---

it is problem like you give me any such graph and i have my choice to remove any edge , now think in worst case how many edges i took to make your graph disconnect.

---

https://gateoverflow.in/152152/graph

Answer 1

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.