graph G is complete bipratite graph K4,4
let one side vertices V1={v1, v2, v3, v4}
the other side vertices V2={u1,u2, u3, u4}
While solving a problem "how many edges removed G can be a planer graph"
solution solve the problem using v-e+f=2 4f=2e answer is 4
But, i use Kuratowski's thm.
minor grpah of G can not be K5 so l only consider k3,3
when i remove two edges there exist subgraph k3,3
when i remove three edges G have no subgrph k3,3 But condition of kuratowsi' thm is minor grpah
i dont know how to show that when remove three edges there exist minor grpah of G iso to k3,3
Best Answer
Well, the first answer is "so, don't do that". Using Euler's formula for bipartite graphs gives us an easy way to prove that at least $4$ edges need to be deleted. Using Kuratowski's theorem is going to be harder, because we'll need to care about which edges we delete, and because finding minors in a graph is hard.
But let's ignore that, and forge on.
First of all, although there are many ways to remove $3$ edges from $K_{4,4}$, we'll only need to care about one of them.
Suppose at least $2$ of the three edges we delete share an endpoint. Then there's a $K_{3,3}$ subgraph in the graph remaining! From the side where two deleted edges share an endpoint, take the three vertices not including that endpoint (automatically missing those two deleted edges). From the other side, take three vertices not including the endpoint of the third edge. Then all $9$ edges between the vertices we chose are still present, and we get $K_{3,3}$.
A $K_{3,3}$ subgraph is definitely a $K_{3,3}$ minor, so in this case, the graph we're left with is definitely not planar.
Now suppose we delete three edges that don't share any endpoints. Well, in $K_{4,4}$, all vertices on each side look identical. So we'll get isomorphic graphs no matter which three edges we delete. Here's one way to do it, identical to all the others (the missing edges are edges $15$, $26$, and $37$):
Here, we can get a $K_{3,3}$ by deleting edges $28$ and $47$, then contracting edges $17$ and $27$:
You can check that if one side has vertices $3,4$, and the combined $\{1,2,7\}$, and the other side has vertices $5, 6, 8$, then all edges between the two sides are present, and we have a $K_{3,3}$ minor.