IISc CDS (MTech-R)

Question

Number of distinct simple graphs possible, given 8 vertices and not considering self loops?

Answer 1

Suppose we formed a simple graph with 8 vertices.

Then it will have one unique adjacency matrix representation.

So, the number of simple graphs with 8 vertices = no. of 8×8 symmetric matrices whose elements are either 0 or 1 except the diagonal elements which are zero always.

Now, a 8×8 matrix has 64 cells. Substracting the diagonal cells we have 56 cells. On the upper half of the matrix has (56/2) = 28 cells

Now, for each of the 28 cells we have 2 options 1 or 0.

So,the number of 8×8 symmetric matrices where the elements are either 0 or 1 except the diagonal elements are 2^28

So,the number of simple graphs with 8 vertices is 2^28.

Comments

Thank you for the quick response.

I got the answer like this:

No. of edges=8C2=28

Each edge may be present or absent so 2 ways.

Hence total =2^28 , just wanted to cross check.

---

Yes your method is correct and I think your way is easier than mine

---

In the question i don't know whether given vertices are labeled or not. 2^28 is correct if labeled vertices else many of the graphs amongst them will be isomorphic to each other hence different number of graphs will be less

Answer 2

Number of ways of selecting edges= n(n-1)/2

Now, every edge can be selected or rejected,So for each edge we have 2 ways of selection.

So, for n(n-1)/2 edges , we have 2^(n(n-1)/2) of selecting i.e 2^28