The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+26 votes
7.5k views

The number of distinct simple graphs with up to three nodes is

  1. $15$
  2. $10$
  3. $7$
  4. $9$
asked in Graph Theory by Veteran (59.6k points)
edited by | 7.5k views
0
0

ans is 8 simple graph possible if 3 vertices if vertices set {A,B,C} then edge set nc2= {AB,BC,CA} and possible simple graph is 2*2*2=8

formula to get no of simple graph 2^nc2 if n is total vertices 

0
@Leen. The 1994 question says "....upto 3 nodes" which means 1/2/3 nodes. But here, exactly 3 nodes are required. COuld you plz tell what should be the answer? If unlabbeled, then only 3, and if labelled then 8, right?
+5

Notice line "up to three nodes" in the question. Now

  1. If labeled graph is considered then answer will be 11.
  2. If unlabeled graph is considered then answer will be 7.
0

What is the difference between this question and this(link)

+1
@y Syedarshadali
there are two major difference
1. in this question ..it is told that nodes are up to 3 ...means here we r allowed to use less than 3 node too...but for question (link) all nodes are compulsory....
2. here node are taken as unlabled...(link) node are considered as lebeled
0
it is not said to take label of node if u do without labeling of nodes u will  reach at ri8 conclusion .

7 Answers

+52 votes
Best answer

answer = option (C)

answered by Boss (30.8k points)
edited by
0
best explanation
+4
why have we considered unlabelled vertices?
+1
I had the same doubt. If you try with labeled upto 3 nodes:-

1 node =1

2 node =2

3 node = 8

1+2+8=11

Which is not in option
0
What about null graph ? If 8 is in the option, I think that we have to go with 8.
0
its upto 3 nodes, why have we not considered null graph, null graph is also a simple graph?
0
do you know what is null graph?
0
Edge less graph are called Null graph.

But where it is mentioned that we have to take unlabelled graph.
0

Shubhanshu where it is mentioned we need to take labeled graph?

and Rajesh R if 8 was in option still 7 is the correct answer because a null graph(a graph without any vertices) is not considered a simple graph. 

0

@Mk Utkarsh 

 a null graph(a graph without any vertices) is not considered a simple graph. 

Can you provide a reference to this statement. 

0

I was wrong

http://oeis.org/A005470/list

here the list mentions graph with no vertex so yeah we can say that 8 is the answer.

0
Thanks :)
+1

There is no standard definition of Null Graph. Null Graph may refer to a graph in which set of vertices and edges both are empty or it may also refer to a graph(also called an empty graph or edgeless graph) in which set of vertices is a non-empty set but set of edges is an empty set.

So, here for this question , answer can be (7) or (8) but mostly resources consider edgeless graphs as null graphs if $n$ $\geqslant$ $1$.

http://mathworld.wolfram.com/EmptyGraph.html

http://mathworld.wolfram.com/NullGraph.html

https://en.wikipedia.org/wiki/Null_graph

https://math.stackexchange.com/questions/1196921/is-there-any-difference-between-empty-graph-and-null-graph

 

 

 

0
@amar can we take disconnected graphs also??
+29 votes
Answer: C

The number of max edges a simple graph can have is $\frac{n×(n−1)}{2}$.

So, for a graph with $3$ nodes the max number of edges is $3.$
Now there can be $0$ edges, $1$ edge, $2$ edges or $3$ edges in a $3$ node simple graph.
So the total number of unlabeled simple graphs on $3$ nodes will be  $4.$
Similarly for two node graph we have option of $0$ or $1$ edge and for one node graph we have option of $0$ edge.
So the total number of simple graphs upto three nodes $=4+2+1=7.$
answered by Boss (34.1k points)
+1

why not we count null graph (which have 0 node) that is also be countable.

and one more doubt is in the question they don't say count label or unlabel graph.if not mention, then we should always count unlabel

0

A simple graph, also called a strict graph (Tutte 1998, p. 2), is an unweighted, undirected graph containing no graph loops or multiple edges (Gibbons 1985, p. 2; West 2000, p. 2; Bronshtein and Semendyayev 2004, p. 346). A simple graph may be either connected or disconnected.

