1
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ If there are $N$ vertices there can only be a maximum degree of $N-1$. $\endgroup$
    – biryani
    Nov 4, 2014 at 15:06
  • 1
    $\begingroup$ @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). $\endgroup$
    – hardmath
    Dec 3, 2014 at 2:59

1 Answer 1

Reset to default
4
$\begingroup$

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.

There is no known list of graph properties (be it the degree sequence, any other graph invariant, or even a combined list of such invariants) that provides a sufficient condition for two given graphs to be isomorphic.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .