How many undirected graphs can be constructed out of a given set V={v1, v2… vn} of n vertices

# Undirected graphs

**shweta**#2

For given n no of vertices ,

Total no of possible edges =n*(n-1)/2 .

Now, for every edge, there are to possible options, either we pick it or don’t pick.

So total number of possible graphs is 2n(n-1)/2.

**APU**#3

Answer:

In an undirected graph, there can be maximum of n(n-1)/2 edges. We can choose to have (or not have) any of the n(n-1)/2 edges.

So, total number of undirected graphs with n vertices is

2^(n(n-1)/2).