CODEWITHSUNDEEP
algorithmcombinationsanalysiscombinatorics
Emma
Emma

Reputation: 47

How many undirected graphs are there on 3 vertices?

An undirected graph contains 3 vertices. How many undirected graphs can be formed? I tried the combination formula but the answer was wrong.

Upvotes: 2

Views: 40488

Answers (4)

MBo
MBo

Reputation: 80287

Graph with N vertices may have up to C(N,2) = (N choose 2) = N*(N-1)/2 edges (if loops aren't allowed).

So overall number of possible graphs is 2^(N*(N-1)/2).

Upvotes: 12

soporific312
soporific312

Reputation: 187

For the directed graph case, wouldn't the number of graphs be given by the equation 2 ^ (n ^ 2) by the same logic as that of the undirected graph case (assuming self-loops are allowed)? In particular, all vertexes can have n outgoing edges (again, including the self-loop). Therefore n ^ 2 (or n * n) represents the maximum number of edges possible for the graph. Since we make a choice for each edge whether to include it or not, the maximum number of graphs is given by 2 ^ (n ^ 2). Can anyone confirm this?

Upvotes: 1

nits.kk
nits.kk

Reputation: 5336

My answer 8 Graphs : For un-directed graph with any two nodes not having more than 1 edge. A graph with N vertices can have at max nC2 edges. 3C2 is (3!)/((2!)*(3-2)!) => 3. So you can compute number of Graphs with 0 edge, 1 edge, 2 edges and 3 edges.

At max the number of edges for N nodes = N*(N-1)/2 Comes from nC2 and for each edge you have option of choosing it in your graph or not choosing it and with each option you get a unique graph and it gives the formula : 2^(N*(N-1)/2) graphs possible.

If nodes are named a, b, and c then

All Disconnected nodes : 0 edge

a  b  c

= 1 Graph

only 2 nodes connected : 1 edge

a--b  c
b--c  a
c--a  b

= 3 graphs

all 3 nodes connected : 2 edges

a--b--c (c--b--a will be same)
a--c--b ( b--c--a will be same)
b--a--c (c--a--b will be same)

= 3 nodes

all 3 nodes connected : 3 edges 

a--b--c--a

= 1 Graph

So total 8 Graphs. Other way of looking at it is for each edge you have 2 options either to have it or not have it there by making 2 raised to the power 3 (2 choices and 3 edges) making 8 as answer.

For Directed graph we will have more cases to consider, I am trying below to find the number of graphs if we could have Directed graph (Note that below is for the case where we do not have more than 1 edge between 2 nodes, in case we have more than 1 edge between 2 nodes then answer will differ)

0 edge

a b c = 1 Graph

1 edge

a-->b c
a<--b c
b-->c a
b<--c a
c-->a b
c<--a b

= 6 Graphs

2 edges

a-->b-->c
a-->b<--c
a<--b-->c
a<--b<--c
b-->a-->c
b-->a<--c
b<--a-->c
b<--a<--c
a-->c-->b
a-->c<--b
a<--c-->b
a<--c<--b

= 12 Graphs

3 Edges

a-->b-->c-->a
a-->b-->c<--a
a-->b<--c-->a
a-->b<--c<--a
a<--b-->c-->a
a<--b-->c<--a
a<--b<--c-->a
a<--b<--c<--a

= 8 Graphs

Total = 1 + 6 + 12 + 8 = 27 Graphs

Upvotes: 2

Matsmath
Matsmath

Reputation: 1224

You should decide first if you want to count labelled or unlabelled objects. Let's assume that your graph is simple, that is: no loops or multiple edges.

If you are counting labelled objects, then you are counting the number of symmetric 0-1 matrices with 0s on the diagonal (that is, the adjacency matrices of the graphs). There are 2^(1+2...+n-1)=2^(n(n-1)/2) such matrices, hence, the same number of undirected, simple graphs. For n=3 this gives you 2^3=8 graphs.

If you are counting unlabelled objects, then you are counting the number of graphs up to graph isomorphism. This is a much more difficult question. Some computational data is available in the website of Online Encyclopedia of Integer Sequences (OEIS) website for larger n: https://oeis.org/A000088. From this website we infer that there are 4 unlabelled graphs on 3 vertices (indeed: the empty graph, an edge, a cherry, and the triangle).

Upvotes: 2

Related Questions