Discrete math Please write your answer neatly so that I can

Discrete math. Please write your answer neatly so that I can read it, thanks.

How many non-isomorphic simple graphs are there on n vertices when n is 2? 3? 4? and 5?

Solution

Two simple graphs are isomorphic if we can redraw one of them so that it appears exactly like the other. Otherwise, they are said to be non-isomorphic.

Hence to find out simple non-isomorphic graphs we have to find out different possibilities where the graphs cannot be redrawn to resemble the other.

Let\'s start with n=2.

When we have 2vertices, we can have two possibilities:

1) one where the two vertices are joined by an edge

2) one where the two vertices are not joined by an edge

Therefore when n=2, and 0 edge we have 1 graph and for n=2, and 1 edge we have 1 graph, so total 1+1 = 2 non-isomorphic graphs for n=2.

So when n=2, answer is 2.

Now for n=3, we follow a similar procedure.

Let\'s evaluate the number of graphs for n=3:

1) We can have a graph where with three vertices and 0edges so 1 possibility

2) We can have two of the three vertices connected by an edge. To elaborate we can have a graph with three vertices and only 1 edge between any two of the three vertices. So only 1 possibility. We cannot consider here as 3 graphs with edges between the three vertices as different since they would be isomorphic and it contradicts the definition of non-isomorphic graphs. So only 1 possibility.

3) We can have a graph with three vertices and two edges which again gives us one possibility. Here also we cannot count three different graphs since they would become isomorphic as explained in point 2 above. So only 1 possibility.

4) Until now we have n=3 and 0 edges - 1graph

n=3 and 1 edge - 1graph

n=3 and 2 edges - 1 graph.

So, now we consider n=3 and 3 edges which(you can imagine of as a triangle for example) gives 1 graph again.

Therefore total for n=3, we have 1+1+1+1 = 4 simple non-isomorphic graphs can be drawn.

Now, lets consider the case for n=4.

Following a similar procedure,

1) n=4 and 0 edges we have 1 graph.

2) n=4 and 1 edge we have 1 graph

3) n=4 and 2 edges we can have 2 graphs, one with a common vertex(Imagine case where one side and a diagonal of a square are joined through a common vertex)

and one without a common vertex(Imagine case as two parallel sides of a square) So, we have 2 graphs.

4) n=4 and 3edges, we can now break this into two possibilities. We can add an edge to a 2-edge graph(as in point 3) without a common vertex so we get 1 graph

or we can add an edge to a 2-edge graph(as in point 3) with a common vertex, we get three possibilities but one will be similar to the graph of adding an edge to a 2-edge graph without a common vertex so only two distinct possibilities.

So for n=4 and 3 edges we get total 1+2 = 3 graphs.

5) For n=4 and 4 edges think of it as similar to (two n=4 and 2 edge graphs) so we will get 2 graphs.

6) For n=4 and 5edges think of it as similar to adding an edge to a 4-edge graph( as in point 5) so you will get 1 graph.Imagine as three sides of a square are drawn and two diagonals are drawn so 5edges in total.

7) For n=4 and 6 edges imagine it as a square with all four sides and two diagonals drawn so 6edges so just 1 simplegraph.

Therefore, total for n=4, is 1+1+2+3+2+1+1 = 11 simple non-isomorphic graphs.

Let\'s consider the last case where n=5.

Total number of edges possible is 10.

So for n=5, 0 edge - 1graph

n=5,1 edge - 1graph

n=5, 2 edges - 2 graphs

n=5,3 edges - 4 graphs

n=5, 4 edges - 6 graphs

n=5, 5 edges - 6 graphs

n=5,6 edges - 6graphs

n=5, 7 edges - 4 graphs

n=5 , 8 edges - 2graphs

n=5, 9edges - 1graph

n=5,10edges - 1 graph

Therefore total for n=5 vertices is 1+1+2+4+6+6+6+4+2+1+1 = 34 non-isomorphic simple graphs.

Therefore, we have

Let me know if you have any doubts regarding the solution. Will be happy to help you answer and clear them.

Thank you for using Chegg.

Vertices	Number of non-isomorphic simple graphs
2	2
3	4
4	11
5	34