The Gateway to Computer Science Excellence
0 votes

What is the minimum number of edges which must be removed from a complete bipartite graph of six nodes K(6) so that the remaining graph is a planar?

Explain with exp why your answer is Right .

in Theory of Computation by Boss (45.4k points) | 681 views

1 Answer

0 votes

It is $K_{3, 3}$ because other combinations result in planar graphs. To regain planarity, we need to remove only 1 edge.

Non-planarity is introduced when we try to connect two vertices which are otherwise unreachable(i.e., require intersection with other edges) with respect to each other.

Lets say we start with $K_{2, 3}$ which is planar. Lets name the partitions $A$(with 2 vertices) and $B$. One can observe that there is one(and only one) vertex(in B) say $h$ which is now hidden in the sense that it cannot be reached from any vertex in $A$. Now trying to add another vertex $n$ in A and connecting it with all vertices of B,  will require connecting $n$ with $h$, which is possible only through intersection with other edge(s) and hence the introduction of non-planarity.

My reasoning is informal and possibly sloppy, Would anyone please provide rigorous proof/explanation for this problem.

by Active (1.8k points)
edited by
any graph which has 8 or less edge  is remove one edge

As per question, input is a non planar complete bipartite graph with 6 vertices which I think can only be $K_{3,3}$.

yes k33 has 9 edges.and we know that any graph less than 8 edge is remove 1 edge
0 mean removing 1 edge is the answer....I thought you are asking me to remove one edge from my answer making answer to the original question as 2.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,292 answers
104,909 users