Data Structure Graph

837 views

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?

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.

edited
0
any graph which has 8 or less edge  is planar...so remove one edge
0

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

0
yes k33 has 9 edges.and we know that any graph less than 8 edge is planar..so remove 1 edge
0
OK...you 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.
0
yes

Related questions

1
144 views
//Just check create_graph function. #include <iostream> #include <malloc.h> using namespace std; struct Adj_node { int node; struct Adj_node *next; }; typedef struct Adj_node Adj_node; struct Edge { int src, dest; }; typedef struct Edge Edge; struct Graph { int v, e; Edge *edge; ... number of edges:"<<endl; cin>>e; create_graph(v, e); print_adj_list(); return 0; } How to get rid of this problem?
State and Explain True/False 1) If the priority queue in Dijkstra's algorithm is implemented using a sorted linked list (where the list is kept sorted after each priority queue operation) then dijkstra's algorithm would run in O(ElgV+VlgV) time. 2) If all edges weight of an undirected ... with n nodes, finding a path from root node of T to a given vertex $v\epsilon T$ using DFS takes O(log n) time