3
$\begingroup$

I was wondering if this solution for finding wheter or not two graphs are isomorphic would work: I claim that two graphs are isomorphic if their degree list coincide. For example let's say that I have graphs A and B given by their adjacence matrix like so: $$ A = \begin{pmatrix} 0 & 1& 1 & 1 &0 \\ 1 & 0& 0 & 0 &1 \\ 1& 0 & 0 & 0 &0 \\ 1& 0 & 0 & 0 &1 \\ 0& 1 & 0 & 1 &0 \end{pmatrix} $$

$$B= \begin{pmatrix} 0 & 1 & 1 & 0 & 0\\ 1 & 0 & 0 & 1 & 1\\ 1 & 0 & 0 & 1 & 0\\ 0 & 1 & 1 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 \end{pmatrix}$$

The degree list for A is 3,2,1,2,2 and for B is 2,3,2,2,1. This sets are equal. Therefore I say that A and B are isomorphic. If I am wrong, can you please explain me why is that with a counterexample

$\endgroup$
1
  • $\begingroup$ Note that the graph isomorphism problem is not known to be solvable in polynomial time. If there is a polynomial-time algorithm, expect it to be quite a bit more involved than this. $\endgroup$
    – Kevin
    Mar 18, 2016 at 5:20

3 Answers 3

7
$\begingroup$

Both a $6$-cycle and the graph consisting of two disjoint $3$-cycles have the degree list $2,2,2,2,2,2$.

The conjecture fails even for connected graphs. If you add a diagonal edge to the $6$-cycle and an edge between the two $3$-cycles, you get non-isomorphic graphs with the degree sequence $3,3,2,2,2,2$.

$\endgroup$
4
$\begingroup$

This graph has the same degree sequence as your $A$ and $B$, yet is not isomorphic to them:

  o
 / \
o---o---o---o
$\endgroup$
2
$\begingroup$

The situation is perhaps clearest for k-regular graphs where k > 2. For example, the cubic graphs:

http://mathworld.wolfram.com/CubicGraph.html

not only do these graphs all have the same degree sequences (for equal number of vertices), all the vertices have the same degree.

What I am not sure about is how many graphs in general are the only member of their 'degree sequence family' (class?). Just as most graphs have a trivial automorphism group - that is, are irregular - I suppose that most belong to a relatively small such family.

$\endgroup$

You must log in to answer this question.

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