The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
141 views
The total number of non isomorphic graph which can be formed with 3 vertices________________________
asked in Graph Theory by Veteran (70.1k points) | 141 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

answered by Boss (6.6k 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

@Aish

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

Maximum till 4 vertices have been asked..you can see this for reference

https://gateoverflow.in/105987/non-isomorphic-graphs 

0 votes
i think it is 4...

NULL,one edge,two edge,three edge...
answered by Active (1.9k 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

thanks:)
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

29,006 questions
36,838 answers
91,329 comments
34,718 users