195 views

Number of subgraphs possible for K3 =____________

| 195 views
0
7 unlableled subgraphs.
0
how?
0
for unlabeled subgraphs, there is no formula,

you have to find it manually.
0

but ans for K3=17

K4=106

0
i have given answer for unlabeled graphs,

17 is for labeled graph.

it should be mentioned in qsn that graph is labeled.
0
its assumed that graphs are not labeled

+1 vote

• 33 subgraph as consider single - vertices ( question does not mention about distinct so we will consider all cases )
• 33 subgraph consider 22 vertices
• 11 subgraph consider 33 vertices
• 33 subgraph consider  22 vertices, one edge
• 33 subgraph consider 33 vertices, 22 edges
• 33 subgraph consider 33 vertices, 11 edge
• 11 subgraph consider 33 vertices, 33 edges

So, total 17

by Active (4.2k points)
selected
0
$\sum_{r=1}^{n}\binom{n}{r}$2^r*(r-1)/2 applying this formula  3+6+8>>17 ans rest what is said by joshi nitish
0
@Akshat Sharma ,can u please give some reference regarding this  formula ?

Subgraph G'(V',E') of a graph G(V,E) is when V'⊆V and E'⊆E.

Let G has 3 vertices A,B and C.

Subgraphs with one node:

V'={A} and E'=null. There can be 3 such graphs.

Subgraphs with two nodes but no edges:

V'={A,B} and E'=null. There can be 3 such graphs V'={B,C} and {C,A}.

Subgraphs with two nodes and one edge:

V'={A,B} and E'={AB}. 3 such cases.

Subgraphs with 3 nodes and no edge.

V'={A,B,C} and E'=null. 1 case.

Subgraphs with 3 nodes and one edge.

V'={A,B,C} and E'={AB}. Again 3 cases.

Subgraphs with 3 nodes and two edges.

V'={A,B,C} and E'={AB,BC}. 3 cases.

Subgraphs with 3 nodes and 3 edges.

V'={A,B,C} and E'={AB,BC,CA}. 1 such case.

Total subgraphs = 5*3+1+1 =17.

by Boss (23.5k points)
0
Manually is better but carefully check all possible case