Just to close the loop on this. I found a simple combinatorial proof that an antipodally symmetric labelling of the boundary always allows for a valid Sperner coloring. This means Tucker’s Lemma actually follows directly from Sperner’s Lemma with a combinatorial argument (in two dimensions). This is quite a surprise to me, because in the literature, Tucker’s Lemma/Borsuk-Ulam Theorem is generally considered stronger, in the sense that it implies Sperner’s Lemma/Brouwer’s Fixed Point Theorem.

Here is a simple proof about the labelling, a proof by induction over antipodally symmetric pairs of boundary vertices.

For the remainder of the proof, we exclude all the cases with a complementary edge on the boundary, as there is nothing more to prove (complementary edge exists).

In the diagrams, the lines do not indicate the triangulation; the lines just indicate the antipodally symmetric pair of vertices.

Induction Base Case($2n=4$): This case obviously allows for a valid Sperner coloring, i.e. a Sperner triangle and hence a complementary edge exists inside the triangulated polygon.

Induction Step from $2n$ to $2n+2$: Assume that the boundary has a valid Sperner coloring for its $2n$ antipodally symmetric labelled vertices. Valid Sperner coloring means that the number of color changes on the boundary is uneven (i.e. uneven number of boundary edges with endpoints of different color). Now we include another pair of antipodally symmetric pair of boundary vertices, to arrive at $2n+2$ vertices with valid Sperner coloring. When including a new pair, we have to insert it in-between two existing pairs of vertices. There are just four different cases to consider:

For case A, because we don’t allow for complementary edges on the boundary, we can only include an antipodally symmetric labelled pair of vertices with 1 or 2 on one side, as in the diagram. But this does not add any color change to the boundary, i.e. the boundary just keeps its valid Sperner coloring. An analoguous argument works for case B.

For case C, because we don’t allow for complementary edges on the boundary, we can only include an antipodally symmetric labelled pair of vertices with 1, 2, or -2 on one side, as in the diagram. But if it is 1, it does not not add any color change to the boundary. And if it is 2 or -2, it just adds an even number of color changes to the boundary. In both cases, the number of color changes remains uneven, i.e. the Sperner coloring of the boundary remains valid.An analoguous argument works for case D.

Conclusion of Induction: So we have shown that a valid Sperner coloring for $2n$ antipodally symmetric labelled vertices implies that the Sperner coloring is also valid for $2n+2$ antipodally symmetric labelled vertices vertices. So starting from $2n=4$, it is valid for all $2n$, which concludes the proof.

Just to close the loop on this. I now found a simple proof that an antipodally symmetric labelling of the boundary always has a valid Sperner coloring (in two dimensions). This means Tucker’s Lemma actually follows directly from Sperner’s Lemma with a combinatorial argument. This is quite a surprise to me, because in the literature, Tucker’s Lemma/Borsuk-Ulam Theorem is generally considered stronger, in the sense that it implies Sperner’s Lemma/Brouwer’s Fixed Point Theorem.

Here is the proof about the compatible labelling, a proof by induction over antipodally symmetric pairs of boundary vertices. It assumes the coloring from the OP questions above.

For the remainder of the proof, we exclude all the cases with a complementary edge on the boundary, as there is nothing more to prove (complementary edge exists).

In the diagrams, the lines do not indicate the triangulation; the lines just indicate the antipodally symmetric pair of vertices.

Induction Base Case($2n=4$): This case obviously allows for a valid Sperner coloring, i.e. a Sperner triangle and hence a complementary edge exists inside the triangulated polygon.

Induction Step from $2n$ to $2n+2$: Assume that the boundary has a valid Sperner coloring for its $2n$ antipodally symmetric labelled vertices. Valid Sperner coloring means that the number of color changes on the boundary is uneven (i.e. uneven number of boundary edges with endpoints of different color). Now we include another pair of antipodally symmetric pair of boundary vertices, to arrive at $2n+2$ vertices with valid Sperner coloring. When including a new pair, we have to insert it in-between two existing pairs of vertices. There are just four different cases to consider:

For case A, because we don’t allow for complementary edges on the boundary, we can only include an antipodally symmetric labelled pair of vertices with 1 or 2 on one side, as in the diagram. But this does not add any color change to the boundary, i.e. the boundary just keeps its valid Sperner coloring. An analoguous argument works for case B.

For case C, because we don’t allow for complementary edges on the boundary, we can only include an antipodally symmetric labelled pair of vertices with 1, 2, or -2 on one side, as in the diagram. But if it is 1, it does not not add any color change to the boundary. And if it is 2 or -2, it just adds an even number of color changes to the boundary. In both cases, the number of color changes remains uneven, i.e. the Sperner coloring of the boundary remains valid.An analoguous argument works for case D.

Conclusion of Induction: So we have shown that a valid Sperner coloring for $2n$ antipodally symmetric labelled vertices implies that the Sperner coloring is also valid for $2n+2$ antipodally symmetric labelled vertices vertices. So starting from $2n=4$, it is valid for all $2n$, which concludes the proof.

