MathCastle
Graph TheoryHardPlanar Graphs

Planar Graphs · Hard problem

Take K5K_5 on vertices 1,…,51,\ldots,5 and subdivide its three edges 1212, 1313, 2323, each by inserting one new degree-22 vertex (66 on edge 1212, 77 on edge 1313, 88 on edge 2323). For this graph GG (now on 88 vertices), find (3V−6)−E(3V-6) - E.