The Gateway to Computer Science Excellence

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.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,258 answers

198,087 comments

104,735 users