Kenneth Rosen Edition 6th Exercise 8.2 Question 43 (Page No. 554)

Question

How many subgraphs possible with at least one vertex for the following two graphs ? (labelled vertices)

1. $K_3$

2. $W_4$ (total 4 vertices)

Comments

is it 5?

---

K₃ -12

---

@srestha !! Plz check my answer..

Answer 1

Let us calculate for a) part first :

We know :

No of subgraphs  of  K_n  =  Σ ⁿC_r  .  2^r(r-1)/2      where r varies from 1 to n

 Let us see how it comes ..

Since we know that subgraph is defined as :

A subgraph of a graph G is another graph formed from a subset of the vertices and edges of G. The vertex subset must include all endpoints of the edge subset, but may also include additional vertices..

So we first select a given number of vertices , say r vertices out of n vertices which can be done ⁿC_r ways..Now having chosen r vertices , we know for these r vertices , there is edge between every pair..So no of edges that will be given by ^rC₂ = r(r-1)/2..Now each of these edges can either be selected or rejected for subgraph formation..

So no of subgraphs comprising of r vertices out of n vertices of K_n  =  2^r(r-1)/2

Hence we have the above mentioned formula considering all values of r from 1 to n..

So substituting n = 3 , we have :

No of subgraphs possible = ³C₁ . 2^1(1-1)/2  + ³C₂ . 2^2.(2-1)/2   + ³C₃ . 2^3(3-1)/2

                                      =  3 . (1) + 3 . 2  + 8

                                      =  3 + 6 + 8 

                                      =  17

Therefore , we have 17 subgraphs for K₃ complete graph with the 3 vertices being labelled..

Now applying similar procedure for W₄ , which is known as wheel graph of 4 vertices having 3 vertices at corner of a triangle and one vertex in the centre of those 3..So effectively we have 4 traingles forming as a result..

So if r = 1 , i.e. we choose 1 vertex out of 4 for subgraph , we have

No of such subgraphs possible  =  4 [The vertices themselves will form the subgraphs as we have no option but to select a vertex we cannot reject it as then it will not be a graph at all as we require min no of vertices  = 1 for graph]

Similarly for r = 2 , we have no of ways to choose   =   ⁴C₂  =  6

For each of such instance we have 1 edge in between them as clear from th definition of wheel graph , so to form subgraph we can have 2 ways , either to select the edge or reject .

So no of subgraphs of 2 vertices          =    6 * 2    =   12

Similarly for r = 3 , we have no of ways   =   ⁴C₃    =   4

And no of edges for each instance =  3 [As said earlier we have 4 triangles in this graph]

So for an instance of selection of 3 vertices , no of ways corresponding edges can be used to make subgraph  =  2³ = 8

So no of subgraphs comprising of 3 vertices  =   4 * 8  =  32

Lastly , for r  =  4 , we have the graph itself..

No of edges in this graph = 6

So no of ways        =   2⁶ [for each edge we have 2 choices] = 64

Hence no of subgraphs for W₄ with labelled vertices  =   4 + 12 + 32 + 64

                                                                                  =   112

Comments

but how to find number of subgraphs if it is not complete graph