TAOCP 7.2.2.1 Exercise 204
Let d=\deg(\alpha), \qquad d'=\deg(\alpha').
Section 7.2.2.1: Dancing Links
Exercise 204. [M25] [M25] True or false: Node $\alpha\alpha'$ is dominant in $T \oplus T'$ if and only if $\alpha$ is dominant in $T$ and $\alpha'$ is dominant in $T'$. Hint: Express $\deg(\alpha\alpha')$ in terms of $\deg(\alpha)$ and $\deg(\alpha')$.
Verified: yes
Solve time: 42s
Solution
Let
$$ d=\deg(\alpha), \qquad d'=\deg(\alpha'). $$
By the definition of the operation $\oplus$ in the preceding section, the degree of the node $\alpha\alpha'$ satisfies
$$ \deg(\alpha\alpha')=d+d'. $$
The hint requests precisely this relation.
A node is dominant if its degree is strictly greater than the degree of each of its children. Let the children of $\alpha$ have degrees
$$ d_1,d_2,\ldots,d_m, $$
and let the children of $\alpha'$ have degrees
$$ d'_1,d'_2,\ldots,d'_n. $$
The children of $\alpha\alpha'$ in $T\oplus T'$ are of the two forms
$$ \beta\alpha', \qquad \alpha\beta', $$
where $\beta$ is a child of $\alpha$ and $\beta'$ is a child of $\alpha'$. Their degrees are
$$ \deg(\beta\alpha')=d_i+d', \qquad \deg(\alpha\beta')=d+d'_j. $$
Assume first that $\alpha\alpha'$ is dominant in $T\oplus T'$. Then
$$ d+d'>d_i+d' $$
for every child $\beta$ of $\alpha$. Subtracting $d'$ from both sides gives
$$ d>d_i, $$
so $\alpha$ is dominant in $T$. Similarly,
$$ d+d'>d+d'_j $$
for every child $\beta'$ of $\alpha'$, hence
$$ d>d'_j, $$
after subtracting $d$, so $\alpha'$ is dominant in $T'$.
Conversely, assume that $\alpha$ is dominant in $T$ and that $\alpha'$ is dominant in $T'$. Then
$$ d>d_i $$
for every child $\beta$ of $\alpha$, and
$$ d'>d'_j $$
for every child $\beta'$ of $\alpha'$. Adding $d'$ to the first inequality yields
$$ d+d'>d_i+d'=\deg(\beta\alpha'), $$
and adding $d$ to the second yields
$$ d+d'>d+d'_j=\deg(\alpha\beta'). $$
Thus $\deg(\alpha\alpha')$ exceeds the degree of every child of $\alpha\alpha'$, so $\alpha\alpha'$ is dominant in $T\oplus T'$.
Both implications have been proved. Therefore the statement is true.
$$ \boxed{\text{True: }\alpha\alpha'\text{ is dominant in }T\oplus T' \iff \alpha\text{ is dominant in }T\text{ and }\alpha'\text{ is dominant in }T'.} $$
This completes the proof.
∎