1,280 views
2 votes
2 votes

Number of subgraphs possible for K3 =____________

2 Answers

Best answer
1 votes
1 votes

  • 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

selected by
2 votes
2 votes

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.

Related questions

0 votes
0 votes
2 answers
1
#Rahul asked May 18, 2017
1,807 views
If there are two graphs G1 and G2 and both are Isomorphic to each other...Is G1 subset of G2?
0 votes
0 votes
1 answer
2
Saurav asked Aug 27, 2015
1,396 views
The predessor subgraph of BFS is a tree but the predecessor subgraph of DFS is a forest ?? please explain why??
2 votes
2 votes
2 answers
4