1
$\begingroup$

if there are two graph $G$ and $H$ that have same number of vertices, and their degree sequences are the same. Does this mean that they are isomorphic ?

$\endgroup$
3
  • 1
    $\begingroup$ Can you think of a counterexample with six vertices each? $\endgroup$ May 2, 2021 at 15:31
  • $\begingroup$ no not really, because their degree sequences are the same, I think they match up the same and their structures are the same $\endgroup$ May 2, 2021 at 15:36
  • $\begingroup$ There are two nonisomorphic graphs with 6 vertices, all of degree 2. Likewise, there are two nonisomorphic graphs (the complements of the ones mentioned before) with 6 vertices all of degree 3. $\endgroup$
    – bof
    May 3, 2021 at 0:10

1 Answer 1

0
$\begingroup$

Look up "graph isomorphism problem". You will find that it is a known hard problem. By contrast, computing the degree sequence is easy. So, by resorting to authority, the answer is "no". More specific reasons are in the comments.

$\endgroup$

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