All trees are 1-embeddable and all except stars are 2-embeddable (Q687137)

A graph \(G\) is said to be \(m\)-embeddable if there is a permutation \(p\) of the vertices of \(G\) such that for any \(m\) edges \(e_ 1,e_ 2,\dots,e_ m\) of \(G\), \(E(G) \cap E(\phi(G))=\{e_ 1,e_ 2,\dots,e_ m\}\). In this paper it is proved that all trees of order \(n \geq 3\) are 1-embeddable, and that all trees of order \(n \geq 4\), except the stars, are 2- embeddable. The later result is sharp because there are trees which are not 3-embeddable. According to the authors, this work arose from the related definition of ``\(k\)-free graphs'' studied by them in two earlier papers. (A graph \(G\) is \((| E(G) |-k)\)-free if and only if it is \(k\)-embeddable.) The notion of ``\(k\)-free graph'' is relevant to the Edge-Reconstruction Conjecture in the sense that if a graph \(G\) is not edge-reconstructible then it is \(k\)-free for all even values of \(k\) (proved by Nash-Williams in 1978). Reviewer's remark: A graph \(G\) is 0-embeddable if and only if \(G\) can be embedded into its complement \(\overline G\). Hence the notion of \(m\)- embedding can be considered as a generalization of the notion of ``embedding a graph into its complement''.