Find all loopfree undirected connected graphs with five vert

Find all loop-free undirected connected graphs with five vertices up to a graph isomorphism. How many of these have no pendant vertices?

16. Find all loop-free undirected connected graphs with five vertices up to a graph isomorphism. How many of these have no pendant vertices?

Solution

First of all we need to find the number of undirected connected graphs with 5 vertices up to a graph isomorphism.

We know that the maximum number of edges for such a graph with n vertices can be n(n-1)/2. Therefore, maximum number of edges with 5 vertices could be 5*(5-1)/2 = (5*4)/2 = 20/2 = 10

Let us see the distribution of graphs depending based on the number of edges:

Therefore, total number of graphs = 1+1+2+3+4+5+4+3+2+1+1 = 27

Therefore, total number of loop-free, undirected, connected graphs with five vertices up to a graph isomorphism would be 27.

There will be two graphs without any pendant vertices, the one without any edges and one with 10 edges.

Number of edges	0	1	2	3	4	5	6	7	8	9	10
Number of graphs	1	1	2	3	4	5	4	3	2	1	1