mathworld.wolfram.com/SimpleGraph.htm

0
can i say it is $2^n - 1$?
0

Sourabh Kumar according to this http://oeis.org/A005470/list 8 is the answer

+17 votes
With n number of nodes, max edges are possible $\frac{n(n-1)}{2}$ in a simple graph. each edge has two choices, it'll be taken in a graph or it won't be taken. so total no of graphs are possible
$2^{\frac{n(n-1)}{2}}$.
in the question, it is asked upto three nodes:
with 1 node total graph possible = 1
with two nodes graph possible = 2
with three nodes, possible graphs= $2^{\frac{3(3-1)}{2}}  = 2^3 = 8$   but there are 3 non distinct graphs which are isomorphic to each other, so with n=3 nodes total graphs possible = 8 but total unique graph possible = 4

upto 3 nodes $1 + 2 +4 = 7 $hence answer is (C)
answered by Boss (41k points)
edited by
0
in 7,you have not counted null graph? why?

total unique graph means?
0

" but there are 3 non distinct graphs which are isomorphic to each other, so with n=3 nodes total graphs possible = 8 but total unique graph possible = 4"

did not understand this part

 

+12 votes
The number of max edges a simple graph can have is $n\times (n-1)/2$.

So, for a graph with $3$ nodes the max number of edges is $3$.

Now there can be $0$ edges, $1$ edge, $2$ edges or $3$ edges in a $3$ node simple graph.

So the total number of unlabled simple graphs on 3 nodes will be  $4$.

Similarly for two node graph we have option of $0$ or $1$ edge.

So the total number of simple graphs upto three nodes are:

$$4 + 2 + 1 = 7$$
answered by Active (2.5k points)
0

for a graph with 3 nodes the max number of edges is 2 rt?

0
what about three node complete graph?
0
sorry.. I was thinking for a single node.
0
Guys  , I'v solved in this way  

3 nodes have maximum 3 edges , so total no of distinct simple graph   

3C0+3C1+3C2+3C3

= 1+3+3+1=8 .... where's the mistake?
0
that will be the answer for number of labeled graph with exactly 3 edges. You need to account in for different nodes also.
+1
1. What would be the answer if nodes were labelled??

2. In this question it is not given whether graph is labelled or not, then why we are assuming it to be unlabelled one
0
what does it meant ?

Similarly for two node graph we have option of 0 or 1 edge.
0
it means either we can take edge between the 2 node or not.
+10 votes
A graph is an ordered pair (V,E). So, given a set V, graph will be different if E is different. Lets see how many different E we can get when |V| = 3.

For |V| = 3, we can have |E| = 0, 1, 2 or 3. So, 4 possible graphs.

Now, the question asks for |V| upto 3. So, we have to consider |V| = 2 and |V| = 1 also. When |V| = 2, we can have |E| = 1 or 0, so 2 possibilities. For |V| = 1, |E| can be only 0 and hence only one possibility.  So, total number of possibilities is $$4 + 2 + 1  = 7$$.
answered by Boss (18.3k points)
edited by
0
this won't work, having an edge on one node means there is some other node with one edge also.
0
Yes. That was a bad mistake. I have corrected it now.
0 votes

ans should be 11:

here they said upto three three nodes means we have |V|=1, or |V|=2,  or |V|=3

here total possible graph are 11

answered by Loyal (8.3k points)
+3
you are counting "labeled" graph. but in the question I guess they didn't ask number of labeled graphs. so 11 option is not there.
0
you are right, if it is unlabelled then only we can say ans is 7. they have not mentioned anything in the question. but from options we have to go by unlabelled only. agree with you. thanks.
–5 votes
No of graphs= No of 1 node graph + No of 2 node graph+ No of 3 node graph.

No of 1 node graph =1,

No of 2 node graph is 2.

No of 3 node Graph is 3C2*2=6( Choice of choosing 2 nodes from 3 node is 3C2, and for each choice possibility is 2,either they will be joined  by edge or not.)

So Answer will be 1 +2+6=9. Option D.
answered by (105 points)
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

42,610 questions
48,608 answers
155,777 comments
63,777 users