MathCastle
Graph TheoryMediumPlanar Graphs

Planar Graphs · Medium problem

A network has 55 "north" hubs and 66 "south" hubs. Every north hub connects to every south hub, and there are also 22 extra direct connections between pairs of north hubs. If this network (now 3232 edges on 1111 vertices) is to be drawn with no crossings, by how many edges does it exceed the correct planar maximum?