Just to close the loop on this. I found a simple combinatorial proof that an antipodally symmetric labelling of the boundary always allows for a valid Sperner coloring. This means Tucker’s Lemma actually follows directly from Sperner’s Lemma with a combinatorial argument (in two dimensions). This is quite a surprise to me, because in the literature, Tucker’s Lemma/Borsuk-Ulam Theorem is generally considered stronger, in the sense that it implies Sperner’s Lemma/Brouwer’s Fixed Point Theorem.

Here is a simple proof about the labelling, a proof by induction over antipodally symmetric pairs of boundary vertices.

For the remainder of the proof, we exclude all the cases with a complementary edge on the boundary, as there is nothing more to prove (complementary edge exists).

Beginning of Induction ($2n=4$): This case obviously allows for a valid Sperner coloring, i.e. a Sperner triangle and hence a complementary edge exists inside the triangulated polygon.

Induction Step from $2n$ to $2n+2$: Assume that the boundary has a valid Sperner coloring for its $2n$ antipodally symmetric labelled vertices. Valid Sperner coloring means that the number of color changes on the boundary is uneven (i.e. uneven number of boundary edges with endpoints of different color). Now we include another pair of antipodally symmetric pair of boundary vertices, to arrive at $2n+2$ vertices with valid Sperner coloring. There are just four different cases to consider:

For case A, because we don’t allow for complementary edges on the boundary, we can only include an antipodally symmetric labelled pair of vertices with 1 or 2 on one side, as in the diagram. But this does not add any color change to the boundary, i.e. the boundary just keeps its valid Sperner coloring. An analoguous argument works for case B.

For case C, because we don’t allow for complementary edges on the boundary, we can only include an antipodally symmetric labelled pair of vertices with 1, 2, or -2 on one side, as in the diagram. But if it is 1, it does not not add any color change to the boundary. And if it is 2 or -2, it just adds an even number of color changes to the boundary. In both cases, the number of color changes remains uneven, i.e. the Sperner coloring of the boundary remains valid.An analoguous argument works for case D.

Conclusion of Induction: So we have shown that a valid Sperner coloring for $2n$ antipodally symmetric labelled vertices implies that the Sperner coloring is also valid for $2n+2$ antipodally symmetric labelled vertices vertices. So starting from $2n=4$, it is valid for all $2n$, which concludes the proof.

Just to close the loop on this. I found a simple combinatorial proof that an antipodally symmetric labelling of the boundary always allows for a valid Sperner coloring. This means Tucker’s Lemma actually follows directly from Sperner’s Lemma with a combinatorial argument (in two dimensions). This is quite a surprise to me, because in the literature, Tucker’s Lemma/Borsuk-Ulam Theorem is generally considered stronger, in the sense that it implies Sperner’s Lemma/Brouwer’s Fixed Point Theorem.

Here is a simple proof about the labelling, a proof by induction over antipodally symmetric pairs of boundary vertices.

For the remainder of the proof, we exclude all the cases with a complementary edge on the boundary, as there is nothing more to prove (complementary edge exists).

In the diagrams, the lines do not indicate the triangulation; the lines just indicate the antipodally symmetric pair of vertices.

Induction Base Case($2n=4$): This case obviously allows for a valid Sperner coloring, i.e. a Sperner triangle and hence a complementary edge exists inside the triangulated polygon.

Induction Step from $2n$ to $2n+2$: Assume that the boundary has a valid Sperner coloring for its $2n$ antipodally symmetric labelled vertices. Valid Sperner coloring means that the number of color changes on the boundary is uneven (i.e. uneven number of boundary edges with endpoints of different color). Now we include another pair of antipodally symmetric pair of boundary vertices, to arrive at $2n+2$ vertices with valid Sperner coloring. When including a new pair, we have to insert it in-between two existing pairs of vertices. There are just four different cases to consider:

For case A, because we don’t allow for complementary edges on the boundary, we can only include an antipodally symmetric labelled pair of vertices with 1 or 2 on one side, as in the diagram. But this does not add any color change to the boundary, i.e. the boundary just keeps its valid Sperner coloring. An analoguous argument works for case B.

For case C, because we don’t allow for complementary edges on the boundary, we can only include an antipodally symmetric labelled pair of vertices with 1, 2, or -2 on one side, as in the diagram. But if it is 1, it does not not add any color change to the boundary. And if it is 2 or -2, it just adds an even number of color changes to the boundary. In both cases, the number of color changes remains uneven, i.e. the Sperner coloring of the boundary remains valid.An analoguous argument works for case D.

Conclusion of Induction: So we have shown that a valid Sperner coloring for $2n$ antipodally symmetric labelled vertices implies that the Sperner coloring is also valid for $2n+2$ antipodally symmetric labelled vertices vertices. So starting from $2n=4$, it is valid for all $2n$, which concludes the proof.