Page 28 - Ellingham, Mark, Mariusz Meszka, Primož Moravec, Enes Pasalic, 2014. 2014 PhD Summer School in Discrete Mathematics. Koper: University of Primorska Press. Famnit Lectures, 3.
P. 28
1.4 Bouchet’s diamond sum
History: Used by Bouchet [Bo78a] in dual form for new proof of minimum genus of Km,n ,
1978. Primal form used by Mohar, Parsons and Pisanski [MPP85], and Magajna, Mo-
har and Pisanski [MMP86], mid-1980s. Mohar and Thomassen [MT] give primal ver-
sion of Bouchet’s proof in their book and use diamond notation, hence name ‘dia-
mond sum’. General form stated by Kawarabayashi, Stephens and Zha [KSZ04].
Theorem: The minimum genus of an orientable genus embedding of Km,n is g(Km,n ) =
(m − 2)(n − 2)/4 .
Proof: This was first proved by Ringel, 1965. But we will give a proof based on the dia-
mond sum, following the one in Mohar and Thomassen [MT]. Will use straightforward
primal arguments instead of Bouchet’s dual arguments.
Euler’s formula and the fact that face degrees must be at least 4 (since graph is simple
and bipartite) gives a lower bound of f 0(m , n ) = (m − 2)(n − 2)/4 on genus, which is
achieved if we have a quadrangular embedding (all facial walks are 4-cycles). Since genus
is integral, can round up: g(Km,n ) ≥ f (m , n ) = f 0(m , n ) = (m − 2)(n − 2)/4 .
F (m , n ) is the statement that g(Km,n ) = f (m , n ). We prove it for m , n ≥ 2 by induction
on m + n by constructing an embedding. Note that F (m , n) ⇔ F (n, m ). True if m = 2 or
n = 2 so suppose m , n ≥ 3.
Claim D: If F (m , n ) and F (p, n ) hold and at least one of f 0(m , n ) and f 0(p, n ) is integral,
then F (m + p − 2, n) holds.
Proof: Take the diamond sum of minimum genus embeddings of Km,n and Kp,n , deleting
a vertex in the first part of each bipartition. The resulting graph is Km+p−2,n with an
embedding of genus
f (m , n) + f (p, n) = f 0(m , n ) + f 0(p, n )
=
f 0(m , n ) + f 0(p, n ) as long as one of f 0(m , n ), f 0(p, n ) is integral
=
= (m − 2)(n − 2) (p − 2)(n − 2) (m + p − 4)(n − 2)
+=
44 4
f 0(m + p − 2, n ) = f (m + p − 2, n )
and so F (m + p − 2, n) holds.
History: Used by Bouchet [Bo78a] in dual form for new proof of minimum genus of Km,n ,
1978. Primal form used by Mohar, Parsons and Pisanski [MPP85], and Magajna, Mo-
har and Pisanski [MMP86], mid-1980s. Mohar and Thomassen [MT] give primal ver-
sion of Bouchet’s proof in their book and use diamond notation, hence name ‘dia-
mond sum’. General form stated by Kawarabayashi, Stephens and Zha [KSZ04].
Theorem: The minimum genus of an orientable genus embedding of Km,n is g(Km,n ) =
(m − 2)(n − 2)/4 .
Proof: This was first proved by Ringel, 1965. But we will give a proof based on the dia-
mond sum, following the one in Mohar and Thomassen [MT]. Will use straightforward
primal arguments instead of Bouchet’s dual arguments.
Euler’s formula and the fact that face degrees must be at least 4 (since graph is simple
and bipartite) gives a lower bound of f 0(m , n ) = (m − 2)(n − 2)/4 on genus, which is
achieved if we have a quadrangular embedding (all facial walks are 4-cycles). Since genus
is integral, can round up: g(Km,n ) ≥ f (m , n ) = f 0(m , n ) = (m − 2)(n − 2)/4 .
F (m , n ) is the statement that g(Km,n ) = f (m , n ). We prove it for m , n ≥ 2 by induction
on m + n by constructing an embedding. Note that F (m , n) ⇔ F (n, m ). True if m = 2 or
n = 2 so suppose m , n ≥ 3.
Claim D: If F (m , n ) and F (p, n ) hold and at least one of f 0(m , n ) and f 0(p, n ) is integral,
then F (m + p − 2, n) holds.
Proof: Take the diamond sum of minimum genus embeddings of Km,n and Kp,n , deleting
a vertex in the first part of each bipartition. The resulting graph is Km+p−2,n with an
embedding of genus
f (m , n) + f (p, n) = f 0(m , n ) + f 0(p, n )
=
f 0(m , n ) + f 0(p, n ) as long as one of f 0(m , n ), f 0(p, n ) is integral
=
= (m − 2)(n − 2) (p − 2)(n − 2) (m + p − 4)(n − 2)
+=
44 4
f 0(m + p − 2, n ) = f (m + p − 2, n )
and so F (m + p − 2, n) holds.
