Omid Hatami wrote: Suppose that $ T$ is a tree with $ k$ edges. Prove that the $ k$-dimensional tree can be partitioned to graphs isomorphic to $ T$. What's the definition of "the $ k$-dimensional tree"?

Oh, it is $ k$-dimensional cube.

I think it's similiar to the 8th problem of Iran's 14th Informatics Olympiad (2nd round)

I think induction works..... ???

Clearly, a $ k$-dimensional cube has $ 2^k$ vertices, each one joined to $ k$ other vertices (one edge in each direction of space), for a total of $ 2^{k - 1}k$ edges, ie, the $ k$ dimensionaly cube must be decomposed in exactly $ 2^{k - 1}$ graphs with $ k$ edges. Denote the vertices of a $ k$-dimensional cube by $ (a_1,a_2,\dots,a_k)$, where each $ a_i$ takes values either $ 0$ or $ 1$. Define a family of operations $ O$ consisting on taking any vertex, and exchanging an EVEN number of its coordinates from 1 to 0 or from 0 to 1. This same family of operations may be applied to any graph which is part of the $ k$-dimensional cube as follows: take all its vertices and apply to them the same operation (ie, exchange in every vertex of the graph the same coordinates, choosing an even numbe of them). Next, draw an edge between any two transformed vertices iff there was an edge between them in the corresponding vertices before transformation. Claim:

Proof (by induction): The base case $ k = 2$ is trivial:

Induction step:

Note that we have proved the following stronger result:

I am sorry if my proof is equivalent to the above, but I think this is a cleaner way to construct the partition: Let the k-dimensional cube be the convex hull of the set of points $(a_1, \dots, a_k) \in \{0, 1\}^k$. It is well known that a k-dimensional cube has $2^k$ vertices and $2^{k-1}k$ edges. Let the vertices be $0, 1, \dots, 2^k - 1$, where the number of a vertex $(a_1, \dots, a_k)$ is $\sum_{i =0}^{k-1} 2^i a_i$. Root the given tree and let the edges be $e_0, \dots, e_{k-1}$. We will construct each of the $2^{k-1}$ trees as follows: The root is an integer with an odd number of ones in its binary representation in $\{0, 1, \dots, 2^k - 1\}$ Each vertex $v$ has the same number of children as in the original tree, and moreover, if an edge connecting him to his children is $e_q$, the number of his child is the number $v \oplus 2^q$ ($v$ with the $q$-th bit flipped). Obviously, that edge is possible because the respectible points differ only in one dimension. There are $2^{k-1}$ roots (number of subsets of a set with $k$ elements which have odd cardinality), so we have $2^{k-1}$ trees with $k$ edges each. If no two trees share an edge, it's the partition we are looking for. Assume that there is an edge $AB$ in two different trees. WLOG $A$ is the parent of $B$ in one of them. Since $AB$ is an edge, they differ only in one same bit in both of the trees, i.e. it's the same $e_q$ in both trees. If $A$ is the parent in the second tree too, $A$ is on the same place in both trees. Inductively, the root is the same also, which is a contradiction. If instead $B$ is the parent in the second tree, it's on the same place in the second tree as $A$ in the first tree. $A$ and $B$ have different parity of the number of ones in their binary representations, so inductively the roots of the trees have different parity of the number of ones. But all roots have the same parity of the number of ones, contradiction.

Label the vertices of the hypercube with the $2^k$ binary strings in the obvious way. Let the parity of a vertex be the parity of the number of $1$s in the binary string of that vertex. Finally, label the vertices of $T$ by $v_0,v_1,\ldots,v_k$. We have the following stronger claim which implies the problem. Claim: The edges $k$-hypercube can be partitioned into $2^{k-1}$ copies of $T$, such that for any fixed $i$, all the vertices corresponding to $v_i$ in the partition have the same parity. Note that a vertex of the hypercube could be a vertex for multiple trees in the partition, but for a given tree in the partition, we can find the unique vertex which is the $v_i$ of that tree. Proof: We proceed by induction on $k$, with the case of $k=1$ being obvious as the only possibility for $T$ is a single edge, and the $k$-cube is also a single edge. There is no parity matching to check since there is only one tree. Now suppose that the claim is true for $k-1$. We'll show that it is true for $k$. Suppose WLOG that $v_0$ is a leaf in $T$ and $v_0v_1$ is the edge incident to it. Now, consider a partition of the $(k-1)$-cube into trees isomorphic to $T'$, which is $T$ with the leaf $v_0$ and its corresponding edge deleted. Use this for the half of the $k$-cube with first coordinate $0$ (which is a $(k-1)$-cube), and use the partition's reflection (so all the parities get swapped) for the other half which has first coordinate $1$. As of now, the edges between the two halves are missing and the trees are still incomplete, but all the parities match, since the two halves are different parities, but we reflected the partition for the second half. Now, since all the $v_1$s have the same parity, we can add a single edge at each $v_1$ that connects the two halves for each tree which has that vertex. This clearly completes each tree since the newly added edge only touches $v_1$ since it goes into the other half, and all the parities of the newly added $v_0$s are the same, the exact opposite parities of the $v_1$s. This completes the induction, and thus the proof. $\blacksquare$

