Determine the number of nonempty subgraphs of K5 Prove that

Determine the number of nonempty subgraphs of K5. Prove that your answer is correct.
Your answer should be an exact number, not just a formula that gives the number.
[Note: This question is not asking for the number of nonisomorphic subgraphs. So, for instance, the
subgraph containing only the vertex v1 and the subgraph containing only the vertex v2 are considered
di erent graphs, even though these two graphs are isomorphic to each other.]

Solution

All the edges and vertices of G might not be present in S; but if a vertex is present in S, it has a corresponding vertex in G and any edge that connects two vertices in S will also connect the corresponding vertices in G.

Hence with only one vertice as subgraphs there will be 5 subgraphs.

With 2 vertices it would be 5C2 subgraphs.

With 3 vertices it would be 5C3 subgraphs.

...

Hence total subgraphs = 5C1+5C2+...+5C5

= 2⁵-1 = 31 subgraphs