# Vertex degree and graph isomorphism

Suppose I have two simple graphs $G(V,E)$ and $H(V,E)$ with number of vertices $N$. And $\forall i \quad \text{such that}\quad 0<i<N$

No:of elements in $V(G)$ with degree $i$ = No:of elements in $V(H)$ with degree $i$

Where $V(G)$ is the vertex set of $G$.

Given this can we say that $H$ and $G$ are isomorphic?

If they are not isomorphic. Then what is such a relation called?

• If there are $N$ vertices there can only be a maximum degree of $N-1$. Nov 4, 2014 at 15:06
• @LeenDroogendijk: Note that since the number of vertices in $G,H$ is the same, it suffices to check that they have equal numbers of vertices with degrees $i=1,\ldots,N-1$ to prove the same degree sequences (equal numbers of isolated vertices is then forced). Dec 3, 2014 at 2:59

The two graphs $G$ and $H$ satisfying the condition you describe are said to have the same degree sequence. But this does not necessarily imply that the two graphs are isomorphic. It is possible to construct two graphs that have the same degree sequence but which are not isomorphic.