We will prove a stronger statement: We can label the edges of the tree $T$ (and the nodes), then partition $Q_{n}$ into $2^{n-1}$ $T$ graphs in a way that no adjacent edges in $Q_{n}$ have the same label in their $T$. In other words, for each vertex $v$ in $Q_{n}$, every label has an edge that contains $v$. We will prove this by induction. Our base case is $n = 0$, and since there are no edges, we are done. Now, assume it is true for $n-1$, we will prove it for $n$. Observe that the graph $Q_{n}$ is formed by taking two graphs $Q_{n-1}$, then for each vertex is the first $Q_{n-1}$, we connect it to a vertex in the second $Q_{n-1}$ that has not been connected yet. Colour the edges in the first $Q_{n-1}$ red, the edges in the second $Q_{n-1}$ blue, and the connecting edges as green. Next, consider $T$, and label its edges from $1$ to $n$ such that the edge with label $n$ has a leaf. Let the tree without the edge $n$ be $S$. By our inductive hypothesis, we can partition the red $Q_{n-1}$ into graphs isomorphic to $S$ such that every vertex contains every label from $1$ to $n-1$. Do the same thing for the blue $Q_{n-1}$, but the root of each blue $S$ can't be adjacent to the root of a red $S$, and do it "symmetrically", where for each blue node $v$, it can't be adjacent to a red node $v$. Finally, we can add the edge $n$ back, such that they are the green nodes. If edge $n$ contains node $u$ which isn't a leaf, then since no red $u$ is adjacent to any blue $u$, the green edges of edge $n$ won't intersect, and furthermore no two blue or red $u$ are on the same node (it would violate the hypothesis that every vertex has exactly one edge of each label). Thus, we can then partition $Q_{n}$ into graphs isomorphic to $T$. Furthermore, since every edge $n$ is green, and no green edges are adjacent, our inductive step is proving, so we conclude that this is possible for all $n$.

In fact we can partition $Q_n$ such that: No two parallel edges are in the same tree, If we mark the same corresponding vertex on each tree $T$, we will mark exactly half the vertices in a way such that no two marked vertices share an edge. (In particular, we don't mark any vertex twice.) We will prove that $Q_n$ can be partitioned, as described by the latter of the two bullets, using induction on $n$. Base case: $n=1$, nothing to prove. Inductive step: Let $T'$ be $T$ with one leaf (and the edge attached to it) removed. Our inductive hypothesis tells us $Q_{n-1}$ can be partitioned into $2^{n-2}$ copies of $T'$. Furthermore, if we color each vertex of $Q_{n-1}$ black and white alternating, in each copy of $T'$, corresponding vertices are all black or all white. Make another copy of $Q_{n-1}$, partitioned and colored the same way - call this copy $R_{n-1}$. We connect $Q_{n-1}$ and $R_{n-1}$ to form $Q_n$ – in particular, we take each vertex of $Q_{n-1}$ and connect it to a vertex of opposite color in $R_{n-1}$. That way, the $Q_n$ we form is still colored like a checkerboard. Now we can add back the leaf to each $T'$ to form $T$. WLOG assume that for each $T'$, the leaf $\ell$ attaches to that $T'$ on a black vertex. If $T'$ is in $Q_{n-1}$, then $\ell$ is a white vertex in $R_{n-1}$; if $T'$ is in $R_{n-1}$, then $\ell$ is a white vertex in $Q_{n-1}$. In each case, $\ell$ is connected to $T'$ via one of the $2^{n-1}$ edges we drew from $Q_{n-1}$ to $R_{n-1}$.

Color the vertices of $Q_n$ as a "chessboard," and let $N_1, N_2, \ldots, N_n$ be the vertices of $T$. We will prove by induction that there exists a partition of $Q_n$ into graphs isomorphic to $T$ that satisfies the following: 1.- All vertices equivalent to $N_i$ are distinct for all $i = 1, 2, \ldots, n$. 2.- All vertices equivalent to $N_i$ are of the same color for all $i = 1, 2, \ldots, n$. For $n = 2$, such a partition obviously exists. Now, suppose there is such a partition for some $n \in \mathbb{Z} \geq 2$. Let $T_{n+1}$ be a tree with $n+1$ edges, and let $N_1, N_2, \ldots, N_n, N_{n+1}$ be its vertices numbered such that $N_{n+1}$ is only connected to $N_1$. Let $T_n$ be the tree obtained by removing $N_{n+1}$ from $T_{n+1}$. By hypothesis, we can provide a partition of $Q_n$ into graphs isomorphic to $T_n$ that satisfy the conditions. Moreover, $Q_{n+1}$ contains two disjoint subgraphs isomorphic to $Q_n$. (This isomorphism also considers coloring). In these two graphs, all vertices equivalent to $N_n$ are of the same color. By adding the edges connecting these two graphs, all the $N_n$'s are given an edge that connects them with a point of another color in the other graph. To each of these vertices that connect with the $N_n$'s, we can assign $N_{n+1}$ to obtain a partition of $Q_{n+1}$ into graphs isomorphic to $T_{n+1}$ that satisfy the conditions, thereby concluding the proof.