The Gateway to Computer Science Excellence
+1 vote
The total number of non isomorphic graph which can be formed with 3 vertices________________________
in Graph Theory by Veteran (119k points) | 187 views

2 Answers

+1 vote

Number of vertices are 3, maximum edges possible in this graph is C(3,2) = 3

Necessary condition for two graphs to be isomorphic is 

1) They have same no of vertices

2) They have same no of edges

3) They have same degree sequence

4) They must preserve adjacency

We have 3 edges to make graph, so we have possible choices to draw no edge, 1 edge, 2 edge or 3 edge.

Graph with no edge:

Only 1 non isomorphic graph is possible.

Graph with 1 edge

But all three graphs are isomorphic to each other(satisfying above conditions), so only 1 non isomorphic graph is possible.

Graph with 2 edges

Similarly, these are also isomorphic to each other, so only 1 non isomorphic graph is possible

Graph with 3 edge

This is a complete graph of 3 vertices


Only 1 non isomorphic graph is possible.

In total there are 1+1+1+1 = 4 non isomorphic graphs possible with 3 vertices

Hence 4 should be the correct answer

by Boss (16.4k points)
@ahswani but since this is only 3 vertices it was easy to draw and check

what abt when it goes to about 10 vertices or more

there should be some other way i think


We have to follow the same approach to solve this, there might be any other method.

Maximum till 4 vertices have been can see this for reference 

0 votes
i think it is 4...

NULL,one edge,two edge,three edge...
by Loyal (8.2k points)
4 graphs
how did u get these sequence of degrees

how do u find them (non isomorphhic graphs)
i was mistaken,

possible edges are 0,1,2,3

so 4 non isomorphic graphs

ans is  not matching

@srestha what is the given answer??

what is the approach to finding the non isomorphic graph??
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
50,737 questions
57,398 answers
105,456 users