Thread: A graph theory problem

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?

Many thanks!

These are called 'unlabled' graph of order 5.
You found the only two with the degree sequence <1,1,2,2,2>.

Originally Posted by Plato

These are called 'unlabled' graph of order 5.
You found the only two with the degree sequence <1,1,2,2,2>.

Thanks a lot!

But now I wonder, how can I be sure that I have really found all of the graphs with the degree sequence <1,1,2,2,2> (up to an isomorphism) and that the "search" has been exhaustive?

Do you know about graph cards?
You may find a website for them, I know of none.
Anyway I found them in GRAPHS by Wilson & Watkins.
The two graphs you found are the only to listed on the cards.