Subscribe to the weekly news from TrueShelf

0

Crossing number

The crossing number \(cr(G)\) of a graph \(G\) is the lowest number of edge crossings of a plane drawing of the graph \(G\).

  • Prove that the crossing number of \(K_n\) (the complete graph on \(n\) vertices) is at least \(\frac{1}{5}{n \choose 4}\).

Related Content