Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
    
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. – Kevin Mar 18 at 5:20
up vote 4 down vote accepted

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

  o
 / \
o---o---o---o
share|cite|improve this answer

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$.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.