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

1.6 Surgery

Recursive constructions

‘Tripling’ for triangulations of complete graphs: Grannell, Griggs and Širánˇ [GGS98] use
2-face-colourable triangulation of Kn to construct 2-face-colourable triangulation of
K3n−2. (Face colouring is important.)

• Take triangulation of Kn , cut out one vertex z , now have Kn−1 on surface with bound-
ary S.

• Take three copies of S: S0, S1, S2, where v i on Si corresponds to v on S, etc.
• For each white triangle t = (u v w ) cut out t 0, t 1, t 2 and glue on 2-face-colourable

toroidal embedding of K3,3,3 with vertex classes {u 0, u 1, u 2}, {v 0, v 1, v 2}, {w 0, w 1, w 2}
which has three black triangles (u i v i w i ) deleted. Gives all edges of K3n−3 except
those x i y j where i = j and x y incident with boundary and black triangle (then no
white triangle containing that edge), and edges of form x i x j where i = j .

• Now suppose boundary is (x1x2 . . . xn−1) (where n − 1 is even) where x1x2, x3x4, . . .

are incident with only black triangles. Construct derived embedding from 3-voltage

graph shown: contains

cycles (x 1i x i . . . x i −1 ) to glue on to boundaries of S0, S 1 , S 2 ,
2 n
10x 21x 31x 2 0
assuming 3 |n −1, hamilton cycle (x 4 . . . x n −1 ) in which to add extra vertex,

and all missing edges;