A spanning tree of the \(2^ m\)-dimensional hypercube with maximum number of degree-preserving vertices (Q686181)

The \(n\)-dimensional hypercube \(Q_ n\) is a graph whose vertices are ordered \(n\)-tuples of 0's and 1's, where two vertices are adjacent iff they differ in exactly one coordinate. \(\deg_ G(v)\) denotes the degree of the vertex \(v\) in the graph \(G\). A degree-preserving (DP-)vertex \(v\) in a tree \(T\) of a graph \(G\) is a vertex satisfying \(\deg_ T(v)=\deg_ G(v)\). It is shown that for a hypercube \(Q_ n\) \((n\geq 2)\) the number of DP-vertices of a spanning tree is at most \({2^ n \over n}\), with equality possible if and only if \(n=2^ m\) holds for some positive integer \(m\).