Guy's Conjecture

Guy's conjecture, which has not yet been proven or disproven, states that the Crossing Number for a Complete Graph of order $n$ is

$${1\over 4}\left\lfloor{n\over 2}\right\rfloor \left\lfloor{n... ...2\over 2}\right\rfloor \left\lfloor{n-3\over 2}\right\rfloor ,$$

where $\left\lfloor{x}\right\rfloor$ is the Floor Function, which can be rewritten

$$\cases{ {\textstyle{1\over 64}} n(n-2)^2(n-4) & for $n$\ even\cr {\textstyle{1\over 64}} (n-1)^2(n-3)^2 & for $n$\ odd.\cr}$$

The first few values are 0, 0, 0, 0, 1, 3, 9, 18, 36, 60, ... (Sloane's A000241).

See also Crossing Number (Graph)

References

Sloane, N. J. A. Sequence A000241/M2772 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.