Subscribe to the weekly news from TrueShelf

0

Planar graphs and girth

Let \(G\) be an \(n\)-vertex simple connected planar graph with girth \(k\).

  • Prove that \(G\) has at most \((n-2)\cdot \frac{k}{k-2}\) edges.

  • Use this to prove that the Petersen graph is nonplanar.

Related Content