Question

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?

Answer 1

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.

Answer 2

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!