[proofplan] We prove the stronger statement that every Sperner-labeled triangulation of $\triangle^d$ contains an odd number of fully labeled $d$-simplices. The proof is by induction on $d$. For the inductive step, we count incidences between $d$-simplices and their facets labeled exactly by $\{0,\dots,d-1\}$. Interior facets contribute twice, boundary facets contribute only on the face opposite $e_d$, and the induction hypothesis makes that boundary contribution odd; the parity is therefore forced to come from an odd number of fully labeled $d$-simplices. [/proofplan] [step:Prove the odd-count strengthening by induction on the dimension] For each integer $d \geq 0$, let $P(d)$ be the assertion that every Sperner labeling of every finite triangulation of $\triangle^d$ has an odd number of $d$-simplices whose vertex labels are exactly $\{0,1,\dots,d\}$. For $d=0$, the simplex $\triangle^0$ consists of the single vertex $e_0$. The unique $0$-simplex has label $0$ by the Sperner condition, so the number of fully labeled $0$-simplices is $1$, which is odd. Assume now that $d \geq 1$ and that $P(d-1)$ holds. We prove $P(d)$ for a fixed finite triangulation $\tau$ of $\triangle^d$ and a fixed Sperner labeling $\lambda: V(\tau) \to \{0,1,\dots,d\}$. [guided] We strengthen the theorem because the parity argument naturally proves more than existence. Instead of only showing that there is at least one fully labeled simplex, we show that the number of fully labeled simplices is odd. An odd number is in particular nonzero. The base case is $d=0$. The standard simplex $\triangle^0$ is the single point $e_0$. Its only triangulation has one $0$-simplex, namely that point. Since $e_0$ lies in the face indexed by $\{0\}$, the Sperner condition forces its label to be $0$. Hence there is exactly one fully labeled $0$-simplex, and $1$ is odd. Now fix $d \geq 1$ and assume the odd-count statement has already been proved in dimension $d-1$. We must prove it in dimension $d$ for an arbitrary finite triangulation $\tau$ of $\triangle^d$ and an arbitrary Sperner labeling $\lambda: V(\tau) \to \{0,1,\dots,d\}$. The rest of the proof will use only parity of finite sets, together with the induction hypothesis on the boundary face opposite $e_d$. [/guided] [/step] [step:Restrict the labeling to the face opposite $e_d$] Define the face \begin{align*} F := \operatorname{conv}\{e_0,\dots,e_{d-1}\} \subset \triangle^d. \end{align*} Let $\tau_F$ be the induced triangulation of $F$, consisting of all simplices of $\tau$ contained in $F$. If $v \in V(\tau_F)$, then $v \in F$, so the Sperner condition gives $\lambda(v) \in \{0,1,\dots,d-1\}$. Thus define the restricted labeling as the map \begin{align*} \lambda_F: V(\tau_F) \to \{0,1,\dots,d-1\}, \qquad \lambda_F(v) = \lambda(v) \text{ for every } v \in V(\tau_F). \end{align*} This map is a Sperner labeling of $\tau_F$ as a triangulation of $F \cong \triangle^{d-1}$. By the induction hypothesis $P(d-1)$, the number of $(d-1)$-simplices of $\tau_F$ whose vertex labels are exactly $\{0,1,\dots,d-1\}$ is odd. [/step] [step:Count selected facets by incidences with top-dimensional simplices] Call a $(d-1)$-simplex $\rho$ of $\tau$ selected if its vertex labels are exactly $\{0,1,\dots,d-1\}$. Define the finite incidence set \begin{align*} I := \{(\sigma,\rho) : \sigma \in \tau \text{ is a } d\text{-simplex},\ \rho \text{ is a selected facet of } \sigma\}. \end{align*} We count $|I|$ modulo $2$ in two ways. First count by selected facets. If a selected facet $\rho$ lies in the interior of $\triangle^d$, then it is a facet of exactly two $d$-simplices of $\tau$. If $\rho$ lies in $\partial \triangle^d$, then it is a facet of exactly one $d$-simplex of $\tau$. A selected boundary facet cannot lie in the face opposite $e_j$ for any $j \in \{0,\dots,d-1\}$, because every vertex of that face has label different from $j$ by the Sperner condition, while a selected facet has a vertex labeled $j$. Therefore every selected boundary facet lies in $F$. It follows that the parity of $|I|$ is the parity of the number of selected $(d-1)$-simplices contained in $F$. By the preceding step, this number is odd. Hence $|I|$ is odd. [guided] The incidence set records every time a top-dimensional simplex contains a facet with the special label set $\{0,\dots,d-1\}$. We define \begin{align*} I := \{(\sigma,\rho) : \sigma \in \tau \text{ is a } d\text{-simplex},\ \rho \text{ is a selected facet of } \sigma\}. \end{align*} This set is finite because the triangulation $\tau$ is finite. We count $I$ by first fixing the selected facet $\rho$. If $\rho$ is an interior facet of the triangulation, then the definition of a triangulation of a manifold with boundary implies that exactly two $d$-simplices of $\tau$ meet along $\rho$. Hence such a facet contributes exactly $2$ elements to $I$, which is $0$ modulo $2$. If $\rho$ lies on the boundary $\partial \triangle^d$, then it is a facet of exactly one $d$-simplex of $\tau$, so it contributes exactly $1$ element to $I$. We must identify which boundary faces can contain a selected facet. Let $G_j := \operatorname{conv}\{e_i : i \neq j\}$ be the face opposite $e_j$. If $j \in \{0,\dots,d-1\}$ and $v \in V(\tau) \cap G_j$, then the Sperner condition gives $\lambda(v) \neq j$. Therefore no simplex contained in $G_j$ can have all labels $\{0,\dots,d-1\}$, since the label $j$ is missing from every one of its vertices. Thus a selected boundary facet cannot lie in any $G_j$ with $j < d$. The only remaining boundary face is \begin{align*} F = G_d = \operatorname{conv}\{e_0,\dots,e_{d-1}\}. \end{align*} Therefore, modulo $2$, all interior selected facets disappear because they contribute twice, and all selected boundary facets are precisely the selected facets lying in $F$. By the induction hypothesis applied to the Sperner-labeled triangulation $\tau_F$ of $F$, the number of such facets is odd. Hence $|I|$ is odd. [/guided] [/step] [step:Compute each simplex contribution to the incidence count] Now count $I$ by fixing a $d$-simplex $\sigma \in \tau$. Let $m(\sigma)$ denote the number of selected facets of $\sigma$. Since $\sigma$ has exactly $d+1$ vertices, the following alternatives hold. If the labels on $\sigma$ are exactly $\{0,1,\dots,d\}$, then $m(\sigma)=1$: the unique selected facet is obtained by deleting the vertex labeled $d$. If the labels on $\sigma$ contain all labels $\{0,1,\dots,d-1\}$ but do not contain $d$, then among the $d+1$ vertices of $\sigma$ one label in $\{0,\dots,d-1\}$ occurs twice and every other label in $\{0,\dots,d-1\}$ occurs once. The selected facets are exactly the two facets obtained by deleting one of the two vertices with the repeated label, so $m(\sigma)=2$. If the labels on $\sigma$ do not contain all labels $\{0,1,\dots,d-1\}$, then no facet of $\sigma$ is selected, so $m(\sigma)=0$. Thus \begin{align*} |I| = \sum_{\sigma} m(\sigma), \end{align*} where the sum is over all $d$-simplices $\sigma$ of $\tau$, and modulo $2$ this sum equals the number of fully labeled $d$-simplices of $\tau$. [/step] [step:Conclude that a fully labeled simplex exists] The previous two steps show that $|I|$ is odd and that $|I|$ has the same parity as the number of fully labeled $d$-simplices of $\tau$. Therefore the number of $d$-simplices whose vertex labels are exactly $\{0,1,\dots,d\}$ is odd. In particular, it is nonzero. This proves $P(d)$, completing the induction. Hence every Sperner labeling of a finite triangulation of $\triangle^d$ contains at least one $d$-simplex whose vertex labels are exactly $\{0,1,\dots,d\}$. [/step]