Finite Playground

To verify is human; to prove, divine.


Leave a comment

Crossing number of Kn and Gioan’s Theorem

The Harary-Hill Conjecture states that the crossing number of complete graph Kn is

\displaystyle \frac{1}{4} \left\lfloor\frac{n\vphantom{-0}}{2}\right\rfloor \left\lfloor\frac{n-1}{2}\right\rfloor \left\lfloor\frac{n-2}{2}\right\rfloor \left\lfloor\frac{n-3}{2}\right\rfloor.

Instead of looking at all possible drawings (which is infinite), we can partition the drawings into classes, depending on the rotation system of the drawing.

The following theorem guarantees us that the crossing number is still well-defined.

Gioan’s Theorem.  Let D1 and D2 be two drawing of graph Kn in the plane.  Then one can transform D1 into Dusing only \Delta-moves.  As a corollary, the crossing number of D1 and Dis the same.

Noted that in general this is not true when the graph is not complete.

Advertisements