The **Harary-Hill Conjecture** states that the crossing number of complete graph K_{n} is

.

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 D_{1} and D_{2} be two drawing of graph K_{n} in the plane. Then one can transform D_{1} into D_{2 }using only -moves. As a corollary, the crossing number of D_{1} and D_{2 }is the same.

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

### Like this:

Like Loading...

Ph.D. student in the Department of Computer Science, University of Illinois at Urbana-Champaign.