Test by Bikram | Mock GATE | Test 4 | Question: 47

Question

An undirected graph has $5$ nodes and $3$ edges. Let $P$ and $Q$, respectively, be the maximum and minimum number of connected components of the graph.

If the graph has no self-loops and there is at most one edge between any pair of nodes, then which of the following conditions is always TRUE?

• A.  $P=5, Q=2$
• B.  $P=4, Q=2$
• C.  $P=3, Q=2$
• D.  $P=5, Q=3$

Comments

@Bikram sir

I agree with ur proof but plz try to understand what I said. If I want to make a complete graph of 3 Edges then at least I need three vertices because i can not make a complete graph of 3 edges in 1 or 2 vertices, right!!

But if i take 3 vertices in order to make complete graph then this will act as one component and remaining two vertices will act as isolated vertices so overall maximum components must be 3, how 4 are coming????

---

@akash

yes, i understand, your assumption is correct.

overall maximum components must be 3 , it can not be 4 as to become 4 components we need to fit 3 edges in between 2 nodes , that can not be possible ...

Thanks for this correction.

---

@Bikram sir

always welcome!!!!

Answer 1

Min number of components =2

Max number of components =3

Answer 2

A Graph G Containing n vertices and k edges, G will contain atleast n-k components. [ minimum ]
Graph containing n vertices and 0 edges will contain n components.Each time adding an edge will reduce the component by 1.Thus k edge will contain n-k component. This is the minimum number. Just check with by putting n = 3 , k = 1 . There are 2 components , minimum .

and n-i+1 = maximum components ( i must be > 2 )

where i = minimum number of connected component

Reference :
https://math.stackexchange.com/questions/2073995/maximum-number-of-components-in-a-graph-containing-n-vertices-and-k-edges?rq=1