Page 41 - Ellingham, Mark, Mariusz Meszka, Primož Moravec, Enes Pasalic, 2014. 2014 PhD Summer School in Discrete Mathematics. Koper: University of Primorska Press. Famnit Lectures, 3.

k Ellingham: Construction Techniques for Graph Embeddings 29

• What do components of D look like? For a given triangle t and x ∈ T , for any other
triangle t there is x ∈ t such that x and x are in the same component of D. So
D has at most three components, and each component contains a fixed number of
vertices of each triangle.
For example, in the octahedron (as shown) there are three components of D with
even vertex sets {p,q }, {w, y }, {x , z }. Take

(t1 + t5) + (t1 + t4) + (t1 + t2) = 3t1 + t2 + t4 + t5
= ±(p ± q ) ± (w ± y ) ± (x ± z )

which is generative for any m (even or odd).

Theorem: Suppose m is odd and Ψ is a triangulation of eulerian G . Then Ψ has a gener-
ative m -valuation and hence a triangular embedding of G(m) of the same orientability as
Ψ.

Proof:
• Fix a triangle t = (x y z ). Choose values so (x , t ) = (y .t ) = (z , t ) = 1.
• Partition each component of D into pairs of vertices, as follows:

- if there is a leftover vertex make sure it is a vertex of t ;
- if a vertex of t is in one of the pairs (u i , vi ), make sure it is u i (so its coefficient

is definitely 1, not −1).
If all components of D are even, just add up all α(u i , vi ) as mentioned

above: all coefficients are ±1.
• If some component of D is odd then adding up all α(u i , vi ) will leave out some ele-

ment(s) of t . So add up all α(u i , vi ) and add t = x + y + z . Now all coefficients ±1
except possibly coefficients of 2 for x , y or z : since m is odd, still generative.