Guy's Conjecture

Guy's conjecture, which has not yet been proven or disproven, states that the graph crossing number for a complete graph K_n is


where |_x_| is the floor function, which can be rewritten

 Z(n)={1/(64)n(n-2)^2(n-4)   for n even; 1/(64)(n-1)^2(n-3)^2   for n odd.

The values for n=1, 2, ... are then given by 0, 0, 0, 0, 1, 3, 9, 18, 36, 60, 100, 150, 225, 315, 441, 588, ... (OEIS A000241).

Guy (1972) proved the conjecture for n<=10, a result extended to n<=12 by Pan and Richter (2007).

It is known that


(Richter and Thomassen 1997, de Klerk et al. 2007, Pan and Richter 2007).

See also

Complete Bipartite Graph, Complete Graph, Graph Crossing Number, Zarankiewicz's Conjecture

Explore with Wolfram|Alpha


Brodsky, A.; Durocher, S.; and Gethner, E. "The Rectilinear Crossing Number of K_(10) Is 62." 22 Sep 2000. Klerk, E.; Pasechnik, D. V.; and Schrijver, A. "Reduction of Symmetric Semidefinite Programs Using the Regular *-Representation." Math Program. 109, 613-624, Klerk, E.; Maharry, J.; Pasechnik, D. V.; Richter, R. B.; Salazar, G. "Improved Bounds for the Crossing Numbers of K_(m,n) and K_n." 2004., R. K. "The Crossing Number of the Complete Graph." Bull. Malayan Math. Soc. 7, 68-72, 1960.Guy, R. K. "Crossing Numbers of Graphs." In Graph Theory and Applications: Proceedings of the Conference at Western Michigan University, Kalamazoo, Mich., May 10-13, 1972 (Ed. Y. Alavi, D. R. Lick, and A. T. White). New York: Springer-Verlag, pp. 111-124, 1972.Pan, S. and Richter, R. B. "The Crossing Number of K_(11) is 100." J. Graph Th. 56, 128-134, 2007.Sloane, N. J. A. Sequence A000241/M2772 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Guy's Conjecture

Cite this as:

Weisstein, Eric W. "Guy's Conjecture." From MathWorld--A Wolfram Web Resource.

Subject classifications