MathCastle
Graph TheoryChallengePlanar Graphs

Planar Graphs · Challenge problem

Let GG be the graph on vertices 0,1,…,80,1,\ldots,8 forming the 99-cycle (01,12,23,34,45,56,67,78,8001,12,23,34,45,56,67,78,80) together with the two chords 0404 and 2727. Using GG's girth in the general edge bound E≤gg−2(V−2)E \le \frac{g}{g-2}(V-2), what is the largest possible integer value of EE for a connected simple PLANAR graph on 99 vertices with the same girth as GG?