info prev up next book cdrom email home

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

{\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)


Sloane, N. J. A. Sequence A000241/M2772 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.

© 1996-9 Eric W. Weisstein