How many graphs are there with five vertices, where the degrees of those five vertices are 1,1,2,2,2? I suppose we have to find the number of them up to an isomorphism.
If we use the theorem stating that the number of edges in a graph is half the sum of degrees of all vertices, we can see that every graph of the type we are looking for will have edges.
I have managed to find only two such graphs:
In graph , the vertices 1 and 5 are of degree 1, while vertices 2, 3, and 4 are of the degree 2, while in graph , the vertices 1 and 2 are of degree 1, while vertices 3, 4, and 5 are of the degree 2.
How can I be sure there aren't more of such graphs? Is there an effective algorithm to find them? Actually, the problem asks to find how many such graphs are there, just the number, and not to specifically draw each one, making the problem presumably easier?