MadeEasy Test Series: Discrete Mathematics - Graph Thoery

Question

The number of labelled subgraphs possible for the graph given below.

Comments

112 is the answer for k4.. the solution to the given question in the mock test is wrong

---

check the solution given below..don't know any formulae..i just follow the procedure.

---

formula for subgraph Kn

https://gateoverflow.in/219583/number-of-subgraphs-of-kn

Answer 1

One vertex sub-graphs: 4C1 (number of ways of picking one vertex among the four)

Two vertices sub-graphs: 4*2^1 (whether to include the edge available between the given selected set of vertices) + 2 * 1 as there is no edge between these set of vertices.

Three vertices sub-graphs: 4C3 * 2^2 (two edges incident on the any selected 3 vertices, 2^2 different ways of having/not-having these edges in the sub-grah)

Four vertices sub-graphs: 4C4 * 2^4 ( four edges)

Total number of subgraphs: 4 + 10 + 4C3 * 2^2 + 4C4 * 2^4 = 46

Comments

Bro, u commented as 112 now posted answer as 48?

:(

---

sorry..112 was for k4..mistyped it

---

@balchandar reddy san

"Two vertices sub-graphs: 4C2 * 2 (whether to include the edge available between the given selected set of vertices)"

what if the 2 out of 4 vertices, b and d are selected and there is no edge between b and d, how can you consider the possibility of selecting and edge?? :/

---

he is correct 112 will be  for k4 and if graph will be  changed than no fixed formula to that only we can apply counting

---

@chauhansunil20th Yes..you are right, in that case it will be 4*2 + 2*1 which will be 10 for Two-vertex sub-graphs...updated the answer

---

nice catch bro. very fine point .

---

What about null graph?

Should we have to consider it or not?

---

As in the question we are asked to find the number of labelled sub-graphs, so i assumed null graph won't be included.

---

no empty graph will not be consider. it is not only in labeled also in unlabebeled. i think u want to ask empty graph. null graph have no edges and empty graph have no vertex and no edges also.

---

bro u consider null graph in ur counting like if u take 4C0 and no edges than that was null graph .