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

formula to get no of simple graph 2^{^}n_{c2 }if n is total vertices

44 votes

1

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

formula to get no of simple graph 2^{^}n_{c2 }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?

19

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

- If labeled graph is considered then answer will be 11.
- If unlabeled graph is considered then answer will be 7.

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

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 .

2

@ankitgupta.1729 @Chhotu sir, in* question they don't say labelled or unlabelled graph.if not mention, then we should always count unlabelled? *

86 votes

6

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

1 node =1

2 node =2

3 node = 8

1+2+8=11

Which is not in option

0

Edge less graph are called Null graph.

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

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

1

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.

1

@Mk Utkarsh

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

Can you provide a reference to this statement.

5

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

41 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.$

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.$

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

23 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)

$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)

13 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$$.

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$$.

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$$

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$$

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?

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.

2 votes

Number of graphs (labelled) possible on n vertices = $2^\frac{n(n-1)}{2}$

So, for upto 3 nodes = $1+2+8=11$

No option matches.

So, the question wants to know it for unlabelled. There's no formula for that, we have to do it manually.

So, by brute force: $1+2+4=7$

**Option C**

1 vote

Minimum no of vertices required for a graph = 1

Number of distinct graphs with 1 node = 1

Number of distinct graphs with 2 nodes = 2 (one without edge and one with edge)

Number of distinct graphs with 3 nodes = 4 (Although total no of possible graphs for 3 nodes is 2 power (n(n-1)/2) = 8, but distinct are 4 as:

1st being null graph in which there is no edge.

2nd being graph in which there is 1 edge.

3rd being graph in which there are 2 edges.

4th being graph in which there are 3 edges.)

So total no of distinct graphs upto 3 nodes = 1 + 2 + 4 = 7.

But this is with the assumption that the nodes are unlabelled.

Had they been labelled, the answer would have been 1 + 2 + 8 =11 and this is not in the option and hence our assumption is correct.

Number of distinct graphs with 1 node = 1

Number of distinct graphs with 2 nodes = 2 (one without edge and one with edge)

Number of distinct graphs with 3 nodes = 4 (Although total no of possible graphs for 3 nodes is 2 power (n(n-1)/2) = 8, but distinct are 4 as:

1st being null graph in which there is no edge.

2nd being graph in which there is 1 edge.

3rd being graph in which there are 2 edges.

4th being graph in which there are 3 edges.)

So total no of distinct graphs upto 3 nodes = 1 + 2 + 4 = 7.

But this is with the assumption that the nodes are unlabelled.

Had they been labelled, the answer would have been 1 + 2 + 8 =11 and this is not in the option and hence our assumption is correct.