Planar subgraph.

Question

I have to find the greatest planar subgraph of $K_{m,n}$ where $m,n\le3$.

So, I know it and i can drow the plane graph with an edge at most $6+2(m-3)$.

But I can't show that the graph is the greatest.

Can someone for help.

Answer 1

You can think of $K_{2,3}$ as a pair of blue vertices at $(\pm 1, 0)$ and the partition of 3 red vertices along the $y$-axis, at $(0,0), (0,\pm 1)$.

Now add another blue vertex at $(0,1/2)$ and connect to its neighbors on the $y$-axis, and the result is $K_{3,3}$ which is missing just one edge.

Adding the edge would make a full $K_{3,3}$ which is not planar, so in that sense, our graph is maximal...