2,735 views

1 Answer

0 votes
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

Related questions

–4 votes
–4 votes
2 answers
1
Souvik33 asked Oct 27, 2022
602 views
*MSQ*The following figure depicts a a. A tree and only treeb. A tree with 3 nodesc. A graph (Since every tree is a graph)d. A graph and only graph
0 votes
0 votes
0 answers
3
Lakshman Bhaiya asked Oct 21, 2018
884 views
$1)$How many different adjacency matrices does a graph with n vertices and E edgeshave?$2)$How many different adjacency lists does a graph with n vertices have?
0 votes
0 votes
0 answers
4