Non-isomorphic bipartite Graphs with same degree sequence and cycles

Question

I am still trying to understand the graph isomorphism problem for bipartite graphs. I know two bipartite graphs cannot be isomorphic if they do not possess the same degree sequence or not the same number of cycles of length $k$. I know that these two conditions are not sufficient to check for isomorphism, but I am still trying to understand why, as I couldn't find any counter example.

Are there non-isomorphic, bipartite graphs which cannot be distinguished this easily? So are there two non-isomorphic, bipartite graphs with the same number of $k$-cycles for all integers $k$?

Answer 1

Any two trees with the same degree sequence will do. Trees have no cycles, so in particular, they have $0$ cycles of length $k$ for any integer $k$. (Also, they have no cycles, so in particular, they have no odd cycles, and therefore they are bipartite.)

Here is a small example of two trees with the same degree sequence:

o--o--o--o--o         o--o--o--o--o
   |            and         |
   o                        o

(They are not isomorphic because only the first tree has two leaves with a common neighbor.)