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

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.

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
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
by

1
765 views
1 vote