Two theorems on the minimum number of intersections for complete graphs
Joseph M. Katz Graduate School of Business
University of Pittsburgh
: Jun, 1967
: Journal of Combinatorial TheoryVol.: 2- Issue: 4- Pages: 571-584
: Journal of Combinatorial Theory
: After summarizing results of work on a conjecture regarding the minimum number of intersections of a complete graph drawn in the plane, the paper gives two theorems: one regarding a realization scheme for the conjectured quantity, and the other regarding a proof that essentially, the result would be minimal if it could be shown that a complete graph on n vertices with a minimum number of intersections contains a complete subgraph on n−2 vertices with a minimum number of intersections.
: Complete graph, Minumum number of intersections