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

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 .