MathCastle
Graph TheoryHardPlanar Graphs

Planar Graphs · Hard problem

A graph has 1212 vertices 0,1,…,110,1,\ldots,11, with each vertex joined to the two vertices 11 step away around the cycle AND the two vertices 55 steps away (so 2424 edges in total). A brute-force search finds its girth. By how many edges does 2424 exceed the planar bound that matches this girth?