Non-isomorphic simple graphs: order $n$, size $\displaystyle \frac{na}{2}$, degree sequence $(a,a,a,...,a) \in \mathbb{N}^n$

Question

If a simple graph has order $n$, size $\displaystyle \frac{na}{2}$ and degree sequence $(a,a,a,...,a) \in \mathbb{N}^n$ then is it unique up to isomorphism?

I thought of this question while examining the Petersen Graph, which is a simple graph (no multiple edges, no loops) satisfying all of the above with $n=10$ and $a=3$.

I can easily find many $\textbf{non-simple}$ graphs satisfying all of the above which are not isomorphic to each other. I am looking for either a proof, or counterexample in the form of two non-isomorphic simple graphs.

Answer 1

No. Compare the circle on six vertices to the disjoint union of two triangles. Both have six vertices and degree sequence $(2,2,2,2,2,2)$. Check, that the size is determined by this two properties, so it must also be the same.

In case you are asking about connected graphs, compare:

• The complete bipartite graph with three vertices per partition $K_{3,3}$
• The disjoint union of two triangles with three edges added, such that each vertex of a triangle is connected to exactly one vertex of the other triangle.

EDIT: Regarding the Petersen graph, you could create a non-isomorphic graph as follows: Take three disjoint triangles. Connect each two triangles by two non-incident edges. Now each triangle is left with exactly one vertex of degree two. Connect those vertices to a tenth vertex. This graph is not isomorphic to the Petersen graph as it contains triangles.