Isomorphic graphs

Question

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

Answer 1

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

  o
 / \
o---o---o---o

Answer 2

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

Answer 3

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.