[proofplan] We prove [Tucker's lemma](/theorems/6480) by contradiction. Assuming that an antipodal labeling by the $2d$ labels $\{\pm 1,\dots,\pm d\}$ has no complementary edge, Ky Fan's lemma with $m=d$ produces an alternating $d$-simplex. Such a simplex has $d+1$ vertices whose absolute labels are pairwise distinct, but only $d$ absolute labels are available. This contradiction forces the existence of a complementary edge. [/proofplan] [step:Assume a Tucker labeling with no complementary edge] Let $K$ be a centrally symmetric triangulation of the $d$-sphere, and let $\lambda: V(K) \to \{\pm 1, \dots, \pm d\}$ be an antipodal vertex labeling. Thus, for every vertex $v \in V(K)$, the antipodal vertex $-v \in V(K)$ satisfies \begin{align*} \lambda(-v) = -\lambda(v). \end{align*} Assume, toward a contradiction, that $K$ has no complementary edge. This means that for every edge $\{u,v\}$ of $K$, \begin{align*} \lambda(u) \neq -\lambda(v). \end{align*} [/step] [step:Apply Ky Fan's lemma with $m=d$] The labeling $\lambda$ takes values in $\{\pm 1,\dots,\pm d\}$, is antipodal, and has no complementary edge by the contradiction assumption. Therefore the hypotheses of Ky Fan's lemma in dimension $d$ with $m=d$ are satisfied. By Ky Fan's lemma (citation unresolved: search-theorem failed with database connection error), there exists an alternating $d$-simplex $\sigma \in K$. By definition of an alternating $d$-simplex, its vertices can be ordered as $v_0,\dots,v_d$ so that their labels have pairwise distinct absolute values: \begin{align*} |\lambda(v_i)| \neq |\lambda(v_j)| \end{align*} whenever $0 \leq i < j \leq d$. [guided] The contradiction comes from counting absolute labels. Since we assumed there is no complementary edge, Ky Fan's lemma applies exactly to the labeling $\lambda: V(K) \to \{\pm 1,\dots,\pm d\}$. The parameter in Ky Fan's lemma is therefore $m=d$. Ky Fan's lemma gives an alternating $d$-simplex $\sigma$. A $d$-simplex has exactly $d+1$ vertices, so we may write its vertices as $v_0,\dots,v_d$. The word “alternating” means that, after a suitable ordering, the signs alternate and the absolute label values are strictly ordered; in particular, the absolute labels are pairwise distinct. Hence \begin{align*} |\lambda(v_i)| \neq |\lambda(v_j)| \end{align*} for all distinct indices $i,j \in \{0,\dots,d\}$. Only this pairwise-distinctness property is needed for the contradiction: an alternating $d$-simplex requires $d+1$ different absolute labels. [/guided] [/step] [step:Count the available absolute labels and obtain a contradiction] For every vertex $v \in V(K)$, the label $\lambda(v)$ lies in $\{\pm 1,\dots,\pm d\}$. Hence its absolute value lies in the $d$-element set \begin{align*} \{1,\dots,d\}. \end{align*} The alternating simplex $\sigma$ has vertices $v_0,\dots,v_d$, and the preceding step shows that the $d+1$ numbers \begin{align*} |\lambda(v_0)|,\dots,|\lambda(v_d)| \end{align*} are pairwise distinct elements of $\{1,\dots,d\}$. This is impossible, because a set with $d$ elements cannot contain $d+1$ pairwise distinct elements. [/step] [step:Conclude that a complementary edge exists] The contradiction arose only from the assumption that $K$ has no complementary edge. Therefore that assumption is false. Hence there exist adjacent vertices $u,v \in V(K)$ such that \begin{align*} \lambda(u) = -\lambda(v). \end{align*} This is precisely Tucker's lemma for $m=d$. [/step]