GATE CSE
First time here? Checkout the FAQ!
x
0 votes
92 views
When say that with n vertices there are total 2^(n(n-1)/2) connected/disconnected graph possible, in this case we are assuming that vertices are labelled, right??

 

Is there any formula to count number of connected/disconnected graphs possible with n unlabeled vertices?
asked in Graph Theory by Veteran (14.4k points)   | 92 views

1 Answer

–2 votes
The # of labeled undirected graphs : 2^(n(n-1)/2)

The # of labelled directed graphs : 2^(n(n-1))
answered by Active (1.3k points)  
edited by
With 3 unlabeled nodes possible undirected graphs are 4, but your formula gives 8/6 how?
Top Users Feb 2017
  1. Arjun

    5386 Points

  2. Bikram

    4230 Points

  3. Habibkhan

    3952 Points

  4. Aboveallplayer

    3086 Points

  5. Debashish Deka

    2564 Points

  6. sriv_shubham

    2318 Points

  7. Smriti012

    2236 Points

  8. Arnabi

    2008 Points

  9. mcjoshi

    1696 Points

  10. sh!va

    1684 Points

Monthly Topper: Rs. 500 gift card

20,863 questions
26,021 answers
59,689 comments
22,131 users