MathDB

A. 777

Part of KoMaL A Problems 2019/2020

Problems(1)

Planar Graph Crossings

Source: KöMaL A. 777

3/20/2022
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
combinatoricskomalplanar graphgraph theory