recategorized by
2,148 views
0 votes
0 votes

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

recategorized by

1 Answer

Best answer
3 votes
3 votes

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

selected by

Related questions

2 votes
2 votes
1 answer
1
Na462 asked Jan 16, 2019
496 views
The number of vertices,edges and colors required for proper coloring in Tripartite graph K<3,2,5 will be :10 , 31 , 310 , 30 , 310 , 30 , 2None
0 votes
0 votes
2 answers
3
0 votes
0 votes
0 answers
4