MathCastle
Graph TheoryMediumPlanar Graphs

Planar Graphs · Medium problem

Take K4,4K_{4,4} (the complete bipartite graph with parts of size 44 each) and remove a perfect matching (a set of 44 non-adjacent edges, one from each vertex pair). Is the resulting graph planar?