+1 vote
159 views
The total number of non isomorphic graph which can be formed with 3 vertices________________________
asked | 159 views

+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 Veteran (10.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

i think it is 4...

NULL,one edge,two edge,three edge...
answered by Boss (7.8k 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??

+1 vote