in Graph Theory edited by
623 views
1 vote
1 vote
Number of distinct simple graphs possible, given 8 vertices and not considering self loops?
in Graph Theory edited by
623 views

2 Answers

4 votes
4 votes
Best answer
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.
selected by

3 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.
2
2
Yes your method is correct and I think your way is easier than mine
0
0
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
0
0
1 vote
1 vote
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

Related questions