search
Log In
0 votes
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?

Explain with exp why your answer is Right .

in Theory of Computation 837 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.


edited by
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

0 votes
0 answers
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?
asked Apr 8, 2018 in Programming Jason 144 views
0 votes
0 answers
2
166 views
No of Simple Undirected Graph with unablled vertices - 2nC2 No of Simple Undirected Graph with labelled vertices - ? No of Simple Undirected Connected Graph with unablled vertices - ? No of Simple Undirected Connected Graph with labelled vertices - ?
asked Feb 5, 2017 in Programming yg92 166 views
0 votes
0 answers
3
129 views
WHY CROSS EDGES TURN TO BE BACK EDGES IN UNDIRECTED GRAPH IN DFS TRAVERSAL?? CAN ANYONE EXPLAIN THIS. WHY ARE THERE NO CROSS EDGES IN DFS OF UNDIRECTED GRAPH??
asked Feb 3, 2017 in Programming sushmita 129 views
0 votes
0 answers
4
104 views
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
asked Dec 30, 2017 in Theory of Computation srestha 104 views
...