MathDB
Planar Graph Crossings

Source: KöMaL A. 777

March 20, 2022
combinatoricskomalplanar graphgraph theory

Problem Statement

A finite graph G(V,E)G(V,E) on nn points is drawn in the plane. For an edge ee of the graph, let χ(e)\chi(e) denote the number of edges that cross over edge ee. Prove that ∑e∈E1χ(e)+1≤3n−6.\sum_{e\in E}\frac{1}{\chi(e)+1}\leq 3n-6.Proposed by Dömötör Pálvölgyi, Budapest
Back to ProblemsView on AoPS