# Trees with the same degree sequences

Constructing trees with the same degree sequences I've got this problem.

Let $G$, $H$ be the trees (simple graphs) with the same degree sequences. Is it true that there always be vertices $q\in V(G)$ and $q′\in V(H)$ such that $(q,p)\in E(G)$ and $(q′,p′)\in E(H)$ for some endvertices $p\in V(G)$ and $p\in V(H)$, and $d(q)=d(q′)$?

$d(q)$ - degree of the vertex $q$.

I haven't found counterexample for trees up to $8$ vertices, and it's seems impossible to me.

Have you references for some results concerned with trees with the same degree sequences?

-
Concerning (3), should the $D$'s be there? –  Tony Huynh Oct 1 '10 at 19:41
Thank you! Corrected) –  Alexander Oct 1 '10 at 20:01

Consider two trees $G$ and $H$ with 14 vertices. Both will have degree sequence $(2,0,6,6)$ i.e. having two vertices of degree 4. $G$ will have the two 4-vertices connected to 3 leaves each and with a 6 vertex long chain between them. $H$ will have the two 4-vertices connected with a single edge. In addition, each will have three 2 vertex long chains connected to them (one 2-vertex connected to a leaf).

Finally, each leaf of $G$ is connected to a 4 vertex and each leaf of $H$ is connected to a 2 vertex.

A picture would do the trick better.

-
Please, give me adjacency matrices of these trees. It would do the trick better) –  Alexander Oct 1 '10 at 21:41
Thank you, daniel! Got it. There's no need for adjacency matrices. –  Alexander Oct 1 '10 at 22:08
Of course, there is a simpler example with 10 vertices. Perhaps I can even draw: =>-<= and >-----< . –  daniel Oct 1 '10 at 22:22
Thank you, Daniel! You help me. My english not so good to say HOW MUCH you help me, indeed) –  Alexander Oct 2 '10 at 9:05

Let $G$ be the Dynkin diagram of $A_5$ and $H$ be the Dynkin diagram of $D_5$. Then $G$ can be extended to the Dynkin diagram of $E_6$, while $H$ can be extended to the Dynkin diagram of $D_6$. These examples satisfy your conditions. I would draw them, as they are not much more elaborate than paths, but my tex skills are not that good!

-
Thank you for the answer, damiano. I know this already) I just have formulated the problem quite incorrectly. Sorry. Indeed, the problem is formulating as follows. Let $G$ and $H$ be the trees with the same degree sequences. Is it true that there always be vertices $q\in V(G)$ and $q′\in V(H)$ such that $(q,p)\in E(G)$ and $(q′,p′)\in E(H)$ for some endvertices $p\in V(G)$ and $p\in V(H)$, and $d(q)=d(q′)$? $d(q)$ - degree of the vertex $q$. –  Alexander Oct 1 '10 at 20:32
Of course, $G$ and $H$ are not isomorphic. –  Alexander Oct 1 '10 at 20:39