Page 30 - 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.4 Bouchet’s diamond sum

h.c. ↔ ↔
face

h.c. h.c.
face face

Hamilton cycle embedding of some r -regular n -vertex G
↔ Triangular (hence min. genus) embedding of join Kr + G
↔ Quadrangular (hence min. genus) embedding of Kr,n .

So the middle step here is a complete bipartite graph with edges added on one side, and
the last step tells us that we added edges to a minimum genus embedding of Kr,n . So
we can now proceed as follows:

Hamilton cycle embedding of r -regular n-vertex G

Triangular (hence minimum genus) embedding of join Kr + G
|

because contains min. genus emb. of Kr,n
↓

Minimum genus embedding of join Kr + H for any spanning subgraph H of G
|

diamond sum with min. genus embedding of Kn,s −r +2
↓

Guaranteed minimum genus embedding of Ks + H for all s ≥ r and spanning H ⊆ G .

Exercise: Prove that the nonorientable genus of Km,n is (m − 2)(n − 2)/2 for m , n ≥ 3,
given that this is known to be a lower bound on the genus. First find an embedding
of K3,4 in the projective plane N1. Then use the diamond sum for induction.

Exercise: Suppose we can construct an orientable hamilton cycle embedding of Kn,n,n
for some particular n . For what family of graphs (as large as possible) can we then
use the diamond sum to obtain minimum orientable genus embeddings?
Repeat the question for Kn,n,n,n .