Let us calculate for a) part first :
We know :
No of subgraphs of Kn = Σ nCr . 2r(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 nCr 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 rC2 = 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 Kn = 2r(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 = 3C1 . 21(1-1)/2 + 3C2 . 22.(2-1)/2 + 3C3 . 23(3-1)/2
= 3 . (1) + 3 . 2 + 8
= 3 + 6 + 8
= 17
Therefore , we have 17 subgraphs for K3 complete graph with the 3 vertices being labelled..
Now applying similar procedure for W4 , 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 = 4C2 = 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 = 4C3 = 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 = 23 = 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 = 26 [for each edge we have 2 choices] = 64
Hence no of subgraphs for W4 with labelled vertices = 4 + 12 + 32 + 64
= 112