Embedding Trees in the Hypercube The( 2q-1)-node complete binary tree even weight is not a subgraph of the q-cube odd weights ○○. Q. even weights Proof by contradiction based on the parity of node label weights(number of 1s in the labels) The 2q-node double-rooted complete even weights binary tree is a subgraph of the g-cube odd weights lew roots NC(NEx) Fig 13.6 The 2q-node N(N fx) double-rooted 入△八 complete binary tree is a subgraph of 2q-node double-rooted Double-rooted tree Double-rooted tree the g-cube plete bi n the ((q-1 ube O n the((q-1)cube Fa2010 Parallel Processing, Low-Diameter Architectures Slide 15Fall 2010 Parallel Processing, Low-Diameter Architectures Slide 15 Embedding Trees in the Hypercube The (2 q – 1)-node complete binary tree is not a subgraph of the q-cube even weight odd weights even weights odd weights even weights Proof by contradiction based on the parity of node label weights (number of 1s in the labels) The 2 q -node double-rooted complete binary tree is a subgraph of the q-cube Fig. 13.6 The 2q -node double-rooted complete binary tree is a subgraph of the q-cube. New Roots x N (N (x)) N (N (x)) 2 -node double-rooted complete binary tree q Double-rooted tree in the (q?)-cube 0 Double-rooted tree in the (q?)-cube 1 N (x) c N (x) b N (x) a b c c b N (N (x)) N (N (x)) c a a c （q -1） （q -1）